A Substantially Improved New Algorithm for Flowshop Scheduling Problem with Uncertain Processing Times

Year 2022, Volume: 14 Issue: 1, 155 - 163, 31.01.2022

Muberra Allahverdi

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

Abstract

The performance measure of total completion time (TCT) plays a key role in manufacturing to improve performance, e.g., reducing inventory levels. Moreover, since uncertainty is an inevitable part of certain manufacturing environments, it is especially important to address cases with uncertain processing times. This paper addresses the four-machine flowshop scheduling problem to minimize TCT with uncertain processing times. Due to the NP-hardness of the problem, different algorithms were presented as solutions in scheduling literature. In this paper, a new substantially improved algorithm is proposed and parameters of the algorithm are fine tuned. The proposed algorithm is compared to the best existing algorithm (RAIRO Operations Research 54, 529–553, 2020) in scheduling literature using extensive computational experiments and statistical analysis. Computational methods using the programming language python, along with statistical inference, is used to confirm the effectiveness of the proposed algorithm over the existing ones. Computational methods reveal that the proposed algorithm is, on average, 86.8% more effective than the best existing one in literature with similar computational times. A test of hypothesis further confirms the effectiveness of the proposed algorithm with a p-value of less than 0.00001, which is practically zero.

Keywords

Algorithm, uncertain processing times, flowshop scheduling, total completion time

References

• Allahverdi, A. 2015. The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research 246, 345–378.
• 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., 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., Aydilek, H. 2010c. Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time. Computers and Mathematics with Applications 59, 684–693.
• Allahverdi, A., 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, A. Aydilek, H., Allahverdi, A. 2013. Increasing the profitability and competitivess in a production environment with random and bounded setup times. Int. 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. Int. 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.
• Chen, J.F. 2015. Unrelated parallel-machine scheduling to minimize total weighted completion time. Journal of Intelligent Manufacturing 26, 1099–1112.
• Costa, M.R.C., Valente, J.M.S., Schaller, J.E. 2020. Efficient procedures for the weighted squared tardiness permutation flowshop scheduling problem. Flexible Services and Manufacturing Journal 32, 487-522.
• Framinan, J.M., Perez-Gonzalez, P. 2017a. The 2-stage assembly flowshop scheduling problem with total completion time: Efficient constructive heuristic and metaheuristic. Computers and Operations Research 88, 237–246.
• Framinan, J.M., Perez-Gonzalez, P. 2017b. New approximate algorithms for the customer order scheduling problem with total completion time objective. Computers and Operations Research 78, 181–192.
• Ha, C. 2020. Evolving ant colony system for large-sized integrated process planning and scheduling problem considering sequence-dependent setup times. Flexible Services and Manufacturing Journal 32, 523-560.
• Kouvelis, P., Yu, G. 1997. Robust discrete optimization and its applications. Kluwer Academic Publisher.