Modified Coral Reef Optimization Methods for Job Shop Scheduling Problems
Source abstract
Abstract
The job shop scheduling problem (JSSP) is a fundamental operational research topic with numerous applications in the real world. Since the JSSP is an NP-hard (nondeterministic polynomial time) problem, approximation approaches are frequently used to rectify it. This study proposes a novel biologically-inspired metaheuristic method named Coral Reef Optimization in conjunction with two local search techniques, Simulated Annealing (SA) and Variable Neighborhood Search (VNS), with significant performance and finding-solutions speed enhancement. The two-hybrid algorithms’ performance is evaluated by solving JSSP of various sizes. The findings demonstrate that local search strategies significantly enhance the search efficiency of the two hybrid algorithms compared to the original algorithm. Furthermore, the comparison results with two other metaheuristic algorithms that also use the local search feature and five state-of-the-art algorithms found in the literature reveal the superior search capability of the two proposed hybrid algorithms.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Scheduling and Optimization Algorithms · Metaheuristic Optimization Algorithms Research · Optimization and Search Problems
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Electronic Engineering, National Kaohsiung University of Science and Technology, Kaohsiung 807618, Taiwan
Department of Electronic and Automation Engineering, Nha Trang University, Nha Trang 650000, Vietnam
Funding
National Science and Technology Council, Taiwan
References (49)
Show source-provided references
1. Baptista, M. (2022, August 31). How Important Is Production Scheduling Today? April 2020. Available online: https://blogs.sw.siemens.com/opcenter/how-important-is-production-scheduling-today/.
2. Production scheduling for continuous manufacturing systems with quality constraints
3. The evolution of production scheduling from Industry 3.0 through Industry 4.010.1080/00207543.2021.1925772 ↗
4. A Review of Production Scheduling10.1287/opre.29.4.646 ↗
5. Optimal two- and three-stage production schedules with setup times included10.1002/nav.3800010110 ↗
6. The Complexity of Flowshop and Jobshop Scheduling10.1287/moor.1.2.117 ↗
7. Review of job shop scheduling research and its new perspectives under Industry 4.010.1007/s10845-017-1350-2 ↗
8. A survey of job shop scheduling problem: The types and models10.1016/j.cor.2022.105731 ↗
9. Xhafa, F., and Abraham, A. (2022, July 01). Metaheuristics for Scheduling in Industrial and Manufacturing Applications. Available online: https://link.springer.com/book/10.1007/978-3-540-78985-7.
10. Pinedo, M.L. (2022, July 03). Planning and Scheduling in Manufacturing and Services. Available online: https://link.springer.com/book/10.1007/978-1-4419-0910-7.
11. A research survey: Heuristic approaches for solving multi objective flexible job shop problems10.1007/s10845-020-01547-4 ↗
12. Guzman, E., Andres, B., and Poler, R. (2021). Matheuristic Algorithm for Job-Shop Scheduling Problem Using a Disjunctive Mathematical Model. Computers, 11.10.3390/computers11010001 ↗
13. Viana, M.S., Contreras, R.C., and Junior, O.M. (2022). A New Frequency Analysis Operator for Population Improvement in Genetic Algorithms to Solve the Job Shop Scheduling Problem. Sensors, 22.10.3390/s22124561 ↗
14. The Coral Reefs Optimization Algorithm: A Novel Metaheuristic for Efficiently Solving Optimization Problems
15. A Coral Reefs Optimization algorithm for optimal mobile network deployment with electromagnetic pollution control criterion10.1016/j.asoc.2014.07.007 ↗
16. A novel Coral Reefs Optimization algorithm with substrate layers for optimal battery scheduling optimization in micro-grids10.1007/s00500-016-2295-7 ↗
17. Offshore wind farm design with the Coral Reefs Optimization algorithm10.1016/j.renene.2013.09.004 ↗
18. Bedoya-Valencia, L. (2007). Exact and Heuristic Algorithms for the Job Shop Scheduling Problem with Earliness and Tardiness over a Common Due Date. [Ph.D. Thesis, Old Dominion University].
19. A branch and bound algorithm for the job-shop scheduling problem10.1016/0166-218X(94)90204-6 ↗
20. A research survey: Review of AI solution strategies of job shop scheduling problem
21. Muthuraman, S., and Venkatesan, V.P. (2017, January 2–4). A Comprehensive Study on Hybrid Meta-Heuristic Approaches Used for Solving Combinatorial Optimization Problems. Proceedings of the 2017 World Congress on Computing and Communication Technologies (WCCCT), Tiruchirappalli, India.10.1109/WCCCT.2016.53 ↗
22. Aarts, E., Aarts, E.H., and Lenstra, J.K. (2022, July 03). Local Search in Combinatorial Optimization. Available online: https://press.princeton.edu/books/paperback/9780691115221/local-search-in-combinatorial-optimization.
23. Metaheuristics in Combinatorial Optimization10.1007/s10479-005-3971-7 ↗
24. Yang, X.-S. (2014). Nature-Inspired Optimization Algorithms, Elsevier.10.1016/B978-0-12-416743-8.00005-1 ↗
25. Davis, L. (1985, January 24–26). Job Shop Scheduling with Genetic Algorithms. Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, USA.
26. Holland, J.H. (2022, July 03). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press eBooks. IEEE Xplore. Available online: https://ieeexplore.ieee.org/book/6267401.
27. Kennedy, J., and Eberhart, R. (December, January 27). Particle Swarm Optimization. Proceedings of the ICNN’95—International Conference on Neural Networks, Perth, Australia.
28. Optimization by Simulated Annealing10.1126/science.220.4598.671 ↗
29. A High Performance Search Algorithm for Job-Shop Scheduling Problem10.1016/j.procs.2018.10.157 ↗
30. Yu, H., Gao, Y., Wang, L., and Meng, J. (2020). A Hybrid Particle Swarm Optimization Algorithm Enhanced with Nonlinear Inertial Weight and Gaussian Mutation for Job Shop Scheduling Problems. Mathematics, 8.10.3390/math8081355 ↗
31. An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem10.18201/ijisae.2019751247 ↗
32. Application of Grey Wolf Optimization for Solving Combinatorial Problems: Job Shop and Flexible Job Shop Scheduling Cases10.1109/ACCESS.2018.2833552 ↗
33. Wang, F., Tian, Y., and Wang, X. (2019, January 19–22). A Discrete Wolf Pack Algorithm for Job Shop Scheduling Problem. Proceedings of the 2019 5th International Conference on Control, Automation and Robotics (ICCAR), Beijing, China.10.1109/ICCAR.2019.8813444 ↗
34. Solving combinatorial optimization problems with single seekers society algorithm
35. A Hybrid Coral Reefs Optimization—Variable Neighborhood Search Approach for the Unequal Area Facility Layout Problem10.1109/ACCESS.2020.3010577 ↗
36. Tsai, C.-W., Chang, H.-C., Hu, K.-C., and Chiang, M.-C. (2016, January 9–12). Parallel coral reef algorithm for solving JSP on Spark. Proceedings of the 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Budapest, Hungary.
37. A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation10.1016/0360-8352(96)00047-2 ↗
38. A tutorial survey of job-shop scheduling problems using genetic algorithms, Part II: Hybrid genetic search strategies10.1016/S0360-8352(99)00136-9 ↗
39. A comparison of the performance of multi-objective optimization methodologies for solvent design10.1016/B978-0-12-818634-3.50007-2 ↗
40. Ruiz, J., and Garcia, G. (2012). Simulated Annealing Evolution, IntechOpen.
41. Variable neighborhood search10.1016/S0305-0548(97)00031-2 ↗
42. Variable neighborhood search for the maximum clique10.1016/j.dam.2003.09.012 ↗
43. Lawrence, S. (1984). Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement). [Master’s Thesis, Graduate School of Industrial Administration].
44. A new hybrid genetic algorithm for job shop scheduling problem10.1016/j.cor.2011.12.005 ↗
45. An efficient memetic algorithm for solving the job shop scheduling problem10.1016/j.cie.2011.01.003 ↗
46. Fisher, C., and Thompson, G. (1963). Probabilistic Learning Combinations of Local Job-shop Scheduling Rules, Industrial Scheduling.
47. A Computational Study of the Job-Shop Scheduling Problem10.1287/ijoc.3.2.149 ↗
48. The Shifting Bottleneck Procedure for Job Shop Scheduling10.1287/mnsc.34.3.391 ↗
49. Viana, M.S., Junior, O.M., and Contreras, R.C. (2020). An Improved Local Search Genetic Algorithm with Multi-crossover for Job Shop Scheduling Problem. Artificial Intelligence and Soft Computing, Springer.10.1007/978-3-030-61401-0_43 ↗