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

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

作　　者：高家全[1] 王雨顺[2] 何桂霞[1] 

机构地区：[1]浙江工业大学之江学院,杭州310024 [2]南京师范大学数学与计算机科学学院,南京210097

出　　处：《计算机工程与应用》2007年第2期15-17,28,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(40405019);浙江省教委基金(20051436)。

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

关 键 词：并行多机 并行遗传算法 提前/拖后 调度问题 不同交货期窗口 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]