На предприятиях периодически приходится решать задачу распределения технологических операций по рабочим местам поточно-конвейерной системы.Пусть для изготовления изделия требуется выполнить совокупность технологических операций (ТО) n типов. Известно, что время выполнения ТО каждого типа t1, t2, t3, …, tn и соответственно их количества w1, w2, …, wn. Считается, что ТО одного типа имеют одинаковые времена выполнения. Кроме того, указаны условия предшествования ТО, вытекающие из технологического процесса изготовления изделия, т.е. условия вида «ТО типа j должны быть выполнены прежде, чем начнется выполнение ТО типа k». Кратко условия предшествования записываются j ≺ k (≺ — знак предшествования), а всю совокупность этих условий изображают в виде некоторого ориентированного графа, называемого далее диаграммой предшествования (рис. 1), в котором каждому отношению j ≺ k соответствует дуга, ведущая от вершины j к вершине k.Наконец, пусть задано m последовательно расположенных на ПКС рабочих мест. Требуется распределить ТО между m рабочими местами, чтобы:• удовлетворять условия предшествования (см. рис. 1);• общее время выполнения ТО на i-м рабочем месте не превышало времени Т;• время Т было минимальным.