An Improved Algorithm for Minimizing Makespan on Flowshops with Uncertain Processing Times

Year 2021, Volume: 13 Issue: 2, 521 - 530, 18.06.2021

Ali Allahverdi , Muberra Allahverdi

https://doi.org/10.29137/umagd.887624

Abstract

We address the four-machine flowshop scheduling problem with the objective of minimizing makespan with uncertain processing times The problem was addressed in the literature (RAIRO Operations Research 54, 529-553) and different algorithms were proposed. In this paper, we propose a new algorithm for the problem. The new proposed algorithm is compared with the best algorithm in the literature by using extensive computational experiments. Computational experiments indicate that the new proposed algorithm performs much better than the best algorithm in the literature in terms of error while both have the same computational time. Specifically, the new proposed algorithm reduces the error of the best existing algorithm in the literature over 40%. This result has been confirmed by using tests of hypotheses with a significance level of 0.01.

Keywords

Makespan, Scheduling, Algorithm, Uncertainty

References

• Allahverdi, A., 2001. The tricriteria two-machine flowshop scheduling problem. International Transactions in Operational Research 8, 403-425.
• Allahverdi, A., 2004. A new heuristic for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness. Computers & Operations Research 31, 157-180.
• Allahverdi, A., Allahverdi, M., 2018. Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness. Computational and Applied Mathematics 37, 6774-679.
• Allahverdi, M., Allahverdi, A., 2020. Algorithms for Four-machine flowshop scheduling problem with uncertain processing times to minimize makespan. RAIRO Operations Research 54, 529-553.
• Allahverdi, A., Aydilek, H., 2010a. Heuristics for two-machine flowshop scheduling problem to minimize makespan with bounded processing times. International Journal of Production Research 48, 6367- 6385.
• Allahverdi, A., and Aydilek, H., 2010b. Heuristics for two-machine flowshop scheduling problem to minimize maximum lateness with bounded processing times. Computers and Mathematics with Applications 60, 1374-1384.
• Allahverdi, A., and Sotskov, Y.N., 2003. Two-machine flowshop minimum length scheduling problem with random and bounded processing times. International Transactions in Operational Research 10, 65-76.
• Aydilek, H., and Allahverdi, A., 2010. Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time. Computers and Mathematics with Applications 59, 684-693.
• Aydilek, A., Aydilek, H., Allahverdi, A., 2013. Increasing the profitability and competitiveness in a production environment with random and bounded setup times. International Journal of Production Research 51, 106- 117.
• Aydilek, A., Aydilek, H., Allahverdi, A., 2015. Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan. International Journal of Production Research 53, 2803-2819.
• Aydilek, A., Aydilek, H., Allahverdi, A., 2017. Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times. Applied Mathematical Modelling 45, 982-996.
• Dumaine, B., 1989. How managers can succeed through speed. Fortune 12, 54-59.
• Fuchigami, H.Y., Rangel, S., 2018. A survey of case studies in production scheduling: Analysis and perspectives. Journal of Computational Science 25, 425-436.
• Garey, M.R., Johnson, D.S., Sethi, R., 1976. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1, 117-129.
• Gonzalez-Neira, E.M., Ferone, D., Hatami, S., Juan, A.A. 2017. A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simulation Modelling Practice and Theory 79, 23-36.
• Kouvelis, P., Yu, G. 1997. Robust Discrete Optimization and its Applications, Kluwer Academic Publisher.
• Mahjoub, A., Sanchez, J. E. P. 2011. Trystram, D. Scheduling with uncertainties on new computing platforms. Computational Optimization and Applications 48, 369-398.
• Sotskov, Y.N., Allahverdi, A., Lai, T.C., 2004. Flowshop scheduling problem to minimize total completion time with random and bounded processing times. Journal of Operational Research Society 55, 277-286.
• Stefansson, H., Sigmarsdottir, S., Jensson, P., Shah, N., 2011. Discrete and continuous time representations and mathematical models for large productions scheduling problems: a case study from the pharmaceutical industry. European Journal of Operational Research 215, 383-392.