Том 26, номер 4, 2019 г., Стр. 56-73

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

Аннотация:
Рассматривается задача построения циклического расписания обработки идентичных деталей с минимальным временем цикла при наличии запретов на простой между некоторыми парами последовательно выполняемых операций. Исследована сложность задачи и ряда её частных случаев. Доказано, что в общем случае задача является NP-трудной в сильном смысле. Выделены эффективно разрешимые случаи и описаны соответствующие алгоритмы. В случае обработки детали без простоев между операциями доказана полиномиальная разрешимость задачи и предложено два полиномиальных алгоритма. Разработан алгоритм решения задачи в общем случае, который является псевдополиномиальным, если число пар последовательных операций, между которыми разрешены простои, ограничено константой. С другой стороны, показано, что в случае одного запрета задача полиномиально разрешима, а при двух запретах уже NP-трудна.
Ил. 4, библиогр. 14.

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

DOI: 10.33048/daio.2019.26.629

Романова Анна Анатольевна ¹
Сервах Владимир Вицентьевич ²
1. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55а, 644077 Омск, Россия
2. Омский филиал Института математики им. С. Л. Соболева,
ул. Певцова, 13, 644099 Омск, Россия
е-mail: anna.a.r@bk.ru, svv_usa@rambler.ru

Статья поступила 27 августа 2018 г.
После доработки — 29 июля 2019 г.
Принята к публикации 28 августа 2019 г.

Литература

[1] Боброва Е. А., Романова А. А., Сервах В. В. Сложность задачи построения циклических расписаний обработки однотипных деталей // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 4. C. 3–14.

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

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

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

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

[6] Middendorf M., Timkovsky V. On scheduling cycle shops: classification, complexity and approximation // J. Sched. 2002. Vol. 5. P. 135–169.

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

[8] Aldakhilallah K. A., Ramesh R. Cyclic scheduling heuristics for a reentrant job shop manufacturing environment // Int. J. Prod. Res. 2001. Vol. 39. P. 2635–2675.

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

[10] Brucker P., Kampmeyer T. Tabu search algorithms for cyclic machine scheduling problems // J. Sched. 2005. Vol. 8. P. 303–322.

[11] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

[12] Kats V., Levner E. Cyclic scheduling in a robotic production line // J. Sched. 2002. Vol. 5. P. 23–41.

[13] Айзенштат B. C. Многооператорные циклические процессы // Докл. АН БССР. 1963. T. VII, № 4. C. 224–227.

[14] Танаев В. С. К задаче составления расписания работы поточной линии с одним автооператором // Инж.-физ. журн. 1964. T. 7, № 3. С. 111–114.