Optimization of job shop scheduling problems using modified clonal selection algorithm

Artificial immune systems (AISs) are one of the artificial intelligence techniques studied a lot in recent years. AISs are based on the principles and mechanisms of the natural immune system. In this study, the clonal selection algorithm, which is used commonly in AISs, is modified. This algorithm is applied to job shop scheduling problems, which are one of the most difficult optimization problems. For applying application results to the optimum solution, parameter values giving the optimum solution are determined by analyzing the parameters in the algorithm. The obtained results are given in detail in the tables and figures. The best makespan values are reached in 7 out of 10 test problems (FT06, LA01, LA02, LA03, LA04, LA05, and ABZ6). Reasonable makespan values are reached for the remaining 3 problems (FT10, LA16, and ABZ5). The obtained results demonstrate that the developed system can be applied successfully to job shop scheduling problems.

Anahtar Kelimeler:

Artificial immune system, clonal selection algorithm, job shop scheduling, optimization

Optimization of job shop scheduling problems using modified clonal selection algorithm

Keywords:

Artificial immune system, clonal selection algorithm, job shop scheduling, optimization,

PDF

___

E. Yenig¨un, At¨olye tipi ¨uretimde teslim tarihi verilmesi, MSc, Sakarya University, Sakarya, Turkey, 2010 (in Turkish).
J.M. Moore, “An n job, one machine sequencing algorithm for minimizing the number of late jobs”, Management Science, Vol. 15, pp. 102–109, 1968.
T. Gonzalez, S. Sahni, “Flow shop and job shop schedules: complexity and approximation”, Operation Research, Vol. 26, pp. 36–52, 1978.
E.M. Arkin, E.B. Silverberg, “Scheduling jobs with fixed start and end times”, Discrete Applied Mathematics, Vol. 18, pp. 1–8, 1987.
V. Valls, M. Perez, M. Quintanilla, “A tabu search approach to machine scheduling”, European Journal of Opera- tional Research, Vol. 106, pp. 277–300, 1998.
M.F. Ta¸sgetiren, ˙I.H. Cedimo˘glu, B. ˙Ince, “Teslim tarihi olu¸sturma y¨ontemleri ¨uzerine bir kar¸sıla¸stırma”, 17th National Conference on Operational Research and Industrial Engineering (YA/EM’95), Middle East Technical University, Ankara, Turkey, 1995 (in Turkish).
M.T. Jensen, T.K. Hansen, “Robust solutions to job shop problems”, Proceedings of the 1999 Congress on Evolu- tionary Computation, Vol. 2, pp. 1138–1144, 1999.
F. Geyik, ˙I.H. Cedimo˘glu, “At¨olye tipi ¸cizelgelemede kom¸suluk yapılarının tabu arama tekni˘gi ile kar¸sıla¸stırılması”, Politeknik Dergisi, Vol. 4, pp. 95–103, 2001 (in Turkish).
M. Watanabe, K. Ida, M. Gen, “A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem”, Computers & Industrial Engineering, Vol. 48, pp. 743–752, 2005.
M. S¸evkli, M.M. Yenisey, “At¨olye tipi ¸cizelgeleme problemleri i¸cin par¸cacık s¨ur¨u optimizasyonu y¨ontemi”, ˙IT ¨U Dergisi D: M¨uhendislik, Vol. 5, 58–68, 2006 (in Turkish).
S. Biro˘gul, U. G¨uven¸c, “Genetik algoritma ile ¸c¨oz¨um¨u ger¸cekle¸stirilen at¨olye ¸cizelgeleme probleminde ¨ur¨un sayısının etkisi”, Akademik Bili¸sim ’07, K¨utahya, Turkey, pp. 613–619, 2007 (in Turkish).
M. Gholami, M. Zandieh, “Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop”, Journal of Intelligent Manufacturing, Vol. 20, pp. 481–498, 2009.
A.A. Bondal, Artificial immune systems applied to job shop scheduling, MSc, Ohio University, Athens, OH, USA, 2008.
A. Alada˘g, Tekrar i¸slemeli esnek at¨olye tipi ¸cizelgeleme problemi i¸cin yapay ba˘gı¸sıklık sistemi ile bir ¸c¨oz¨um yakla¸sımı, MSc, Eski¸sehir Osmangazi University, Eski¸sehir, Turkey, 2010.
M. Akhshabi, M. Akhshabi, J. Khalatbari, “Solving flexible job-shop scheduling problem using clonal selection algorithm”, Indian Journal of Science and Technology, Vol. 4, pp. 1248–1251, 2011.
D.K. Mahapatra, Job shop scheduling using artificial immune system, BSc, National Institute of Technology, Rourkela, India, 2012.
A. Guldali, Seri i¸s-akı¸slı at¨olye ¸cizelgelemesinde sezgisel teknikler, MSc, Gazi University, Ankara, Turkey, 1990 (in Turkish).
T.F. Ang, T.C. Ling, K.K. Phang, “Adaptive QoS scheduling in a service-oriented grid environment”, Turkish Journal of Electrical Engineering & Computer Science, Vol. 20, pp. 413–424, 2012.
R. Samet, O.F. Duman, “Behaviors of real-time schedulers under resource modification and a steady scheme with bounded utilization”, Turkish Journal of Electrical Engineering & Computer Science, Vol. 18, pp. 1115–1130, 2010.
L.N. de Castro, F.J. Von Zuben, “Immune and neural network models: theoretical and empirical comparisons”, International Journal of Computational Intelligence and Applications, Vol. 1, pp. 239–257, 2001.
L.N. de Castro, F.J. Von Zuben, “The clonal selection algorithm with engineering applications”, Workshop Pro- ceedings of GECCO, pp. 36–37, 2000.
A. Chaudhuri, K. De, “Job scheduling problem using rough fuzzy multilayer perception neural networks”, Journal of Artificial Intelligence: Theory and Application, Vol. 1, pp. 4–19, 2010.
G.C. Luh, C.H. Chueh, “Job shop scheduling optimization using multi-modal immune algorithm”, Lecture Notes in Computer Science, Vol. 4570, pp. 1127–1137, 2007.
A. Udomsakdigool, V. Kachitvichyanukul, “Multiple colony ant algorithm for job-shop scheduling problem”, Inter- national Journal of Production Research, Vol. 46, pp. 4155–4175, 2008.
J. K¨aschel, T. Teich, G. K¨obernik, B. Meier, “Algorithms for the job shop scheduling problem: a comparison of different methods”, European Symposium on Intelligent Techniques, pp. 3–4, 1999.