Advanced Tree-Seed Algorithm for Large Sized JSP Problems

Abstract

Globalizing economies force manufacturing companies to develop themselves and take new measures. Planning the production process is indispensable and the Job shop scheduling (JSP) problem has a great role in planning the production accurately. In JSP, jobs have to run in the correct order on the appropriate machines, and planning to be completed in the shortest possible time is a combinatorial hard optimization problem. Meta-heuristic algorithms are frequently used in solving JSP problems, which is an NP-Hard optimization problems. In this study, the exploration and exploitation abilities in the Tree-Seed Algorithm (TSA) are enhanced with the swap, symmetry, and shift mutation operators. The proposed new TSA (Advanced TSA-ATSA) algorithm is compared with well-known meta-heuristic algorithms in the literature in large-size JSP problems. According to the results obtained from the experimental studies, the proposed ATSA has shown promising performance.

Keywords

• Tree-Seed Algorithm
• Job Shop Sch. Prob.
• Meta-Heuristic Alg.
• Mutation Operators

Büyük Boyutlu JSP Problemlerinde Gelişmiş Ağaç-Tohum Algoritması

Abstract

Küreselleşen ekonomiler, imalatçı firmaları kendilerini geliştirmeye ve yeni önlemler almaya zorlamaktadır. Üretim sürecinin planlanması vazgeçilmezdir ve üretimin doğru planlanmasında Job shop çizelgeleme (JSP) probleminin büyük rolü vardır. JSP'de, işlerin uygun makinelerde doğru sırada çalışması gerekir ve mümkün olan en kısa sürede tamamlanması için hazırlanan planlama ise kombinatoryal zorlu bir optimizasyon problemidir. NP-Zor bir optimizasyon problemi olan JSP problemlerinin çözümünde meta-sezgisel algoritmalar sıklıkla kullanılmaktadır. Bu çalışmada, Ağaç Tohum Algoritması'ndaki (TSA) keşif ve sömürü yetenekleri, takas, simetri ve kaydırma mutasyon operatörleri ile geliştirilmiştir. Önerilen yeni TSA (Gelişmiş TSA-GTSA) algoritması, büyük boyutlu JSP problemlerinde literatürde iyi bilinen meta-sezgisel algoritmalarla karşılaştırılmıştır. Deneysel çalışmalardan elde edilen sonuçlara göre önerilen GTSA'nın umut verici performans sağladığını göstermiştir.

Keywords

• Ağaç-Tohum Alg.
• İş Atl. Plan. Problemi
• Meta-Sezgisel Alg.
• Mutasyon Operatörleri

References

1. [1] H. Mousavipoor, H. Farughi, and F. Ahmadizar, "Job shop scheduling problem based on learning effects, flexible maintenance activities and transportation times," Journal of Industrial and Systems Engineering, vol. 12, no. 3, pp. 107-119, 2019.
2. [2] Y. Yu, "A Research Review on Job Shop Scheduling Problem," in E3S Web of Conferences, 2021, vol. 253: EDP Sciences, p. 02024.
3. [3] M. R. Garey, D. S. Johnson, and R. Sethi, "The complexity of flowshop and jobshop scheduling," Mathematics of operations research, vol. 1, no. 2, pp. 117-129, 1976.
4. [4] R. Buddala and S. S. Mahapatra, "An integrated approach for scheduling flexible job-shop using teaching–learning-based optimization method," Journal of Industrial Engineering International, vol. 15, no. 1, pp. 181-192, 2019.
5. [5] J. Kennedy and R. Eberhart, "Particle swarm optimization," in Proceedings of ICNN'95-international conference on neural networks, 1995, vol. 4: IEEE, pp. 1942-1948.
6. [6] Y. Fan, P. Wang, A. A. Heidari, H. Chen, and M. Mafarja, "Random reselection particle swarm optimization for optimal design of solar photovoltaic modules," Energy, vol. 239, p. 121865, 2022.
7. [7] L. Zhang, C. P. Lim, Y. Yu, and M. Jiang, "Sound classification using evolving ensemble models and Particle Swarm Optimization," Applied Soft Computing, vol. 116, p. 108322, 2022.
8. [8] N. Karasekreter, M. A. Şahman, F. Başçiftçi, and U. Fidan, "PSO-based clustering for the optimization of energy consumption in wireless sensor network," Emerging Materials Research, vol. 9, no. 3, pp. 776-783, 2020.

