задачи оптимизации многостадийного процесса.

Оптимизация процессов обработки заданий в дискретных многостадийных системах dslib.net Библиотека диссертаций Навигация Для нормальной работы сайта необходимо включить JavaScript → → Оптимизация процессов обработки заданий в дискретных многостадийных системах Мирецкий Игорь Юрьевич Диссертация, - 15у.е., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья Автореферат - 6 у.е., доставка 10 минут, круглосуточно, без выходных и праздников Мирецкий Игорь Юрьевич. Оптимизация процессов обработки заданий в дискретных многостадийных системах : Дис. ... д-ра техн. наук : 05.13.01 : Пенза, 2003 363 c. РГБ ОД, 71:04-5/573 Введение к работе Актуальность темы. Вопросам повышения эффективности функционирования систем неизменно уделяется значительное внимание. С середины 50-х годов XX века (после опубликования результатов исследований С. Джонсона и Р. Беллмана по планированию работы сборочных линий) для решения задач оптимизации работы дискретных систем активно используют модели и методы теории расписаний.Исследования в теории расписаний имеют как теоретическую, так и практическую значимость. Они проводятся с целью уменьшения длительности производственного цикла, уменьшения запаздывания работ относительно установленных сроков и т. п., то есть в конечном итоге направлены на совершенствование механизмов планирования и управления производственными процессами. Этим объясняется неослабевающий интерес к задаче Беллмана-Джонсона и ее обобщениям - классу задач теории расписаний, связанных с решением проблемы составления оптимального плана работы систем последовательного типа (дискретных многостадийных систем). Задачи этого класса являются предметом диссертационного исследования.Задачи теории расписаний в большинстве своем оказываются трудно решаемыми (Garey М. R., Johnson R. S.). Задача Беллмана-Джонсона является М'-трудной. Первоначально для ее решения предлагались точные подходы, а также метод случайного поиска (Heller J., Nugent С. Е.). Аналитические результаты получены в основном средствами комбинаторного анализа. Комбинаторные исследования проводились при рассмотрении частных случаев, для выявления условий элиминации и доминирования (Белов И. С, Бурдюк В. Я., Столин Я. Н., Johnson S. М., Gupta J. N. D., Nabeshima I., Szwarc W.).Как точные методы решения задачи Беллхмана-Джонсона и ее обобщений предлагались схемы ветвей и границ (Schrage L., Ignal Е., Dudek R. A., Campbell Н. G., Lawler E. L., Lenstra J. K., Rin-nooy Kan A. H. G.), динамического программирования (Беллман P., Карп P., Якимов P. M.), целочисленного программирования (Мап-ne A. S., Story А. Е., Wagner Н. М.). Однако точные методы можноPOC НАЦИОНАЛЬНА» { БИБЛИОТЕКА |использовать лишь для решения задач небольшой размерности.После того, как была установлена ЛГР-трудность задачи Беллма-на-Джонсона (Garey М. R., Johnson R. S., Sethi Ravi), исследования в основном проводятся в области приближенных подходов и связаны с построением эффективных приближенных алгоритмов. Наиболее интенсивные разработки ведутся в области алгоритмов с гарантированными оценками точности и алгоритмов локального поиска.Одним из основных направлений в современной дискретной оптимизации и, в частности, в теории расписаний является разработка р-приближающих алгоритмов (Севастьянов С. В., Спесивцев А. В., Hall L. A., Potts С. N.). Препятствием к построению алгоритм