双链遗传算法在作业车间调度中的应用

Application of Diploid Genetic Algorithm in Job-Shop Scheduling Problem

针对简单遗传算法在解决作业车间生产调度问题时存在收敛效率低与过早收敛的局限,将一种改进的遗传算法——“双链遗传算法”应用于求解作业车间生产调度问题.与简单遗传算法相比,双链遗传算法在解决作业车间调度问题上,显著提高了搜索效率,还增强了避免早熟的能力.对双链遗传算法求解作业车间调度问题的某些策略和基本步骤作了简要的归纳和总结,编制了双链遗传算法求解作业车间调度问题的程序,通过调度例子测试表明了算法的有效性和可行性.

For the low efficiency and premature convergence of Sample Genetic Algorithm（SGA） application in job- shop scheduling problem（JSP）, an improved algorithm, diploid genetic algo- rithm（DGA） is presented to resolve JSP. Comparing with SGA, DGA, the DGA improves searching efficiency and has strong ability to avoid premature convergence. The strategies and basic steps of solving JSP by DGA are summarized and generalized, and the program is compiled. The result of DGA in JSP proves its efficiency and feasibility.