Алгоритм с оценками для пропорционального случая двухпроцессорной задачи теории расписаний типа flow shop c минимальными задержками

Рассматривается двухпроцессорная задача типа flow shop с минимальными задержками. Известно, что эта задача NP-трудна в сильном смысле даже в случае единичных длительностей операций и может быть решена за полиномиальное время с точностью 2 в общем случае. В ряде работ ставился вопрос о существовании полиномиального алгоритма с лучшей оценкой точности, но он до сих пор остаётся открытым. В этой статье предлагается полиномиальный алгоритм с оценкой точности $\frac32$ для частного случая задачи, в котором обе операции каждой работы имеют равные длительности (этот случай задач типа flow shop в литературе обычно принято называть пропорциональным). Анализ алгоритма основан на нетривиальном обобщении нижней границы, установленной в работе В. Ю для случая единичных длительностей операций. Библ. 13.