Двухстадийные задачи планирования для поточной линии

Сформулирована задача построения расписаний двухстадийной обработки множества изделий на двух расположенных в последовательную цепочку системах машин в одной и той же и одинаковой для всех изделий последовательности. Число машин на каждой стадии обработки может быть различным. Ни одна из выполняемых операций не допускает прерываний в процессе ее выполнения. Учтены также потери времени на постобработку после завершения первой стадии изготовления. В качестве критерия оптимальности рассмотрено выполнение всего комплекса работ в кратчайшие сроки. Получены оценки нижней границы оптимальной последовательности обработки изделий, обеспечивающие выполнение всех работ на двух стадиях обработки в кратчайшие сроки. Предложены алгоритмы точного и приближенного решения задачи методами ветвей и границ и динамического программирования, а также эвристический алгоритм полиномиальной сложности получения приближенных решений. Алгоритмы решения проиллюстрированы на числовом примере. Полученные результаты могут найти широкое применение в системах календарного планирования работы производственных участков и цехов машиностроительного и приборостроительного производства, а также в процессах деревообработки, электронной и легкой промышленности.