Том 20, номер 4, 2013 г., Стр. 3-14

УДК 519.854
Боброва Е. А., Романова А. А, Сервах В. В.
Сложность задачи построения циклических расписаний обработки однотипных деталей

Аннотация:
Исследована сложность построения оптимальных циклических расписаний в случае, когда число деталей, одновременно находящихся в обработке, не превосходит заданной величины H. Доказана NP-трудность задачи при фиксированном H ≥ 4. При H = 2 предложен алгоритм полиномиальной трудоёмкости.
Ил. 7, библиогр. 16.

Ключевые слова: однотипные детали, циклическое расписание.

Боброва Екатерина Александровна ¹
Романова Анна Анатольевна ^2,3
Сервах Владимир Вицентьевич ^1,3
1. Омский филиал ин-та математики им. С. Л. Соболева СО РАН,
ул. Певцова, 13, 644099 Омск, Россия
2. Омская юридическая академия,
ул. Короленко, 12, 644010 Омск, Россия
3. Омский гос. университет,
пр. Мира, 55a, 644077 Омск, Россия
е-mail: eabobrova88@gmail.com, anuta81@bk.ru, svv_usa@rambler.ru

Статья поступила 21 ноября 2012 г.
Исправленный вариант — 3 апреля 2013 г.

Литература

[1] Межецкая М. А. Задачи выпуска партии однотипных деталей с ограничением на число одновременно обрабатываемых деталей. - Омск: Изд-во ОмГУ, 2008. - 35 с. (Препринт)

[2] Романова А. А., Сервах В. В. Оптимизация выпуска однотипных деталей на основе циклических расписаний // Дискрет. анализ и исслед. операций. - 2008. - T. 15, № 5. - C. 47–60.

[3] Сервах В. В. О задаче Акерса - Фридмана // Управляемые системы. - 1983. - Вып. 23. - С. 70–81.

[4] Тимковский В. Г. Приближённое решение задачи составления расписания циклической системы // Экономика и мат. методы. - 1986. - T. 1. - C. 171–174.

[5] Boudoukh T., Penn M., Weiss G. Scheduling jobshops with some identical or similar jobs // J. Sched. - 2001. - Vol. 4. - P. 177–199.

[6] Brucker P. Scheduling algorithms. - Leipzig: Springer-Verl., 2007. - 371 p.

[7] Hall N. G., Lee T. E., Posner M. E. The complexity of cyclic shop scheduling problems // J. Sched. - 2002. - Vol. 5. - P. 307–327.

[8] Hanen C. Study of a NP-hard cyclic scheduling problem: the recurrent job-shop // Eur. J. Oper. Res. - 1994. - Vol. 72. - P. 82–101.

[9] Hardgrave W. W., Nemhauser G. A. Geometric model and graphical algorithm for a sequencing problem // Oper. Res. - 1963. - Vol. 11, N 6. - P. 889–900.

[10] Kamoun H., Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacturing systems // Eur. J. Oper. Res. - 1993. - Vol. 70. - P. 350–364.

[11] Levner E., Kats V., Pablo D., Cheng E. Complexity of cyclic scheduling problems: a state-of-the-art survey // Comp. Ind. Eng. - 2010. - Vol. 59, N 2. - P. 352–361.

[12] McCormick S. T., Rao U. S. Some complexity results in cyclic scheduling // Math. Comput. Modeling. - 1994. - Vol. 20. - P. 107–122.

[13] Rao U., Jackson P. Identical jobs cyclic scheduling: subproblems, properties, complexity and solution approaches. - Ithaca, NY: Cornell Univ. Press, 1993. - 48 p.

[14] Roundy R. Cyclic schedules for job shops with identical jobs // Math. Oper. Res. - 1992. - Vol. 17, N 4. - P. 842–865.

[15] Sotskov Y. N., Shakhlevich N. V. NP-hardness of shop-scheduling problems with three jobs // Discrete Appl. Math. - 1995. - Vol. 59, N 3. - P. 237–266.

[16] Timkovsky V. G. Cyclic shop scheduling. Handbook of scheduling: algorithms, models, and performance analysis. - Boca Raton: Chapman & Hall/CRC, 2004. - P. 7.1–7.22.