Optimizing Manufacturing Efficiency: An Evaluation of Heuristic Algorithms for Nonpreemptive Flow-Shop Scheduling With Makespan Criterion
Abstract
In today’s competitive and technology-driven industrial landscape, optimizing manufacturing efficiency remains a primary objective. Production scheduling emerges as a critical decision-making tool in achieving this goal, playing a pivotal role in coordinating manufacturing operations. Over the past few decades, researchers have developed numerous exact, heuristic, and meta-heuristic scheduling algorithms for diverse production environments. However, selecting a compatible algorithm remains a significant challenge due to the combinatorial nature of scheduling, further compounded by the NP-completeness of the non-preemptive flow-shop scheduling problem. Therefore, this study evaluates eight heuristic algorithms for solving the non-preemptive flow-shop scheduling problem, with a focus on makespan minimization. Using empirical data from a real-world Ready-Made Garment (RMG) manufacturing facility, the performance of the heuristics is assessed in terms of makespan, idle time, and time complexity. Among the methods analyzed, the NEH heuristic demonstrates the most favorable result, with a 2.91% deviation from the theoretical lower bound. The study provides practical insights for researchers and practitioners in selecting effective heuristics under varying scheduling conditions.
References
P. Brucker, Scheduling algorithms. Springer Berlin Heidelberg, Germany, 2007. 21
I. M. Alharkan, Algorithms for sequencing and scheduling. Industrial Engineering Department, King Saud University, Riyadh, Saudi Arabia, 2005.
Md. K. A. Asif, S. T. Alam, S. Jahan, and Md. R. Arefin, “An empirical analysis of exact algorithms for solving non-preemptive flow shop scheduling problem,” International Journal of Research in Industrial Engineering, vol. 11, no. 3, pp. 306–321, Sep. 2022, doi: 10.22105/RIEJ.2022.350120.1324.
R. W. Conway, W. L. Maxwell, and L. W. Miller, Theory of scheduling. Addison-Wesley Publishing Company, 1967.
K. R. Baker, Introduction to sequencing and scheduling. John Wiley & Sons, Inc., New York, USA, 1974.
S. M. Johnson, “Optimal two- and three-stage production schedules with setup times included,” Naval Research Logistics Quarterly, vol. 1, no. 1, pp. 61–68, Mar. 1954, doi: 10.1002/NAV.3800010110.
D. S. Palmer, “Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time— A Quick Method of Obtaining a Near Optimum,” Journal of the Operational Research Society, vol. 16, no. 1, pp. 101–107, Mar. 1965, doi: 10.1057/JORS.1965.8.
H. G. Campbell, R. A. Dudek, and M. L. Smith, “ A Heuristic Algorithm for the n Job, m Machine Sequencing Problem ,” Manage Sci, vol. 16, no. 10, p. B-630-B-637, Jun. 1970, doi: 10.1287/MNSC.16.10.B630.
J. N. D. Gupta, “A Functional Heuristic Algorithm for the Flowshop Scheduling Problem,” Journal of the Operational Research Society 1971 22:1, vol. 22, no. 1, pp. 39–47, Mar. 1971, doi: 10.1057/JORS.1971.18.
D. G. Dannenbring, “Evaluation of Flow Shop Sequencing Heuristics,” Manage Sci, vol. 23, no. 11, pp. 1174–1182, 1977, doi: 10.1287/MNSC.23.11.1174.
M. Nawaz, E. E. Enscore, and I. Ham, “A heuristic algorithm for the m-machine, n-job flowshop sequencing problem,” Omega (Westport), vol. 11, no. 1, pp. 91–95, 1983, doi: 10.1016/0305-0483(83)90088-9.
C. Rajendran and D. Chaudhuri, “An efficient heuristic approach to the scheduling of jobs in a flowshop,” Eur J Oper Res, vol. 61, no. 3, pp. 318–325, Sep. 1992, doi: 10.1016/03772217(92)90361-C.
C. Koulamas, “A new constructive heuristic for the flowshop scheduling problem,” Eur J Oper Res, vol. 105, no. 1, pp. 66–71, Feb. 1998, doi: 10.1016/S0377-2217(97)00027-1.
V. Modrák and R. S. Pandian, “Flow shop scheduling algorithm to minimize completion time for n-jobs m-machines problem,” Tehnički vjesnik, vol. 17, no. 3, pp. 273–278, Sep. 2010.
N. R. N, N. R. O, and R. B. I, “Modified Heuristic Time Deviation Technique for Job Sequencing and Computation of Minimum Total Elapsed Time,” International Journal of Computer Science and Information Technology, vol. 5, no. 3, pp. 67–77, Jun. 2013, doi: 10.5121/IJCSIT.2013.5305.
J. Lin, Z. J. Wang, and X. Li, “A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem,” Swarm Evol Comput, vol. 36, pp. 124–135, Oct. 2017, doi: 10.1016/J.SWEVO.2017.04.007.
Y. Yang and X. Li, “A knowledge-driven constructive heuristic algorithm for the distributed assembly blocking flow shop scheduling problem,” Expert Syst Appl, vol. 202, Sep. 2022, doi: 10.1016/J.ESWA.2022.117269.
Z. Pan, D. Lei, and L. Wang, “A Knowledge-Based Two-Population Optimization Algorithm for Distributed Energy-Efficient Parallel Machines Scheduling,” IEEE Trans Cybern, vol. 52, no. 6, pp. 5051–5063, Jun. 2022, doi: 10.1109/TCYB.2020.3026571.
F. Zhao, S. Di, and L. Wang, “A Hyperheuristic With Q-Learning for the Multiobjective EnergyEfficient Distributed Blocking Flow Shop Scheduling Problem,” IEEE Trans Cybern, vol. 53, no. 5, pp. 3337–3350, May 2023, doi: 10.1109/TCYB.2022.3192112.
F. Zhao, C. Zhuang, L. Wang, and C. Dong, “An Iterative Greedy Algorithm With Q -Learning Mechanism for the Multiobjective Distributed No-Idle Permutation Flowshop Scheduling,” IEEE Trans Syst Man Cybern Syst, vol. 54, no. 5, pp. 3207–3219, May 2024, doi: 10.1109/TSMC.2024.3358383.
B. Jerbi, S. Kanoun, and H. Kamoun, “Multi-objective mathematical programs to minimize the makespan, the patients’ flow time, and doctors’ workloads variation using dispatching rules and genetic algorithm,” Yugoslav Journal of Operations Research, vol. 35, no. 2, pp. 365–382, 2025, doi: 10.2298/YJOR240115032J.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
