摘要
作业车间调度问题是最困难的组合优化问题之一,也是计算机集成制造系统中的一个关键环节,在实际生产中具有广泛应用。为此,提出了双倍体遗传算法。该算法提供了一种记忆以前有用的基因块的功能,保留了某些低适应度染色体中的一些局部基因块,构成最优解中的基因片段,提高遗传算法的适应能力。与已有算法相比,基于双倍体遗传算法的作业车间调度方法,显著提高了搜索效率,改进了收敛性能。
Job-shop Scheduling Problem (JSP) is one of the most difficult combinatorial optimization problems. It is one of the most important links on CIMS and widely applied to the engineering. This paper proposes a double chromosomes genetic algorithm for job-shop scheduling problems. Because the function remembering the useful gene pieces is provided, and some gene pieces of chromosomes with lower fitness to form the gene pieces of optimal solution are kept, the adaptation of algorithm is increased. Compared with the existing algorithms, the efficiency of search is increased and the convergence is improved with the double chromosomes genetic algorithm.
基金
国家自然科学基金资助项目(60374056)
国家863/CIMS主题资助项目(2002AA412610)
浙江省科技计划资助项目(012047)。~~
关键词
生产调度
作业车间调度
遗传算法
组合优化
production scheduling
job-shop scheduling
genetic algorithm
combinatorial optimization
