Задача open shop с маршрутизацией на двухвершинной сети и разрешением прерываний

Задача open shop с разрешением прерываний и маршрутизацией является обобщением двух классических задач дискретной оптимизации: NP-трудной метрической задачи коммивояжёра и полиномиально разрешимой задачи теории расписаний open shop с разрешением прерываний. В статье рассматривается частный случай этой задачи, в котором транспортная сеть состоит из двух вершин. Показано, что задача с двумя машинами полиномиально разрешима, а для случая нефиксированного числа машин задача NP-трудна в сильном смысле. Ил. 6, библиогр. 6.