计算机工程 ›› 2009, Vol. 35 ›› Issue (5): 188-190.doi: 10.3969/j.issn.1000-3428.2009.05.065

• 人工智能及识别技术 • 上一篇    下一篇

一种求解单件车间调度问题的单亲遗传算法

刘胜辉,张淑丽,王 波,滕春贤   

  1. (哈尔滨理工大学软件学院,哈尔滨150080)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-03-05 发布日期:2009-03-05

Partheno Genetic Algorithm for Solving Job-shop Scheduling Problem

LIU Sheng-hui, ZHANG Shu-li, WANG Bo, TENG Chun-xian   

  1. (School of Software, Harbin University of Science and Technology, Harbin 150080)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-03-05 Published:2009-03-05

摘要: 针对单件车间调度问题,设计一种基于整数编码的单亲遗传算法。该算法既具有单亲遗传算法运算量小、不存在“早熟收敛”现象等优点,在编码中又体现了单件车间调度的“保序性”等工艺约束条件,增强了调度算法的整体性能。对不同规模的FT类问题的仿真结果表明,该算法的收敛速度随着问题规模的增大而加快,并在求解单件车间调度问题时能得到稳定的满意解。

关键词: 单件车间调度, 遗传算法, 整数编码, 收敛速度

Abstract: A Integer Coded Partheno Genetic Algorithm(IPGA) is designed for Job-Shop Scheduling Problem(JSSP). This algorithm strengthens the unitary capability of scheduling algorithm, not only has the virtue of PGA, such as small calculation capacity, no immature convergence and so on, but also incarnates technics constraint condition in coding, such as keeping job shop scheduling sequence. Considering different sizes of FT emulation results problems show that the convergence expedites as size extends, and can give good stable solutions for solving job shop problems.

Key words: job-shop scheduling, genetic algorithm, integer coding, convergence speed

中图分类号: