摘要
为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2007年第2期15-17,28,共4页
Computer Engineering and Applications
基金
国家自然科学基金资助项目(40405019)
浙江省教委基金(20051436)。
关键词
并行多机
并行遗传算法
提前/拖后
调度问题
不同交货期窗口
parallel machine
parallel genetic algorithm
earliness/tardiness
scheduling problem
different due windows
