Memory based Lamarckian evolutionary algorithm for job shop scheduling problem

被引：1
|
作者：
Xia Z.-C. [1 ,2 ]
Liu F. [1 ,2 ]
Gong M.-G. [2 ,3 ]
Qi Y.-T. [1 ,2 ]
机构：
[1] School of Computer Science and Technology, Xidian University
[2] Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education of China, Xidian University
[3] Institute of Intelligent Information Processing, Xidian University
来源：
Ruan Jian Xue Bao/Journal of Software | 2010年 / 21卷 / 12期
关键词：
Job shop scheduling; Lamarckian evolution; Local search; Memory-base; Multi-population genetic algorithm; Simulated annealing;
D O I：
10.3724/SP.J.1001.2010.03687
中图分类号：
学科分类号：
摘要：
Compared with the Genetic Algorithm, a multi-population genetic algorithm has an enhancement in performance, but for a job shop scheduling problem, which has a lot of local optima, it also has the shortcomings of an easy-to-fall into local optima and a poor ability of local search. Therefore, an effective algorithm is proposed to solve job shop scheduling problem. The proposed algorithm, based on multi-population genetic algorithm, involves the strategy of memory-base and a mechanism of the Lamarckian evolution. Not only does the memory-base make individuals between sub-populations exchange information, but it can maintain the diversity of the population. The local search operator, based on Lamarckian evolution, is adupted to enhance the individual's ability of local search. The simulated annealing algorithm that has a stronger ability to jump out local optima than the genetic algorithm is used, thus, alleviated the problem and enhances the performance of the algorithm for job shop scheduling. The experimental results on the well-known benchmark instances show the proposed algorithm is very effective in solving job shop scheduling problems. © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：3082 / 3093
页数：11
相关论文
共 13 条
  • [1] Yahyaoui A., Fnaiech F., Recent trends in intelligent job shop scheduling, Proc. of the 2006 1st IEEE Int'l Conf. on E-Learning in Industrial Electronics, pp. 191-195, (2006)
  • [2] Watanabe M., Ida K., Gen M., A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem, Computers and Industrial Engineering, 48, 4, pp. 743-752, (2005)
  • [3] Krishna K., Ganeshan K., Ram D.J., Distributed simulated annealing algorithms for job shop scheduling, IEEE Trans. on Systems, Man and Cybernetics, 25, 7, pp. 1102-1109, (1995)
  • [4] Wan G.H., Wan F., Job shop scheduling by taboo search with fuzzy reasoning, Proc. of the IEEE Int'l Conf. on Systems, Man and Cybernetics, pp. 1566-1570, (2003)
  • [5] Li J.P., Uwe A., Explicit learning: An effort towards human scheduling algorithms, Proc. of the 1st Multidisciplinary Int'l Conf. on Scheduling: Theory and Applications, pp. 240-241, (2003)
  • [6] Chen X., Kong Q.S., Wu Q.D., Hybrid algorithm for job-shop scheduling problem, Proc. of the 4th World Congress on Intelligent Control and Automation, pp. 1739-1743, (2002)
  • [7] Cantu-Paz E., Markov chain models of parallel genetic algorithms, IEEE Trans. on Evolutionary Computation, 4, 3, pp. 216-226, (2000)
  • [8] Salwani A., Uwe A., Edmund B., Aniza D., Qu R., Investigating a hybrid metaheuristic for job shop rescheduling, Proc. of the 3rd Australian Conf. on Artificial Life, pp. 357-368, (2007)
  • [9] Chen H., Flann N.S., Watson D.W., Parallel genetic simulated annealing: A massively parallel SIMD algorithm, IEEE Trans. on Parallel and Distributed Systems, 9, 2, pp. 126-136, (1998)
  • [10] Essafi I., Mati Y., Dauzere-Peres S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers and Operations Research, 35, 8, pp. 2599-2616, (2008)
12