摘要
为克服传统遗传算法解决车间作业调度问题的局限性,综合遗传算法和局部搜索的优点,提出一种改进的遗传算法。为基于工序的编码提出了一种新的POX交叉算子。同时,为克服传统遗传算法在求解车间作业调度问题时的早熟收敛,设计了一种子代交替模式的交叉方式,并运用局部搜索改善交叉和变异后得到的调度解,将提出的改进遗传算法应用于MuthandThompson基准问题的实验运行,显示了该算法的有效性。
To overcome the limitations of traditional Genetic Algorithm (GA) when solving the problem of job-shop scheduling, an improved GA was proposed by taking advantages of traditional GA and local search. A new crossover operator, Precedence Operation Crossover (POX), for operation-based representation was created. To avoid premature convergence, which appeared in the course of solving job-shop scheduling by applying conventional GA. The concept of an improved generation alteration model was introduced. After a schedule was obtained, a local search heuristic was applied to improve the solution. Its efficiency was validated by applying improved GA to Muth and Thompson's benchmark problem.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2004年第8期966-970,共5页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金资助项目(50105006
50305008)。~~
关键词
车间作业调度
遗传算法
交叉算子
局部搜索
job-shop scheduling
genetic algorithm
crossover operator
local search
