Том 27, номер 3, 2020 г., Стр. 71-87

УДК 519.854.2
Головачёв М. О., Пяткин А. В.
Об одной задаче Open Shop с маршрутизацией на двух вершинах с единичной длительностью
операций

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

Ключевые слова: задача Open Shop с маршрутизацией, операция единичной длительности, сложность, расписание, полиномиальное время, оценка длины расписания.

DOI: 10.33048/daio.2020.27.681

Головачёв Михаил Олегович ¹
Пяткин Артём Валерьевич ^2,1
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: mik-golovachev2@mail.ru, artem@math.nsc.ru

Статья поступила 10 января 2020 г.
После доработки — 20 апреля 2020 г.
Принята к публикации 25 мая 2020 г.

Литература

[1] Gonzalez T., Sahni S. Open shop scheduling to minimize finish time // J. ACM. 1976. Vol. 23, No. 4. P. 665–679.

[2] Williamson D. P., Hall L. A., Hoogeveen J. A., Hurkens C. A. J., Lenstra J. K., Sevast’janov S. V., Shmoys D. B. Short shop schedules // Oper. Res. 1997. Vol. 45. P. 288–294.

[3] Cole R., Ost K., Schirra S. Edge-coloring bipartite multigraphs in $O$($E \times$ log $D$) time // Combinatorica. 2001. Vol. 21, No. 1. P. 5–12.

[4] Averbakh I., Berman O., Chernykh I. A 6/5-approximation algorithm for the two-machine routing open shop problem on a 2-node network // Eur. J. Oper. Res. 2005. Vol. 166, No. 1. P. 3–24.

[5] Averbakh I., Berman O., Chernykh I. The routing open-shop problem on a network: Complexity and approximation // Eur. J. Oper. Res. 2006. Vol. 173, No. 2. P. 521–539.

[6] Кононов А. В. О цеховой задаче открытого типа на двух машинах с маршрутизацией в двухвершинной сети // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 2. С. 54–74.

[7] Пяткин А. В., Чёрных И. Д. Задача Open Shop с маршрутизацией на двухвершинной сети и разрешением прерываний // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 3. С. 65–78.

[8] Van Bevern R., Pyatkin A. V. Completing partial schedules for open shop with unit processing times and routing // Computer Science – Theory and Applications. Proc. 11th Int. Computer Science Symp. in Russia (St. Petersburg, Russia, June 9–13, 2016). Cham: Springer, 2016. P. 73–87. (Lect. Notes Comput. Sci.; Vol. 9691).

[9] Van Bevern R., Pyatkin A. V., Sevastyanov S. V. An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times // Сиб. электрон. мат. изв. 2019. Т. 16. С. 42–84.

[10] Brucker P., Knust S., Cheng T. C. E., Shakhlevich N. V. Complexity results for flow-shop and open-shop scheduling problems with transportation delays // Ann. Oper. Res. 2004. Vol. 129. P. 81–106.

[11] Lushchakova I., Soper A., Strusevich V. Transporting jobs through a two-machine open shop // Naval Res. Logistics. 2009. Vol. 56. P. 1–18.

[12] Strusevich V. A heuristic for the two-machine open-shop scheduling problem with transportation times // Discrete Appl. Math. 1999. Vol. 93, No. 2. P. 287–304.

[13] Golovachev M. O., Pyatkin A. V. Routing Open Shop with two nodes, unit processing times and equal number of jobs and machines // Mathematical Op?timization Theory and Operations Research. Proc. 18th Int. Conf. (Ekaterin?burg, Russia, July 8–12, 2019). Cham: Springer, 2019. P. 264–276. (Lect. Notes Comput. Sci.; Vol. 11548).

[14] Bräsel H., Kluge D., Werner F. A polynomial algorithm for the [$n/m/0$, $t_{ij} = 1, tree/C_{max}$] open shop problem // Eur. J. Oper. Res. 1994. Vol. 72, No. 1. P. 125–134.

[15] Diestel R. Graph theory. Heidelberg: Springer, 2016.