Makespan minimization in reentrant flow shop problem with identical jobs

A. A. Romanova ; V. V. Servakh ; V. Yu. Tavchenko

Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 99-111.

Résumé

We consider the reentrant flow shop problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$ with identical jobs and makespan criterion. We prove its NP-hardness in the ordinary sense. The proof is performed by polynomial reduction of the problem $J3|n =3|C_{\max}$ to the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$ with three identical jobs. Using the input data of the problem $J3|n=3|C_{\max}$, we have constructed a special type of job for the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$. In the proof, we analyze all possible variants of critical paths in the constructed instance. We also propose a dynamic programming algorithm to find the optimal solution of the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$. Analysis of the time complexity of the algorithm showed that the problem with fixed number of jobs is pseudopolynomially solvable. Next, we study the use of cyclic schedules to construct approximate solutions. A cyclic schedule with a minimum cycle time can be found in polynomial time. We propose a polynomial algorithm for finding an approximate solution. This algorithm is based on the construction of a cyclic schedule with a minimum cycle time and its subsequent compaction at the beginning and at the end. We construct an upper bound of the makespan of cyclic schedules. This bound depends on the number of jobs processed in one cycle. The paper provides numerous examples characterizing cyclic schedules from both the positive and negative sides to solve the problem $F|\text{reentrant}$, $p_{ij} = p_i|C_{\max}$.

Détail

Keywords: schedule, identical jobs, NP-hardness, theory of NP-completeness.
Mots-clés : pseudopolynomial algorithm

Bibliographie

[1] Pinedo M. L., Scheduling. Theory, Algorithms, and Systems, Springer, 2008, 671 pp. | MR | Zbl

[2] Graves S. C., Meal H. M., Stefek D., and Zeghmi A. H., “Scheduling of re-entrant flow shops”, J. Oper. Management, 3:4 (1983), 197–207 | DOI

[3] Emmons H. and Vairaktarakis G., Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications, Springer Science Business Media, 2012, 334 pp. | MR

[4] Shufan E., Grinshpoun T., Ikar E., and Ilani H., “Reentrant flow shop with identical jobs and makespan criterion”, J. Production Res., 61:1 (2021), 183–197 | DOI

[5] Lev V. and Adiri I., “V-shop scheduling”, Europ. J. Oper. Res., 18:1 (1984), 51–56 | DOI | MR | Zbl

[6] Pan J. C.-H. and Chen J.-S., “Minimizing makespan in re-entrant permutation flow-shops”, J. Oper. Res. Soc., 54:6 (2003), 642–653 | DOI | Zbl

[7] Chen J.-S., “A branch and bound procedure for the reentrant permutation flowshop scheduling problem”, Intern. J. Adv. Manufacturing Technology, 29 (2006), 1186–1193 | DOI

[8] Wang M. Y., Suresh P. S., and van de Velde S. L., “Minimizing makespan in a class of reentrant shops”, Oper. Res., 45:5 (1997), 702–712 | DOI | Zbl

[9] Kubiak W., Lou Sh. X. C., and Wang Y., “Mean flow time minimization in reentrant job shops with a hub”, Oper. Res., 44:5 (1996), 743–753 | DOI

[10] Xie X., Tang L., and Li Y., “Scheduling of a hub reentrant job shop to minimize makespan”, Intern. J. Adv. Manufacturing Technology, 56 (2011), 743–753 | DOI

[11] Middendorf M. and Timkovsky V. G., “On scheduling cycle shops: Classification, complexity and approximation”, J. Scheduling, 5:2 (2002), 135–169 | DOI | MR | Zbl

[12] Timkovsky V. G., “Cycle Shop Scheduling”, Handbook of Scheduling, Ch. 7, ed. Leung J. Y.-T., CRC Press, Boca Raton–London–N.Y.–Washington, 2004 | MR

[13] Yu T.-S. and Pinedo M. L., “Flow shops with reentry: Reversibility properties and makespan optimal schedules”, Europ. J. Oper. Res., 282:2 (2021), 478–490 | MR

[14] Kats V. and Levner E., “Minimizing the number of robots to meet a given cyclic schedule”, Ann. Oper. Res., 69 (1997), 209–226 | DOI | MR | Zbl

[15] Kats V. and Levner E., “Cyclic scheduling in a robotic production line”, J. Scheduling, 5:1 (2002), 23–41 | DOI | MR | Zbl

[16] Boudoukh T., Penn M., and Weiss G., “Scheduling jobshops with some identical or similar jobs”, J. Scheduling, 4:4 (2001), 177–199 | DOI | MR | Zbl

[17] Mezhetskaya M. A. and Servakh V. V., “The shop scheduling problems with complex technological route”, Sovremennye Problemy Nauki i Obrazovaniya, 2013, no. 1 (in Russian) https://science-education.ru/ru/article/view?id=8407

[18] Sotskov Y. N. and Shakhlevich N. V., “NP-hardness of shop-scheduling problems with three jobs”, Discrete Appl. Math., 59:3 (1995), 237–266 | DOI | MR | Zbl

[19] Servakh V. V. and Shcherbinina T. A., “A fully polynomial time approximation scheme for two project scheduling problems”, IFAC Proc. Volumes, 39:3 (2006), 131–135 | DOI

[20] Servakh V. V., “An efficiently solvable case of the scheduling problem with renewable resources”, Diskretnyy Analiz i Issledovaniye Operatsiy, Ser. 2, 7:1 (2000), 75–82 (in Russian) | MR | Zbl

[21] Middendorf M. and Timkovsky V. G., “Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems”, J. Combin. Optimization, 3:4 (1999), 417–435 | DOI | MR | Zbl

[22] Romanova A. A. and Servakh V. V., “Optimization of identical jobs production on the base of cyclic schedules”, J. Appl. Industr. Math., 3:4 (2009), 496–504 | DOI | MR

[23] Bobrova E. A., Romanova A. A., and Servakh V. V., “Complexity of cyclic scheduling for identical jobs”, Diskretnyy Analiz i Issledovaniye Operatsiy, 20:4 (2013), 3–14 (in Russian) | MR | Zbl