摘要
将遗传算法与模拟退火算法相结合,提出了一种混合调度算法。该算法采用3种提高效率的策略:(1)采用基于机器的分段编码方式,使编码简单直观,并且编码空间小。(2)采用4-2选择代替常用的转轮选择方式,既保留了优秀个体又维持了群体多样性;(3)采用基于关键路径的邻域产生函数和变异算子,缩小了搜索邻域。实验表明该算法具有较高的求解质量和效率。
A mixed algorithm that combines genetic algorithm with-simulated annealing algorithm for a job shop scheduling problem is proposed. The algorithm takes three measures to improve efficiency： （ 1 ） A simple and obvious gene encoding scheme and its crossover are designed. （2） An effective selection operator, namely ＂4-2 selection＂, is used to keep the diversity of the population and good individuals. （3） The neighborhood search template that employs a critical path and blocks of operations is adopted to decrease the search area and improve the efficiency of the exploration. Numerical simulation demonstrates that with the framework of the newly designed genetic algorithm the NP-hard classic job shop scheduling problem can be efficiently solved with higher quality and that the optimization performance of EGA is superior to the algorithm reported in literature.
出处
《机械科学与技术》
CSCD
北大核心
2006年第3期317-321,共5页
Mechanical Science and Technology for Aerospace Engineering
基金
国家自然科学基金项目(50275078)
山东省自然科学基金项目(2004ZX14
2004ZX17)资助
关键词
遗传算法
模拟退火
作业调度
关键路径
genetic algorithm
simulated annealing
job shop scheduling
critical path
