Расписания выполнения заданий во взаимосвязанных последовательно работающих производственных системах

Классическая в теории расписаний задача построения последовательности выполнения заданий на одной машине в условиях наличия ограничений на времена начала и завершения выполнения заданий и учитывающая не только затраты времени на работу оборудования, но и потери на постобработку, рассмотрена для многостадийных производственных систем, состоящих из взаимосвязанной цепочки участков и цехов промышленного предприятия. Критерием оптимальности задачи является выполнение многостадийного расписания в кратчайшие сроки. Рассматриваемые в работе задачи относятся к классу NP-полных задач экспоненциальной сложности. Исследованы свойства допустимых и оптимальных последовательностей выполнения заданий. Предложены методы расчета нижней границы длины оптимального расписания и правила отсева недопустимых и неоптимальных продолжений. Разработаны алгоритмы точного и приближенного решения задачи модифицированными методами ветвей и границ. Предложенные алгоритмы проиллюстрированы числовыми примерами. Выполненные автором вычислительные эксперименты показали, что наличие системы строгих ограничений на сроки выполнения заданий при реализации предложенных в работе алгоритмов в ряде случаев существенно сокращает число рассматриваемых вариантов.