Построение сокращенного дерева вариантов для общей задачи теории расписаний

В статье рассматривается NP-полная общая задача теории расписаний: имеется конечное множество технологически связанных операций, каждая из которых должна выполняться на одной определенной машине из заданного конечного множества машин. Время выполнения операции на машине детерминировано (и задано). Задача состоит в выборе последовательности проведения операций на каждой машине с целью минимизации общего времени их выполнения. Если представить технологические связи между операциями в виде обычных дуг в графе, а зависимости операций по машинам – в виде так называемых дизъюнктивных дуг, то задачу можно свести к выбору минимального по длине критического пути ориентированного графа из всего множества допустимых графов. Строится алгоритм, позволяющий сократить это множество до подмножества, содержащего оптимальный граф. Дается сравнение построенного алгоритма с известными алгоритмами.