Том 19, номер 3, 2012 г., Стр. 65-78

УДК 519.8
Пяткин А. В., Черных И. Д. 
Задача open shop с маршрутизацией на двухвершинной сети и разрешением прерываний

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

Ключевые слова: задача open shop с маршрутизацией, прерывание операций, NP-полнота.

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

Статья поступила 8 августа 2011 г.
Исправленный вариант — 22 ноября 2011 г.

Литература

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

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

[3] Chernykh I., Dryuck N., Kononov A., Sevastyanov S. The routing open shop problem: new approximation algorithms // Approximation and online algorithms: 7th Int. Workshop WAOA 2009 (Copenhagen, Denmark, September 10–11, 2009). Revised Papers. — Berlin: Springer-Verl., 2010. — P. 75–85. (Lect. Notes Comput. Sci.; Vol. 5893).

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

[5] Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Shmoys D. B. Sequencing and scheduling: algorithms and complexity // Logistics of production and inventory. — Amsterdam: Elsevier, 1993. — P. 445–522. (Handb. Oper. Res. Manag.; Vol. 4.)

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