Об одной задаче Open Shop с маршрутизацией на двух вершинах с единичной длительностью операций

В задаче Open Shop с маршрутизацией $n$ работ расположены в вершинах рёберно-взвешенного графа $G=(V,E),$ а $m$ машин в начальный момент времени находятся в особой вершине, называемой депо. Машины должны выполнить все работы в произвольном порядке так, чтобы в каждый момент времени каждая машина выполняла не более одной работы и каждая работа выполнялась не более чем одной машиной. Требуется минимизировать длину расписания, т. е. время возвращения последней машины в депо. Известно, что эта задача NP-трудна, даже если граф содержит всего две вершины и число машин равно двум. В этой работе рассматривается частный случай данной задачи на двухвершинном графе, где длительности всех операций, а также перемещения между вершинами равны $1$. Выдвигается гипотеза, что данная задача полиномиально разрешима, т. е. длина расписания зависит только от распределения работ по вершинам графа и может быть найдена за время $O(\log mn).$ Строятся новые оценки на длину расписания в зависимости от распределения работ в случае $m=n.$ Табл. 2, библиогр. 15.