Dergiler / International Journal of Intelligent Systems and Applications in Engineering / 2019 / Cilt: 7 - Sayı: 1

An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem

Sayfa
13–18
DOI
—
🏛️Bu makalenin bibliyografik verileri ve tam metin bağlantısı DergiPark üzerinden sağlanmıştır.
DergiPark Kaydı ↗
✨

Yapay Zeka Hızlı Bakış & Çıkarımlar

AI Insight
⚡ TL;DR(1 Cümlede Hızlı Çıkarım)

The computational results validate the enhancements accomplished by the proposed selective exchange, and show the superiority of the proposed algorithm over the compared works in terms of solution quality, and validate its effectiveness.

📌 3 Maddede Bu Makale

🎯
Amaç & Hipotez:This work presents an effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem with the objective of makespan minimization (GA-CPG-GT).
📊
Temel Bulgular & Veri:The proposed approach is tested on 55 benchmarks, with the proposed selective exchange, and without it using the random one, and also compared with other 5 similar works reported in the literature.
💡
Sonuç & Katkı:The computational results validate the enhancements accomplished by the proposed selective exchange, and show the superiority of the proposed algorithm over the compared works in terms of solution quality, and validate its effectiveness.
🔬Tür:Araştırma Makalesi
📍Kapsam:Genişletilmiş Akademik Örneklem
⚙️Değişkenler:Alan Parametreleri

Özet

This work presents an effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem with the objective of makespan minimization (GA-CPG-GT). Even though passing important traits from parents to offspring is known to be an important feature of any uniform crossover operator, most of the proposed operators adopt random exchange of genetic materials between parents; this is probably due to the fact that it is tricky to identify the genetic materials that hold the important traits. For that reason, in this work, a new selective exchange of genetic materials is proposed. In the proposed approach, at first, the genetic materials that hold the important traits are identified according to some domain specific information provided by the critical paths of the parents, and then the exchange is made on favor of them. The properties of critical path are usually utilized by the local search methods such as tabu search and simulating annealing; however, in this work, they are utilized in the global search method GA during the crossover operator. The implications of the proposed approach are investigated using the Giffler and Thompson crossover operator, which is a uniform crossover combined with the G&T algorithm. The proposed approach is tested on 55 benchmarks, with the proposed selective exchange, and without it using the random one, and also compared with other 5 similar works reported in the literature. The computational results validate the enhancements accomplished by the proposed selective exchange, and show the superiority of the proposed algorithm over the compared works in terms of solution quality, and validate its effectiveness.

🔖

Bu Makaleye Atıf Yap

KURDİ, M. (2019). An effective genetic algorithm with a critical-path-guided Giffler and Thompson crossover operator for job shop scheduling problem. International Journal of Intelligent Systems and Applications in Engineering, Cilt: 7 - Sayı: 1, 13–18. https://ajindex.com/articles/161613

Kaynakça (9)

  1. J. Carlier, E. Pinson, “An algorithm for solving the job-shop problem”, Manag Sci, vol. 35, no. 2, pp. 164-176, 1989. https://doi.org/10.1287/mnsc.35.2.164
  2. J. Adams, E. Balas, D. Zawack, “The shifting bottleneck procedure for job shop scheduling”, Manag Sci, vol. 34, no. 3, pp. 391-401, 1988. https://doi.org/10.1287/mnsc.34.3.391
  3. J.H. Blackstone, D.T. Phillips, G.L. Hogg, “A state-of-the-art survey of dispatching rules for manufacturing job shop operations”, Int J Prod Res, vol. 20, no. 1, pp. 27-45, 1982. https://doi.org/10.1080/00207548208947745
  4. T. Satake, K. Morikawa, K. Takahashi, N. Nakamura, “ Simulated annealing approach for minimizing the makespan of the general job-shop”,Int J Prod Econ, pp. 60–61, pp. 515-522, 1999. https://doi.org/10.1016/S0925-5273(98)00171-6
  5. E. Nowicki, C. Smutnicki, “An advanced tabu search algorithm for the job shop problem”, J Sched, vol. 8, no. 2, pp. 145-159, 2005. https://doi.org/10.1007/s10951-005-6364-5
  6. N. Fığlalı, C. Özkale, O. Engin, A. Fığlalı, “Investigation of ant system parameter interactions by using design of experiments for job-shop scheduling problems”, Comput Ind Eng, vol. 56, no. 2, pp. 538-559, 2009. https://doi.org/10.1016/j.cie.2007.06.001 L. Asadzadeh, “A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy”, Comput Ind Eng, vol 102, pp. 359-367, 2016. https://doi.org/10.1016/j.cie.2016.06.025 K. &. R. C. Rameshkumar, “A novel discrete PSO algorithm for solving job shop scheduling problem to minimize makespan”. In IOP Conference Series: Materials Science and Engineering, vol. 310, no. IOP Publishing, 2018. https://doi.org/10.1088/1757-899X/310/1/012143 [9] Atay, Y., & Kodaz, H. “Optimization of job shop scheduling problems using modified clonal selection algorithm”. Turk J Elec Eng & Comp Sci, vol. 22, no. 6, pp. 1528-1539, 2014. https://doi.org/10.3906/elk-1212-26
  7. Dao, T. K., Pan, T. S., & Pan, J. S.“Parallel bat algorithm for optimizing makespan in job shop scheduling problems”, J Intell Manuf, vol. 29, no. 2, pp. 451-462, 2018. https://doi.org/10.1007/s10845-015-1121-x
  8. G. Zobolas, C. Tarantilis, G. Ioannou, “Exact, heuristic and meta-heuristic algorithms for solving job shop scheduling problems”, F. Xhafa, A. Abraham (Eds.), Metaheuristics for scheduling in industrial and manufacturing applications, Springer, Berlin (2008), pp. 1-40 https://doi.org/10.1007/978-3-540-78985-7_1
  9. A.S. Jain, S. Meeran, “Deterministic job-shop scheduling: past, pres