• 论文 •    

具有柔性加工时间的机器人制造单元调度问题改进遗传算法

晏鹏宇,车阿大,李鹏,杨乃定   

  1. 西北工业大学 管理学院,陕西西安710072
  • 出版日期:2010-02-15 发布日期:2010-02-25

Improved genetic algorithm for robotic cell scheduling problem with flexible processing times

YAN Peng-yu, CHE A-da, LI Peng, YANG Nai-ding   

  1. School of Management, Northwestern Polytechinical University, Xi'an 710072, China
  • Online:2010-02-15 Published:2010-02-25

摘要: 为克服传统遗传算法在求解具有柔性加工时间的机器人制造单元调度问题时易出现早熟收敛、冗余迭代等缺陷,提出了改进遗传算法。该算法采用基于工件搬运顺序的染色体编码,并根据调度问题特征,设计构造型启发式算法来生成初始种群,避免了大量不可行染色体的产生,提高了后续操作的优化质量。同时,在交叉变异操作中引入局部邻域搜索,通过对子代邻域的局部寻优提高了算法的收敛速度。最后,分别应用该算法和传统遗传算法求解六个基准案例,实验结果验证了该算法的有效性。

关键词: 遗传算法, 柔性加工时间, 机器人制造单元, 调度

Abstract: An improved Genetic Algorithm (GA) was proposed to overcome premature convergence and redundant iterations by using traditional GA to solve the scheduling problem in robotic cell with flexible processing time. This algorithm adopted the encoding scheme based on part moving sequence. According to the characterstics of this scheduling problem, a new constructive heuristic method was designed to generate initial populations which eliminated large amout of infeasible chromosomes and improved the solution quality in the subsequent operations. At the same time, a local search was introduced to improve the efficiency of algorithm in the crossover and mutation operations. Finally, the proposed algorithm was compared to the traditional GA by solving six benchmark problems. Computation results proved the effectiveness of the improved GA.

Key words: genetic algorithm, flexible processing times

中图分类号: