Research indexJournal article
РАСПИСАНИЯ ВЫПОЛНЕНИЯ ЗАДАНИЙ ВО ВЗАИМОСВЯЗАННЫХ ПОСЛЕДОВАТЕЛЬНО РАБОТАЮЩИХ ПРОИЗВОДСТВЕННЫХ СИСТЕМАХ
Зак
Russian Agency for Digital Standardization1 Jan 2020Open access
NobleIDark:/48914/w1/20260525/0F302054DOI10.25728/pu.2020.5.9
РАСПИСАНИЯ ВЫПОЛНЕНИЯ ЗАДАНИЙ ВО ВЗАИМОСВЯЗАННЫХ ПОСЛЕДОВАТЕЛЬНО РАБОТАЮЩИХ ПРОИЗВОДСТВЕННЫХ СИСТЕМАХ
Зак · Russian Agency for Digital Standardization · 2020
NobleIDark:/48914/w1/20260525/0F302054DOI10.25728/pu.2020.5.9
Free to read at the publisher
You can read the abstract here, or the full text at the publisher.
Abstract
Классическая в теории расписаний задача построения последовательности выполнения заданий на одной машине в условиях наличия ограничений на времена начала и завершения выполнения заданий и учитывающая не только затраты времени на работу оборудования, но и потери на постобработку, рассмотрена для многостадийных производственных систем, состоящих из взаимосвязанной цепочки участков и цехов промышленного предприятия. Критерием оптимальности задачи является выполнение многостадийного расписания в кратчайшие сроки. Рассматриваемые в работе задачи относятся к классу NP-полных задач экспоненциальной сложности. Исследованы свойства допустимых и оптимальных последовательностей выполнения заданий. Предложены методы расчета нижней границы длины оптимального расписания и правила отсева недопустимых и неоптимальных продолжений. Разработаны алгоритмы точного и приближенного решения задачи модифицированными методами ветвей и границ. Предложенные алгоритмы проиллюстрированы числовыми примерами. Выполненные автором вычислительные эксперименты показали, что наличие системы строгих ограничений на сроки выполнения заданий при реализации предложенных в работе алгоритмов в ряде случаев существенно сокращает число рассматриваемых вариантов.