Improvement of Nature-Based Optimization Methods for Solving Job shop Scheduling Problems
Improvement of Nature-Based Optimization Methods for Solving Job shop Scheduling Problems |
||
 |
 |
|
| © 2023 by IJETT Journal | ||
| Volume-71 Issue-3 |
||
| Year of Publication : 2023 | ||
| Author : Hakim Jebari, Siham Rekiek, Kamal Reklaoui |
||
| DOI : 10.14445/22315381/IJETT-V71I3P232 | ||
How to Cite?
Hakim Jebari, Siham Rekiek, Kamal Reklaoui, "Improvement of Nature-Based Optimization Methods for Solving Job shop Scheduling Problems," International Journal of Engineering Trends and Technology, vol. 71, no. 3, pp. 312-324, 2023. Crossref, https://doi.org/10.14445/22315381/IJETT-V71I3P232
Abstract
Scheduling is a key decision-making process within the industrial manufacturing sectors. Effective scheduling is crucial for enhancing the company's key performance indicators and competitiveness. Job shop scheduling is used extensively in real-world businesses and is challenging to solve due to its NP-hard complexity. Nature-inspired optimization methods have proven to solve various difficult optimization issues successfully. This paper presents nature-based multi-hybrid methods for solving job shop scheduling issues. The extensive experiments of these proposed methods are carried out to assess their performance in all well-known reference instances. An in-depth analysis of other methods available in the literature is also conducted to validate and compare the reliability and efficacy of the proposed methods. The computational results demonstrate that the proposed methods have achieved high performance and have provided better results. The proposed methods were more competitive and effective for the considered problem.
Keywords
Hybridization, Job shop, Nature-inspired method, Optimization, Scheduling.
References
[1] Li Xixing, and Liu Yi, “Approach of Solving Dual Resource Constrained Multi-Objective Flexible Job Shop Scheduling Problem Based on MOEA/D,” International Journal of Online and Biomedical Engineering, vol. 14, no. 7, pp. 75–89, 2018. Google Scholar | Crossref | Publisher Site
[2] Michael R. Garey, and David S. Johnson, “A Guide to the Theory of NP-Completeness,” Computers and Intractability, Freeman, 1979. Publisher Site
[3] H. Fisher, and G.L. Thompson, Industrial Scheduling, Englewood Cliffs, NJ: Prentice-Hall, 1963.
[4] S. Lawrence, “Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques,” Pittsburgh: Graduate School of Industrial Administration, 1984.
[5] Joseph Adams, Egon Balas, and Daniel Zawack, “The Shifting Bottleneck Procedure for Job-Shop Scheduling,” Management Science, vol. 34, no. 3, pp. 391–401, 1988. Google Scholar | Crossref | Publisher Site
[6] David Applegate, and William Cook, “A Computational Study of the Job-Shop Scheduling Problem,” ORSA Journal on Computing, vol. 3, no. 2, pp. 149–156, 1991. Google Scholar | Crossref | Publisher Site
[7] Takeshi Yamada, and Ryohei Nakano, “A Genetic Algorithm Applicable to Large-Scale Job-Shop Problems,” Proceedings of the second International Workshop on Parallel Problem Solving from Nature (PPSN’2), Brussels, Belgium, pp. 281–290, 1992. Google Scholar | Publisher Site
[8] Robert H. Storer, S. David Wu, and Renzo Vaccari, “New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling,” Management Science, vol. 38, no. 10, pp. 1495–1509, 1992. Google Scholar | Crossref | Publisher Site
[9] Éric D. Taillard, “Parallel Taboo Search Techniques for the Job Shop Scheduling Problem,” ORSA Journal on Computing, vol. 6, no. 2, pp. 108–117, 1994. Google Scholar | Crossref | Publisher Site
[10] Ebru Demirkol, Sanjay Mehta, and Reha Uzsoy, “A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems,” Journal of Heuristics, vol. 3, no. 2, pp. 111–137, 1997. Google Scholar | Crossref | Publisher Site
[11] E.G. Talbi, “A Taxonomy of Hybrid Metaheuristics,” International Journal of Heuristics, vol. 8, no. 5, pp. 541–564, 2002. Google Scholar | Crossref | Publisher Site
[12] Thi-Kien Dao et al., “Parallel Bat Algorithm for Optimizing Makespan in Job Shop Scheduling Problems,” Journal of Intelligent Manufacturing, vol. 29, no. 2, pp. 451–462, 2018. Google Scholar | Crossref | Publisher Site
[13] Mohamed Kurdi, “A New Hybrid Island Model Genetic Algorithm for Job Shop Scheduling Problem,” Computers & Industrial Engineering, vol. 88, pp. 273–283, 2015. Google Scholar | Crossref | Publisher Site
[14] T.C.E. Cheng, Bo Peng, and Zhipeng Lü, “A Hybrid Evolutionary Algorithm to Solve the Job Shop Scheduling Problem,” Annals of Operations Research, vol. 242, no. 2, pp. 223–237, 2016. Google Scholar | Crossref | Publisher Site
[15] Andr´e Henning, “Praktische Job-Shop Scheduling-Probleme,” Ph.D. Thesis, Friedrich-Schiller-Universität Jena, Jena, Germany, 2002. Publisher Site
[16] José Fernando Gonçalves, and Mauricio G. C. Resende, “An Extended Akers Graphical Method with a Biased Random-Key Genetic Algorithm for Job-Shop Scheduling,” International Transactions on Operational Research, vol. 21, no. 2, pp. 215–246, 2014. Google Scholar | Crossref | Publisher Site
[17] Eugeniusz Nowicki, and Czesław Smutnicki, “An Advanced Taboo Search Algorithm for the Job Shop Problem,” Journal of Scheduling, vol. 8, no. 2, pp. 145–159, 2005. Google Scholar | Crossref | Publisher Site
[18] Eugeniusz Nowicki, and Czeslaw Smutnicki, “A Fast Taboo Search Algorithm for the Job Shop Problem,” Management Science, vol. 42, no. 6, pp. 783–938, 1996. Google Scholar | Crossref | Publisher Site
[19] Marco Antonio Cruz-Chávez et al., “Hybrid Micro Genetic Multi-Population Algorithm with Collective Communication for the Job Shop Scheduling Problem,” IEEE Access, vol. 7, pp. 82358–82376, 2019. Google Scholar | Crossref | Publisher Site
[20] Bao-An Han, and Jian-Jun Yang, “Research on Adaptive Job Shop Scheduling Problems Based on Dueling Double DQN,” IEEE Access, vol. 8, pp. 186474–186495, 2020. Google Scholar | Crossref | Publisher Site
[21] Panos M. Pardalos, Oleg V. Shylo, and Alkis Vazacopoulos, “Solving Job Shop Scheduling Problems Utilizing the Properties of Backbone and Big Valley,” Computational Optimization and Applications, vol. 47, no. 1, pp. 61–76, 2010. Google Scholar | Crossref | Publisher Site
[22] Ferdinando Pezzella, and Emanuela Merelli, “A Tabu Search Method Guided by Shifting Bottleneck for the Job Shop Scheduling Problem,” European Journal of Operational Research, vol. 120, no. 2, pp. 297–310, 2000. Google Scholar | Crossref | Publisher Site
[23] Petr Vil´ım, Philippe Laborie, and Paul Shaw, “Failure-Directed Search for Constraint-Based Scheduling-Detailed Experimental Results,” CPAIOR’2015, Barcelona, Spain, pp. 437–453, 2015. Google Scholar | Publisher Site
[24] Bo Peng, Zhipeng Lü, and T.C.E. Cheng, “A Tabu Search/Path Relinking Algorithm To Solve The Job Shop Scheduling Problem,” Computers and Operations Research, vol. 53, pp. 154–164, 2015. Google Scholar | Crossref | Publisher Site
[25] Oleg V. Shylo, and Hesam Shams, “Boosting Binary Optimization via Binary Classification: A Case Study of Job Shop Scheduling,” cs.AI/math.OC abs/1808.10813, arXiv, 2018. Google Scholar | Crossref | Publisher Site
[26] Shao-Juan Wang, Chun-Wei Tsai, and Ming-Chao Chiang, “A High Performance Search Algorithm for Job-Shop Scheduling Problem,” Procedia Computer Science, vol. 141, pp. 119–126, 2018. Google Scholar | Crossref | Publisher Site
[27] Leila Asadzadeh, “A Local Search Genetic Algorithm for the Job Shop Scheduling Problem with Intelligent Agents,” Computers & Industrial Engineering, vol. 85, pp. 376–383, 2015. Google Scholar | Crossref | Publisher Site
[28] S.K. Sahana, I. Mukherjee, and P.K. Mahanti, “Parallel Artificial Bee Colony (PABC) for Job Shop Scheduling Problems,” Advances in Information Sciences and Service Sciences, vol. 10, no. 3, pp. 1–11, 2018. Google Scholar | Crossref | Publisher Site
[29] Jebari Hakim, Siham Rekiek, and Kamal Reklaoui, “Solving the Job Shop Scheduling Problem by the Multi-Hybridization of Swarm Intelligence Techniques,” International Journal of Advanced Computer Science and Applications, vol. 13, no. 7, pp. 753–764, 2022. Google Scholar | Crossref | Publisher Site
[30] S. Sivasubramaniam, and S.P. Balamurugan, “Nature Inspired Optimization with Hybrid Machine Learning Model for Cardiovascular Disease Detection and Classification,” International Journal of Engineering Trends and Technology, vol. 70, no. 12, pp. 127–137, 2022. Crossref | Publisher Site
[31] Jebari Hakim et al., “Multi Hybridization of Swarm Intelligence Methods to Solve Job Shop Scheduling Problem,” Journal of Theoretical and Applied Information Technology, vol. 97, no. 16, pp. 4366–4386, 2019. [31] Google Scholar | Publisher Site
[32] Jebari Hakim et al., “The Search of Balance Between Diversification and Intensification in Artificial Bee Colony to Solve Job Shop Scheduling Problem,” Journal of Theoretical and Applied Information Technology, vol. 97, no. 2, pp. 658–673, 2019. Google Scholar | Publisher Site
[33] Dervis Karaboga, “An Idea Based on Honey Bee Swarm for Numerical Optimization,” Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, vol. 200, 2005. Google Scholar | Publisher Site
[34] D. Karaboga, and B. Akay, “A Comparative Study of Artificial Bee Colony Algorithm,” Applied Mathematics and Computation, vol. 214, no. 1, pp. 108–32, 2009. Google Scholar | Crossref | Publisher Site
[35] V. Satyanarayana and V. Jayasankar, “Advanced Modeling and Optimization of Hybrid Renewable Energy Management Strategy Based on Artificial Bee Colony Algorithm in Micro Grid,” International Journal of Engineering Trends and Technology, vol. 70, no. 10, pp. 329–338, 2022. Crossref | Publisher Site
[36] Ammar K Alazzawi, Helmi Md Rais, and Shuib Basri, “ABCVS: An Artificial Bee Colony for Generating Variable T-Way Test Sets,” International Journal of Advanced Computer Science and Applications, vol. 10, no. 4, pp. 259–274, 2019. Google Scholar | Crossref | Publisher Site
[37] M. Fatih Tasgetiren et al., “A Discrete Artificial Bee Colony Algorithm for the Total Flowtime Minimization in Permutation Flow Shops,” Information Sciences, vol. 181, no. 16, pp. 3459–3475, 2011. Google Scholar | Crossref | Publisher Site
[38] Nasser Tairan, Habib Shah, and Aliya Aleryani, “Prediction of Crude Oil Prices Using Hybrid Guided Best-So-Far Honey Bees Algorithm-Neural Networks,” International Journal of Advanced Computer Science and Applications, vol. 10, no. 5, pp. 317–330, 2019. Google Scholar | Crossref | Publisher Site
[39] S. Sivasubramaniam, and S. P. Balamurugan, "Nature Inspired Optimization with Hybrid Machine Learning Model for Cardiovascular Disease Detection and Classification," International Journal of Engineering Trends and Technology, vol. 70, no. 12, pp. 127-137, 2022. Crossref | Publisher Site
[40] Shyam Sunder Pabboju, and Adilakshmi Thondepu, “Effective Task Scheduling in Cloud Computing using Improved BAT Algorithm,” International Journal of Engineering Trends and Technology, vol. 70, no. 10, pp. 271–276, 2022. Crossref | Publisher Site
[41] Xin-She Yang, “Bat Algorithm: Literature Review and Applications,” International Journal of Bio-Inspired Computing, vol. 5, no. 3, pp. 141–149, 2013. Google Scholar | Crossref | Publisher Site
[42] Koffka Khan, Alexander Nikov, and Ashok Sahai, “A Fuzzy Bat Clustering Method for Ergonomic Screening of Office Workplaces,” Advances in Intelligent and Soft Computing, vol. 101, pp. 59–66, 2011. Google Scholar | Crossref | Publisher Site
[43] Waqas Haider Bangyal et al., “An Improved Bat Algorithm based on Novel Initialization Technique for Global Optimization Problem,” International Journal of Advanced Computer Science and Applications, vol. 9, no. 7, pp. 158–166, 2018. Google Scholar | Crossref | Publisher Site
[44] Jiann-Horng Lin et al., “A Chaotic Levy Flight Bat Algorithm for Parameter Estimation in Nonlinear Dynamic Biological Systems,” Journal of Computing and Information Technology, vol. 2, no. 2, pp. 56–63, 2012. Google Scholar | Publisher Site
[45] Jian Xie, Yongquan Zhou, and Huan Chen, “A Novel Bat Algorithm Based on Deferential Operator and Levy Flights Trajectory,” Computational Intelligence and Neuroscience, pp. 1–13, 2013. Google Scholar | Crossref | Publisher Site
[46] Caichang Ding, Wenxiu Peng, and Weiming Wang, “Hybrid Metaheuristics and their Implementations,” International Journal of Online and Biomedical Engineering, vol. 11, no. 7, pp. 25–28, 2015. Google Scholar | Crossref | Publisher Site
[47] Ramanathan.L, and Ulaganathan.K, "Nature-inspired Metaheuristic Optimization Technique-Migrating Bird‟s Optimization in Industrial Scheduling Problem," SSRG International Journal of Industrial Engineering, vol. 1, no. 2, pp. 12-17, 2014. Google Scholar | Crossref | Publisher Site
[48] Yazhi Li, Xiaoping Li, and Jatinder N.D. Gupta, “Solving the Multi-Objective Flowline Manufacturing Cell Scheduling Problem by Hybrid Harmony Search,” Expert Systems with Applications, vol. 42, no. 3, pp. 1409-1417, 2015. Google Scholar | Crossref | Publisher Site
[49] Xiuli Wu, Xianli Shen, and Qi Cui, “Multi-Objective Flexible Flow Shop Scheduling Problem Considering Variable Processing Time due to Renewable Energy,” Sustainability, vol. 10, no. 3, p. 841, 2018. Google Scholar | Crossref | Publisher Site
[50] Dervis Karaboga et al., “A Comprehensive Survey: Artificial Bee Colony (Abc) Algorithm and Applications,” Artificial Intelligence Review, vol. 42, no. 1, pp. 21–57, 2014. Google Scholar | Crossref | Publisher Site
[51] Xin-She Yang, Nature-Inspired Optimization Algorithms, Elsevier, London, 2014. Google Scholar | Crossref | Publisher Site