ГлавнаяАрхивЗадача минимизации общего времени обработки идентичных деталей

Задача минимизации общего времени обработки идентичных деталей | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/8

Рассматривается задача минимизации общего времени обработки идентичных деталей со сложным технологическим маршрутом, когда возможно неоднократное поступление деталей на некоторые машины. Исследуются вопросы вычислительной сложности данной задачи, доказана её NP-трудность в обычном смысле. При фиксированном числе деталей доказана псевдополиномиальная разрешимость задачи. Исследуется вопрос использования циклических расписаний при построении приближённых решений.
  • Title Задача минимизации общего времени обработки идентичных деталей
  • Headline Задача минимизации общего времени обработки идентичных деталей
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 64
  • Date:
  • DOI 10.17223/20710410/64/8
Ключевые слова
расписание, идентичные детали, NP-трудность, псевдополиномиальный алгоритм, теория сложности
Авторы
Ссылки
Pinedo M. L. Scheduling. Theory, Algorithms, and Systems. Springer, 2008. 671 p.
Graves S. C., Meal H. M., Stefek D., and Zeghmi A. H. Scheduling of re-entrant flow shops //J. Oper. Management. 1983. V. 3. No. 4. P. 197-207.
Emmons H. and Vairaktarakis G. Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications. Springer Science & Business Media, 2012. 334 p.
Shufan E., Grinshpoun T., Ikar E., and Ilani H. Reentrant flow shop with identical jobs and makespan criterion // J. Production Res. 2021. V. 61. No. 1. P. 183-197.
Lev V. and Adiri I. V-shop scheduling // Europ. J. Oper. Res. 1984. V. 18. No. 1. P. 51-56.
Pan J. C.-H. and Chen J.-S. Minimizing makespan in re-entrant permutation flow-shops // J. Oper. Res. Soc. 2003. V. 54. No. 6. P. 642-653.
Chen J.-S. A branch and bound procedure for the reentrant permutation flowshop scheduling problem // Intern. J. Adv. Manufacturing Technology. 2006. V. 29. P. 1186-1193.
Wang M. Y., Suresh P. S., and van de Velde S. L. Minimizing makespan in a class of reentrant shops // Oper. Res. 1997. V. 45. No. 5. P. 702-712.
Kubiak W., Lou Sh. X. C., and Wang Y. Mean ow time minimization in reentrant job shops with a hub // Oper. Res. 1996. V. 44. No. 5. P. 743-753.
Xie X., Tang L., and Li Y. Scheduling of a hub reentrant job shop to minimize makespan // Intern. J. Adv. Manufacturing Technology. 2011. V. 56. P. 743-753.
Middendorf M. and Timkovsky V. G. On scheduling cycle shops: Classi cation, complexity and approximation // J. Scheduling. 2002. V. 5(2). P. 135-169.
Timkovsky V. G. Cycle Shop Scheduling / Leung J.Y.-T. (ed.). Handbook of Scheduling. Ch. 7. Boca Raton; London; N.Y.; Washington, CRC Press, 2004.
Yu T.-S. and Pinedo M. L. Flow shops with reentry: Reversibility properties and makespan optimal schedules // Europ. J. Oper. Res. 2021. V. 282(2). P. 478-490.
Kats V. and Levner E. Minimizing the number of robots to meet a given cyclic schedule // Ann. Oper. Res. 1997. V. 69. P. 209-226.
Kats V. and Levner E. Cyclic scheduling in a robotic production line // J. Scheduling. 2002. V. 5(1). P. 23-41.
Boudoukh T., Penn M., and Weiss G. Scheduling jobshops with some identical or similar jobs // J. Scheduling. 2001. V. 4(4). P. 177-199.
Межецкая M. A., Cepвax B.B. Задачи обработки деталей со сложным технологическим маршрутом // Современные проблемы науки и образования. 2013. №1. https://science-education.ru/ru/article/view?id=8407.
Sotskov Y. N. and Shakhlevich N. V. NP-hardness of shop-scheduling problems with three jobs // Discrete Appl. Math. 1995. V.59(3). P.237-266.
Servakh V. V. and Shcherbinina T. A. A fully polynomial time approximation scheme for two project scheduling problems // IFAC Proc. Volumes. 2006. V. 39. Iss.3. P.131-135.
Сервах В. В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретн. анализ исслед. опер. Сер. 2. 2000. Т. 7. №1. С.75-82.
Middendorf М. and Timkovsky V. G. Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems //j.Combin. Optimization. 1999. V. 3. No.4. P.417-435.
Romanova A. A. and Servakh V. V. Optimization of identical jobs production on the base of cyclic schedules //j. Appl. Industr. Math. 2009. V.3. No.4. P.496-504.
Боброва E. А., Романова А. А., Сервах В. В. Сложности задачи построения циклических расписаний обработки однотипных деталей // Дискретн. анализ исслед. опер. 2013. Т. 20. №4. С. 3-14.
Задача минимизации общего времени обработки идентичных деталей | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/8
Задача минимизации общего времени обработки идентичных деталей | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/8