The problem of minimizing the total processing time of identical parts with a complex technological route is considered, when parts can be repeatedly supplied to some machines. The issues of computational complexity of this problem are investigated, and its NP-hardness in the usual sense is proven. For a fixed number of parts, the pseudopolynomial solvability of the problem is proved. The issue of using cyclic schedules in constructing approximate solutions is investigated.
Download file
Counter downloads: 7
- Title Makespan minimization in reentrant flow shop problem with identical jobs
- Headline Makespan minimization in reentrant flow shop problem with identical jobs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 64
- Date:
- DOI 10.17223/20710410/64/8
Keywords
schedule, identical jobs, NP-hardness, pseudopolynomial algorithm, theory of NP-completenessAuthors
References
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.
Makespan minimization in reentrant flow shop problem with identical jobs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/8
Download full-text version
Counter downloads: 140