Полиномиально разрешимый случай двухстадийной задачи $open shop$ с тремя машинами

Рассматривается двухстадийная задача open shop на трех машинах с критерием “минимум длины расписания”. Вопрос о сложности этой задачи, поставленный Гонзалезом и Са́ни в 1976 г., до сих пор остается открытым. В статье доказывается, что задача полиномиально разрешима при $L_{\max}\geqslant 3p_{\max}$, где $L_{\max}$ –максимальная машинная нагрузка, $p_{\max}$ – максимальная длительность операции. При этом длина оптимального расписания равняется $L_{\max}$. Библиогр. 7.