一种求解作业车间调度问题的异步元胞遗传算法

摘要

The paper presented the mathematical model of Job-shop Scheduling Problem( JSP) and took the minimum makespan as its optimization goal. We proposed a new kind of asynchronous cellular genetic algo-rithm( acGA) by introducing an asynchronous update strategy in the cellular genetic algorithm. Then we ap-plied the proposed acGA and the simple genetic algorithm to the JSP examples and compared the results. The contrastive results showed that acGA had better search capability, faster convergence speed, and prefer-able stability than the simple genetic algorithm when solving the JSP examples. It proved that the proposed acGA is a feasible and effective algorithm for JSP.%以最快完工时间最少为目标建立了作业车间调度数学模型。将一种异步更新策略引入元胞遗传算法,提出了一种异步元胞遗传算法( acGA )。采用acGA和传统遗传算法求解作业车间调度实例,结果对比表明在求解作业车间调度问题时,acGA与sGA相比搜索能力更强,收敛速度更快,算法的稳定性也更好,表明acGA是一种求解JSP问题的有效算法。