Оптимальное планирование работ в конвейерных системах

Дается обзор известных постановок и методов решения классической задачи теории расписаний по упорядочению работ во времени в системах конвейерного типа (задача Беллмана–Джонсона). Приводится классификация применяемых методов оптимизации. Описываются комбинаторный подход к решению задачи, перестановочный прием, алгебраический подход, приемы, основанные на изучении критических путей в матрице времен выполнения работ в системе, методы, использующие специфику матрицы времен, методы, основанные на использовании бесконечнозначной логики. Даются сведения о применении к решению задачи теории расписаний по упорядочению работ в конвейерных системах методов ветвей и границ, статистического моделирования, математического программирования. Сравнивается предпочтительность того или иного метода.