Three-Machine Flowshop Scheduling Problem to Minimize Makespan with Interval Processing Times

Ali Allahverdi; Muberra Allahverdi

Ali Allahverdi
Muberra Allahverdi

Abstract

The three-machine flowshop scheduling problem with interval processing times, where processing times are within a lower and an upper bound, is studied. The objective is to minimize makespan. Given that the problem is NP-hard, some heuristics are proposed. The proposed heuristics are assessed based on numerous experiments. The data for the experiments were randomly generated for different number of jobs and different distributions, where both symmetric and skewed distributions are considered. The number of replications considered for each combination of the number of jobs and the distribution was one hundred. Error of each heuristic was reported. Computational experiments indicated that one of the proposed heuristics significantly performs better than the other heuristics.

References

Allahverdi, A. (2022). A survey of scheduling problems with uncertain interval/bounded processing/setup times. Journal of Project Management, 7, 255-264.
Allahverdi, A. (2008). Three-machine flowshop scheduling problem to minimize makespan with bounded setup and processing times. Journal of the Chinese Institute of Industrial Engineers, 25, 52-61.
Allahverdi, A., & Aydilek, H. (2010). Heuristics for the two-machine flowshop scheduling problem to minimize makespan with bounded processing times. International Journal of Production Research, 48, 6367-6385.
Allahverdi, A., & Mittenthal, J. (1994). Two-Machine Ordered Flowshop Scheduling Under Random Breakdowns. Mathematical and Computer Modelling, 20, 9-17.
Aydilek, H., & Allahverdi, A. (2013). A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times. Applied Mathematical Modelling, 37, 7164-7173.
Aydilek, A., Aydilek, H., & Allahverdi, A. (2017). Increasing the profitability and competitiveness in a production environment with random and bounded setup times. International Journal of Production Research, 51, 106- 117.
Aydilek, H., Aydilek, A., Allahverdi, M., & Allahverdi, A. (2022). More effective heuristics for a two-machine no-wait flowshop to minimize maximum lateness. International Journal of Industrial Engineering Computations, 13, 543-556.
Al-Anzi, F.S., & Allahverdi, A. (2013). An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time. Journal of Manufacturing Systems, 32, 825-830.
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.
Ng, C.T., Matsveichuk, N.M., Sotskov, Y. N., & Cheng, T.C.E. (2009). Two-machine flow-shop minimum-length scheduling with interval processing times. Asia-Pacific Journal of Operational Research, 26, 715-734.
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.
Sotskov, Y.N., Matsveichuk, N.M., Kasiankou, A. A., & Werner, F. (2014). Time management based on two-machine flowshop scheduling with uncertain job processing times. International Journal of Information Technologies Knowledge, 8, 212-224.