Том 24, номер 1, 2017 г., Стр. 5-20

УДК 519.8
Боброва Е. А., Сервах В. В.
Построение циклических расписаний при наличии параллельных машин

Аннотация:
Рассматривается задача обработки партии идентичных деталей со сложным технологическим маршрутом при наличии параллельных машин. Требуется построить циклическое расписание с минимальной длиной цикла при ограничении на максимальное число одновременно обрабатываемых деталей. Предложен и обоснован алгоритм построения точного решения, выделен псевдополиномиально разрешимый случай задачи.
Ил. 4, библиогр. 16.

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

DOI: 10.17377/daio.2017.24.500

Боброва Екатерина Александровна ¹
Сервах Владимир Вицентьевич ¹
1. Институт математики им С. Л. Соболева СО РАН, Омский филиал,
ул. Певцова, 13, 644043 Омск, Россия
е-mail: eabobrova88@gmail.com, svv_usa@rambler.ru

Статья поступила 3 июля 2015 г.
Исправленный вариант — 30 августа 2016 г.

Литература

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

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

[3] Сервах В. В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискрет. анализ и исслед. операций. Сер. 2. 2000. T. 7, № 1. С. 75–82.

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

[5] Boudoukh T., Penn M., Weiss G. Job-shop — an application of fluid approximation // Proc. 10th Conf. Ind. Eng. Management (Haifa, Israel, June 10–12, 1998). Haifa, Israel: Isr. Inst. Technol., 1998. P. 254–258.

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

[7] Brucker P. Scheduling algorithms. Berlin; Heidelberg; New York: Springer-Verl., 2007. 371 p.

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

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

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

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

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

[13] Rao U. S., Jackson P. L. Subproblems in identical jobs cyclic scheduling: properties, complexity, and solution approaches. Tech. Rep. Ithaca, NY: Cornell Univ. Press, 1993. 47 p.

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

[15] Servakh V. V. A dynamic algorithm for some project management problems // Proc. Int. Workshop Discrete Optimization Methods in Scheduling and Computer-Aided Design (Minsk, Sept. 5–6, 2000). Minsk: Inst. Eng. Cybern. NAS Belarus, 2000. P. 90–92.

[16] Timkovsky V. G. Cycle shop scheduling // Handbook of scheduling: algorithms, models, and performance analysis (J. Y.-T. Leung, ed.). London: Chapman & Hall/CRC, 2004. P. 127–148.