Том 19, номер 2, 2012 г., Стр. 55-75

УДК 519.95
Кононов А. В. 
О цеховой задаче открытого типа на двух машинах с маршрутизацией в двухвершинной сети

Аннотация:
Рассматривается цеховая задача открытого типа для двух машин с маршрутизацией в двухвершинной сети. Задача является NP-трудной. Для ее решения предлагаются точный псевдополиномиальный алгоритм и вполне полиномиальная приближенная схема и выделяются полиномиально разрешимые случаи.
Ил. 6, табл. 1, библиогр. 8.

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

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

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

Литература

[1] Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. — М.: Наука, 1989. — 329 с.

[2] 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.

[3] 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. 521–539.

[4] 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. — Heidelberg: Springer-Verl., 2010. — P. 75–85. (Lect. Notes Comp. Sci.; Vol. 5893.)

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

[6] Ibarra O., Kim C. E. Fast approximation algorithms for the knapsack and sum of subset problems // J. ACM. — 1975. — Vol. 22. — P. 463–468.

[7] Johnson S. M. Optimal two- and three stage production schedules with setup times included // Naval Res. Logistic Quaterly. — 1954. — Vol. 1. — P. 61–68.

[8] Schuurman P., Woeginger G. Approximation schemes — a tutorial //
http://www.win.tue.nl/ gwoegi/papers/ptas.pdf