Улучшенный алгоритм решения двухмашинной задачи flow shop

Для задачи flow shop с двумя машинами и неодновременным поступлением работ представлен алгоритм трудоемкости $O(n^3\log n)$ для нахождения приближенного решения с относительной погрешностью (т. е. отношением длины полученного расписания к длине оптимального расписания), не превосходящей 3/2. Тем самым улучшены характеристики алгоритма одного из авторов (Поттс, 1985), решающего эту задачу с относительной погрешностью 5/3 при той же оценке трудоемкости.
Ил. 2, табл. 1, библиогр. 7