Discrete differential evolution algorithm for the job shop scheduling problem

ABSTRACT

Differential Evolution (DE) Algorithm is a new evolutionary computation algorithm with rapid convergence rate. However, it does not perform well on dealing with job shop scheduling problems that have discrete decision variables. To remedy this, a Discrete Differential Evolution (DDE) Algorithm with special crossover and mutation operators is proposed to solve this problem. Under the skeleton of DE algorithm, The DDE algorithm inherits the advantage of rapid convergence rate. The experimental results on the well-known benchmark instances show the proposed algorithm is efficient in solving Job Shop Scheduling Problem

REFERENCES

• 1: Christos Dimopoulos and Ali M. S. Zalzala. Recent developments in evolutionary computation for manufacturing optimization: problems solutions and comparisons. IEEE transactions on evolutionary computation. vol.4, no.2, July 2000, PP.93--113.
• 2: Krishna K., Ganeshan K., Ram D.J. Distributed simulated annealing algorithms for job shop scheduling. IEEE Transactions on Systems, Man and Cybernetics. vol. 25, Issue.7, 1995, PP.1102--1109.
• 3: Guohua Wan, Feng Wan. Job shop scheduling by taboo search with fuzzy reasoning. IEEE International Conference on Systems, Man and Cybernetics, 2003. vol.2, 2003, PP.1566--1570.
• 4: Masato Watanabe , Kenichi Ida , Mitsuo Gen, A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem, Computers and Industrial Engineering, v.48 n.4, p.743-752, June 2005 [doi>10.1016/j.cie.2004.12.008]
• 5: Chen xiong, Kong qingsheng, and Wu qidi. Hybrid algorithm for job-shop scheduling problem. In: Proceedings of the 4th World Congress on Intelligent Control and Automation. 2002.
• 6: Tamaki H, Nishikawa Y. A parallel genetic algorithm based on neighborhood model and its application to the job shop scheduling. In: Parallel Problem Solving from nature II, Elsevier Science, 1992, PP.573--582.
• 7: Andreas C. Nearchou , Sotiris L. Omirou, Differential evolution for sequencing and scheduling optimization, Journal of Heuristics, v.12 n.6, p.395-411, December 2006 [doi>10.1007/10732-006-3750-x]
• 8: Nasimul Noman and Hitoshi Iba. Accelerating differential evolution using an adaptive local search. IEEE transaction on evolutionary computation. vol.12, no.2, February 2008, PP.107--125.
• 9: Fatih Tasgetiren. M, Quan-Ke Pan, Suganthan, P.N. Yun-Chia Liang. A Discrete Differential Evolution Algorithm for the No-Wait Flowshop Scheduling Problem with Total Flowtime Criterion. Computational Intelligence in Scheduling, 2007. SCIS '07. IEEE Symposium on 1--5 April 2007 Page(s):251 --- 258.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms

Keywords:
immune memory clonal selection., job-shop scheduling, neighborhood search, scheduling code