9. [9] M. A. Şahman, A. A. Altun, and A. O. Dündar, "A new MILP model proposal in feed formulation and using a hybrid-linear binary PSO (H-LBP) approach for alternative solutions," Neural Computing and Applications, vol. 29, no. 2, pp. 537-552, 2018.
10. [10] D. Karaboga, "An idea based on honey bee swarm for numerical optimization," Citeseer, 2005.
11. [11] T. Ye et al., "Artificial bee colony algorithm with efficient search strategy based on random neighborhood structure," Knowledge-Based Systems, p. 108306, 2022.
12. [12] G. Yavuz, B. Durmuş, and D. Aydın, "Artificial Bee Colony Algorithm with Distant Savants for constrained optimization," Applied Soft Computing, vol. 116, p. 108343, 2022.
13. [13] M. S. Kiran, "The continuous artificial bee colony algorithm for binary optimization," Applied Soft Computing, vol. 33, pp. 15-23, 2015.
14. [14] M. S. Kiran, H. Hakli, M. Gunduz, and H. Uguz, "Artificial bee colony algorithm with variable search strategy for continuous optimization," Information Sciences, vol. 300, pp. 140-157, 2015.
15. [15] S. Mirjalili, S. M. Mirjalili, and A. Lewis, "Grey wolf optimizer," Advances in engineering software, vol. 69, pp. 46-61, 2014.
16. [16] J. Adhikary and S. Acharyya, "Randomized Balanced Grey Wolf Optimizer (RBGWO) for solving real life optimization problems," Applied Soft Computing, p. 108429, 2022.
17. [17] L. Yin and Z. Sun, "Distributed multi-objective grey wolf optimizer for distributed multi-objective economic dispatch of multi-area interconnected power systems," Applied Soft Computing, vol. 117, p. 108345, 2022.
18. [18] K. Tütüncü, M. A. Şahman, and E. Tuşat, "A hybrid binary grey wolf optimizer for selection and reduction of reference points with extreme learning machine approach on local GNSS/leveling geoid determination," Applied Soft Computing, vol. 108, p. 107444, 2021.
19. [19] M. S. Kiran, "TSA: Tree-seed algorithm for continuous optimization," Expert Systems with Applications, vol. 42, no. 19, pp. 6686-6698, 2015.
20. [20] X. Song, Y. Cao, and C. Chang, "A hybrid Algorithm of PSO and SA for Solving JSP," in 2008 Fifth international conference on fuzzy systems and knowledge discovery, 2008, vol. 1: IEEE, pp. 111-115.
21. [21] P. Pongchairerks and V. Kachitvichyanukul, "A comparison between algorithms VNS with PSO and VNS without PSO for job-shop scheduling problems," International Journal of Computational Science, vol. 1, no. 2, pp. 179-191, 2007.
22. [22] P. Pongchairerks and V. Kachitvichyanukul, "A two-level particle swarm optimisation algorithm on job-shop scheduling problems," International Journal of Operational Research, vol. 4, no. 4, pp. 390-411, 2009.
23. [23] D. Sha and C.-Y. Hsu, "A hybrid particle swarm optimization for job shop scheduling problem," Computers & Industrial Engineering, vol. 51, no. 4, pp. 791-808, 2006.
24. [24] B. Z. Yao, C. Y. Yang, J. J. Hu, G. D. Yin, and B. Yu, "An improved artificial bee colony algorithm for job shop problem," in Applied Mechanics and Materials, 2010, vol. 26: Trans Tech Publ, pp. 657-660.
25. [25] T. Jiang and C. Zhang, "Application of grey wolf optimization for solving combinatorial problems: job shop and flexible job shop scheduling cases," Ieee Access, vol. 6, pp. 26231-26240, 2018.
26. [26] T. Jiang, "A hybrid grey wolf optimization for job shop scheduling problem," International Journal of Computational Intelligence and Applications, vol. 17, no. 03, p. 1850016, 2018.
27. [27] J. C. Bean, "Genetic algorithms and random keys for sequencing and optimization," ORSA journal on computing, vol. 6, no. 2, pp. 154-160, 1994.
28. [28] J. Jiang, R. Han, X. Meng, and K. Li, "TSASC: tree–seed algorithm with sine–cosine enhancement for continuous optimization problems," Soft Computing, pp. 1-20, 2020.
29. [29] J. Jiang, M. Xu, X. Meng, and K. Li, "STSA: A sine Tree-Seed Algorithm for complex continuous optimization problems," Physica A: Statistical Mechanics and its Applications, vol. 537, p. 122802, 2020.
30. [30] A. C. Cinar, "Training Feed-Forward Multi-Layer Perceptron Artificial Neural Networks with a Tree-Seed Algorithm," Arabian Journal for Science and Engineering, vol. 45, no. 12, pp. 10915-10938, 2020.
31. [31] A. C. Cinar, H. Iscan, and M. S. Kiran, "Tree-Seed algorithm for large-scale binary optimization," KnE Social Sciences, pp. 48-64, 2018.
32. [32] M. A. Sahman and A. C. Cinar, "Binary tree-seed algorithms with S-shaped and V-shaped transfer functions," International Journal of Intelligent Systems and Applications in Engineering, vol. 7, no. 2, pp. 111-117, 2019.
33. [33] A. C. Cinar and M. S. Kiran, "Similarity and logic gate-based tree-seed algorithms for binary optimization," Computers & Industrial Engineering, vol. 115, pp. 631-646, 2018.
34. [34] A. C. Cinar, S. Korkmaz, and M. S. Kiran, "A discrete tree-seed algorithm for solving symmetric traveling salesman problem," Engineering Science and Technology, an International Journal, vol. 23, no. 4, pp. 879-890, 2020.
35. [35] E. Taillard, "Benchmarks for basic scheduling problems," european journal of operational research, vol. 64, no. 2, pp. 278-285, 1993.