解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。

Parallel genetic algorithm for solving parallel machine scheduling problem with different due windows

In order to solve non-identical parallel machine earliness/tardiness scheduling problem with different due windows,a hybrid genetic algorithm based on sectional coding is suggested.The coding method,on one hand,can effectively reflect the virtual scheduling policy,which can vividly reflect the distributed sequences of these produced jobs from every machine every day.On the other hand,a heuristic algorithm with combining priority rule with best-fit rule is adopted to adjust its local solutions to speed its convergence.Considering the requirements of adapting it to this kind of lager scale problem and real-time scheduling,it is parallelly implemented under the mode of master-slave control networks.The computational results show that it is effficient,and is advantageous over common genetic algorithms,and has much better parallel characteristics,and is fit for larger scale non- identical parallel machine earliness/tardiness scheduling problem with different due windows.