一类解决车间调度问题的遗传退火算法

将遗传算法与模拟退火算法相结合,提出了一种混合调度算法。该算法采用3种提高效率的策略:(1)采用基于机器的分段编码方式,使编码简单直观,并且编码空间小。(2)采用4-2选择代替常用的转轮选择方式,既保留了优秀个体又维持了群体多样性;(3)采用基于关键路径的邻域产生函数和变异算子,缩小了搜索邻域。实验表明该算法具有较高的求解质量和效率。

A Classic Genetic Annealing Algorithm for Job Shop Scheduling

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.