Algorithms for four-machine flowshop scheduling problem with uncertain processing times to minimize makespan

Allahverdi, Muberra; Allahverdi, Ali

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 529-553.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

We consider the four-machine flowshop scheduling problem to minimize makespan where processing times are uncertain. The processing times are within some intervals, where the only available information is the lower and upper bounds of job processing times. Some dominance relations are developed, and twelve algorithms are proposed. The proposed algorithms first convert the four-machine problem into two stages, then, use the well-known Johnson’s algorithm, known to yield the optimal solution for the two-stage problem. The algorithms also use the developed dominance relations. The proposed algorithms are extensively evaluated through randomly generated data for different numbers of jobs and different gaps between the lower and upper bounds of processing times. Computational experiments indicate that the proposed algorithms perform well. Moreover, the computational experiments reveal that one of the proposed algorithms, Algorithm A7, performs significantly better than the other eleven algorithms for all possible combinations of the number of jobs and the gaps between the lower and upper bounds. More specifically, error percentages of the other eleven algorithms range from 2.3 to 27.7 times that of Algorithm A7. The results have been confirmed by constructing 99% confidence intervals and tests of hypotheses using a significance level of 0.01.

Classification : 20-XX
Mots-clés : Flowshop scheduling, makespan, uncertain processing times, algorithm

[1] A. Allahverdi, The tricriteria two-machine flowshop scheduling problem. Int. Trans. Oper. Res. 8 (2001) 403–425. | DOI | MR | Zbl

[2] A. Allahverdi, A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. Comput. Oper. Res. 31 (2004) 157–180. | DOI | MR | Zbl

[3] A. Allahverdi and M. Allahverdi, Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness. Comput. Appl. Math. 37 (2018) 6774–6794. | DOI | MR | Zbl

[4] M. Allahverdi and A. Allahverdi, Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times. J. Ind. Manage. Optim. 13 (2019) 1. | MR | Zbl

[5] A. Allahverdi and H. Aydilek. Heuristics for two-machine flowshop scheduling problem to minimize makespan with bounded processing times, Int. J. Prod. Res. 48 (2010) 6367–6385. | DOI

[6] A. Allahverdi and H. Aydilek. Heuristics for two-machine flowshop scheduling problem to minimize maximum lateness with bounded processing times, Comput. Math. Appl. 60 (2010) 1374–1384. | DOI | MR | Zbl

[7] A. Allahverdi and Y.N. Sotskov, Two-machine flowshop minimum length scheduling problem with random and bounded processing times. Int. Trans. Oper. Res. 10 (2003) 65–76. | DOI | MR | Zbl

[8] H. Aydilek and A. Allahverdi, Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time. Comput. Math. Appl. 59 (2010) 684–693. | DOI | Zbl

[9] A. Aydilek, H. Aydilek and A. Allahverdi, Increasing the profitability and competitiveness in a production environment with random and bounded setup times. Int. J. Prod. Res. 51 (2013) 106–117. | DOI

[10] A. Aydilek, H. Aydilek and A. Allahverdi, Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan. Int. J. Prod. Res. 53 (2015) 2803–2819. | DOI

[11] A. Aydilek, H. Aydilek and A. Allahverdi, Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times. Appl. Math. Model. 45 (2017) 982–996. | DOI | MR

[12] B. Dumaine, How managers can succeed through speed. Fortune 12 (1989) 54–59.

[13] H.Y. Fuchigami and S. Rangel, A survey of case studies in production scheduling: analysis and perspectives. J. Comput. Sci. 25 (2018) 425–436. | DOI

[14] M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1 (1976) 117–129. | DOI | MR

[15] E.M. Gonzalez-Neira, D. Ferone, S. Hatami and A.A. Juan, A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simul. Model. Pract. Theory 79 (2017) 23–36. | DOI

[16] T. Keshavarz and N. Salmasi, Makespan minimization in flexible flowshop sequence-dependent group scheduling problem. Int. J. Prod. Res. 51 (2013) 6182–6193. | DOI

[17] P. Kouvelis and G. Yu, Robust Discrete Optimization and its Applications. Kluwer Academic Publisher (1997). | DOI | MR | Zbl

[18] M. Pinedo, Scheduling Theory, Algorithms, and Systems. Prentice Hall, Englewood Cliffs, NJ (2016). | Zbl

[19] H. Seidgar, M. Kiani, M. Abedi, H. Fazlollahtabar, An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem. Int. J. Prod. Res. 52 (2014) 1240–1256. | DOI

[20] Y.N. Sotskov, A. Allahverdi and T.C. Lai, Flowshop scheduling problem to minimize total completion time with random and bounded processing times. J. Oper. Res. Soc. 55 (2004) 277–286. | DOI | Zbl

[21] H. Stefansson, S. Sigmarsdottir, P. Jensson and N. Shah, Discrete and continuous time representations and mathematical models for large productions scheduling problems: a case study from the pharmaceutical industry. Eur. J. Oper. Res. 215 (2011) 383–392. | DOI | MR | Zbl

[22] P. Tayanithi, S. Manivannan and J. Banks, A knowledge-based simulation architecture to analyze interruptions in a flexible manufacturing system. J. Manuf. Syst. 11 (1992) 195–214. | DOI

[23] K. Wang and S.H. Choi, A decomposition-based approach to flexible flow shop scheduling under machine breakdown. Int. J. Prod. Res. 50 (2012) 215–234. | DOI