A Whale Optimization Algorithm Approach for Flow Shop Scheduling to Minimize Makespan
Keywords:
Flow shop scheduling, Scheduling optimization, Whale optimization algorithm, MetaheuristicsAbstract
Flow shop scheduling is crucial in manufacturing and production environments because it directly impacts output and overall production efficiency. It involves processing a set of jobs on multiple machines in a specific order. The objective is to determine the optimal job sequence that minimizes the makespan, which is the total time required to complete all jobs. This study proposes a computerized approach utilizing the Whale Optimization Algorithm (WOA) to solve the flow shop scheduling problem and minimize the makespan. The WOA is a recently developed meta-heuristic algorithm inspired by the bubble-net hunting strategy of humpback whales. The performance of the WOA is evaluated using five benchmark problems with varying numbers of jobs and machines, and the results are compared with those obtained from other algorithms reported in the literature, such as genetic algorithms and heuristic models. The findings demonstrate that the WOA can effectively solve the flow shop scheduling problem and provide improved makespan values, with an average efficiency of 7.33% compared to the other algorithms.
References
M. Khatami, A. Salehipour, and T. C. E. Cheng, “Flow-shop scheduling with exact delays to minimize makespan,” Comput Ind Eng, vol. 183, p. 109456, 2023, doi: https://doi.org/10.1016/j.cie.2023.109456.
X. Chen, Q. Miao, B. M. T. Lin, M. Sterna, and J. Blazewicz, “Two-machine flow shop scheduling with a common due date to maximize total early work,” Eur J Oper Res, vol. 300, no. 2, pp. 504–511, 2022, doi: https://doi.org/10.1016/j.ejor.2021.07.055.
C. H. Lim and S. K. Moon, “A Two-Phase Iterative Mathematical Programming-Based Heuristic for a Flexible Job Shop Scheduling Problem with Transportation,” Applied Sciences, vol. 13, no. 8. 2023. doi: 10.3390/app13085215.
W. Shao, Z. Shao, and D. Pi, “Effective constructive heuristics for distributed no-wait flexible flow shop scheduling problem,” Comput Oper Res, vol. 136, p. 105482, 2021, doi: https://doi.org/10.1016/j.cor.2021.105482.
Ö. Tosun, M. K. Marichelvam, and N. Tosun, “A literature review on hybrid flow shop scheduling,” International Journal of Advanced Operations Management, vol. 12, no. 2, pp. 156–194, Jan. 2020, doi: 10.1504/IJAOM.2020.108263.
J. K. Lenstra, V. A. Strusevich, and M. Vlach, “A historical note on the complexity of scheduling problems,” Operations Research Letters, vol. 51, no. 1, pp. 1–2, 2023, doi: https://doi.org/10.1016/j.orl.2022.11.006.
B. Toaza and D. Esztergár-Kiss, “A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems,” Appl Soft Comput, vol. 148, p. 110908, 2023, doi: https://doi.org/10.1016/j.asoc.2023.110908.
M. Abd Elaziz, S. Lu, and S. He, “A multi-leader whale optimization algorithm for global optimization and image segmentation,” Expert Syst Appl, vol. 175, p. 114841, 2021, doi: https://doi.org/10.1016/j.eswa.2021.114841.
J. S. Neufeld, S. Schulz, and U. Buscher, “A systematic review of multi-objective hybrid flow shop scheduling,” Eur J Oper Res, vol. 309, no. 1, pp. 1–23, 2023, doi: https://doi.org/10.1016/j.ejor.2022.08.009.
M. Nageswara Rao, K. Prakash Babu, K. K. Dama, S. K. Malyala, and P. K. Chaurasiya, “Flexible Manufacturing System Simultaneous Scheduling Through Palmer Heuristic Algorithm BT - Technology Innovation in Mechanical Engineering: Select Proceedings of TIME 2021,” P. K. Chaurasiya, A. Singh, T. N. Verma, and U. Rajak, Eds., Singapore: Springer Nature Singapore, 2022, pp. 1013–1021. doi: 10.1007/978-981-16-7909-4_94.
S. Schulz, “A genetic algorithm to solve the hybrid flow shop scheduling problem with subcontracting options and energy cost consideration,” Advances in Intelligent Systems and Computing, vol. 854, pp. 263–273, 2019, doi: 10.1007/978-3-319-99993-7_23.
D. Li, X. Meng, Q. Liang, and J. Zhao, “A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines,” J Intell Manuf, vol. 26, no. 5, pp. 873–890, Feb. 2014, doi: 10.1007/s10845-014-0874-y.
J. Yan, J. Wen, and L. Li, “Genetic algorithm based optimization for energy-aware hybrid flow shop scheduling,” in Proceedings of the 2014 International Conference on Artificial Intelligence, ICAI 2014 - WORLDCOMP 2014, 2014, pp. 358–364. [Online]. Available: https://www.scopus.com/inward/record.uri?eid=2-s2.0-84953357421&partnerID=40&md5=85a27447b9e56d9082071b3ea538214c
M. Eddaly, B. Jarboui, and P. Siarry, “Combinatorial Particle Swarm Optimization for solving Blocking Flowshop Scheduling Problem,” J Comput Des Eng, 2016, doi: 10.1016/j.jcde.2016.05.001.
C.-J. Liao, Chao-Tang Tseng, and P. Luarn, “A discrete version of particle swarm optimization for flowshop scheduling problems,” Comput Oper Res, vol. 34, no. 10, pp. 3099–3111, 2007, Accessed: Jan. 10, 2014. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0305054805003643
S. Mirjalili and A. Lewis, “The Whale Optimization Algorithm,” Advances in Engineering Software, vol. 95, pp. 51–67, 2016, doi: 10.1016/j.advengsoft.2016.01.008.
M. S. Uzer and O. Inan, “Application of improved hybrid whale optimization algorithm to optimization problems,” Neural Comput Appl, vol. 35, no. 17, pp. 12433–12451, 2023, doi: 10.1007/s00521-023-08370-x.
M. H. Nadimi-Shahraki, H. Zamani, Z. Asghari Varzaneh, and S. Mirjalili, “A Systematic Review of the Whale Optimization Algorithm: Theoretical Foundation, Improvements, and Hybridizations,” Archives of Computational Methods in Engineering, vol. 30, no. 7, pp. 4113–4159, 2023, doi: 10.1007/s11831-023-09928-7.
A. M. Ahmed et al., “Balancing exploration and exploitation phases in whale optimization algorithm: an insightful and empirical analysis,” in Handbook of Whale Optimization Algorithm, S. B. T.-H. of W. O. A. Mirjalili, Ed., Academic Press, 2024, pp. 149–156. doi: https://doi.org/10.1016/B978-0-32-395365-8.00017-8.
M. Li, X. Yu, B. Fu, and X. Wang, “A modified whale optimization algorithm with multi-strategy mechanism for global optimization problems,” Neural Comput Appl, 2023, doi: 10.1007/s00521-023-08287-5.
I. A. Chaudhry and A. M. Khan, “Minimizing makespan for a no-wait flowshop using genetic algorithm,” Sadhana, vol. 37, pp. 695–707, 2012.
I. A. Chaudhry, I. A. Q. Elbadawi, M. Usman, and M. Tajammal Chugtai, “Minimising total flowtime in a no-wait flow shop (NWFS) using genetic algorithms,” Ingenier{’i}a e Investigación, vol. 38, no. 3, pp. 68–79, 2018.
A. K. Agarwal and N. Kumar, “Flow Shop Scheduling Problem For 8-Jobs, 3-Machines With Make Span Criterion,” International Journal of Innovations in Engineering and Technology (IJIET), vol. 7, no. 11, pp. 1757–1762, 2012.
A. K. Agarwal and R. Garg, “Flow Shop Scheduling Problem For 10-Jobs, 8-Machines With Make Span Criterion,” International Journal of Innovative Research and Development, pp. 389–403, 2013.
A. K. Agarwal and R. Garg, “Flowshop Scheduling Problem for 10-Jobs, 10-Machines By Heuristics Models Using Makespan Criterion,” International Journal of Innovations in Engineering and Technology (IJIET), vol. 2, no. 1, pp. 1058–2319, 2013.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 The Author(s)
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
