• 论文 •    

采用多个体交叉的遗传算法求解作业车间问题

杨晓梅,曾建潮   

  1. 太原重型机械学院系统仿真与计算机应用研究所,山西太原030024
  • 出版日期:2004-09-15 发布日期:2004-09-25

Multi-individual-crossover genetic algorithm for job shop scheduling problem

YANG Xiao-mei, ZENG Jian-chao   

  1. Div. of System Simulation and Computer Application,Taiyuan Heavy Machinery Inst., Taiyuan030024, China
  • Online:2004-09-15 Published:2004-09-25

摘要: 为改善目前求解Job-Shop问题中的遗传算法的性能,加快搜索最优调度解的速度,首先分析了目前Job-Shop问题自身的求解难点和遗传算法的特点,并借鉴生物学的依据,提出了多个体交叉的遗传算法。该算法在遗传过程中采用多个体遗传算子,充分利用个体的优良性质,对不可行调度解根据多个体修补原则进行修正,可保证遗传后代的合法性和多样性,能够加快最优调度解的搜索时间。仿真结果充分证明了该算法的有效性。

关键词: 遗传算法, 作业车间调度问题, 多个体交叉

Abstract: To improve the performance of the existing genetic algorithms for Job-shop scheduling problem and speed up searching fpr the optimal scheduling solution, the difficulty of the Job-shop scheduling problem and the characteristics of genetic algorithm were analyzed firstly. Then a multi-individual-crossover genetic algorithm for the Job-shop scheduling problem was presented based on of biology. Multi-individual-crossover genetic operators were introduced to make full use of the excellent quality of the individual. In addition, multi-individual remedy principle was used to revise unfeasible scheduling solutions. Therefore, it not only ensured validity and diversification of the evolving descendants, but also reduced searching time of optimal schedule. The simulation results validated the effectiveness of the proposed algorithm.

Key words: genetic algorithm, job-shop scheduling problem

中图分类号: