О точном алгоритме составления оптимального циклического расписания многооператорного обслуживания поточной линии

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