Алгоритмы решения одной задачи построения расписания минимальной длины для двух машин

Рассматривается NP-трудная задача составления расписания выполнения операций единичной длительности на двух машинах при наличии частичного порядка между операциями c критерием минимизации момента завершения всех операций. Предложен приближённый алгоритм решения задачи с гарантированной оценкой точности. Доказана полиномиальная разрешимость задачи в случае, когда каждая операция, выполняющаяся на первой машине, связана отношениями предшествования ровно с двумя операциями, выполняющимися на второй машине, разработан соответствующий алгоритм. Ил. 9, библиогр. 8.