解并行多机提前/拖后调度问题的并行遗传算法  

Parallel Genetic Algorithm for Solving Parallel Multi-Machine Earliness/Tardiness Scheduling Problem

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

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

出　　处：《计算机工程与应用》2006年第20期10-12,共3页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:40405019);国家973基础研究发展规划资助项目(编号:2005cb321703);浙江省教委基金资助项目(编号:20051436)

摘　　要：为有效地解决带有公共交货期的非等同并行多机提前/拖后调度问题,设计了一种分段扩展排列编码的混合遗传算法,使遗传编码能同时反映调度方案和公共交货期,并对其初始种群产生、交叉和变异方法也进行了研究。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,并能适用于大规模非等同并行多机提前/拖后调度问题。In order to solve non-identical parallel machine earliness/tardiness scheduling problem,a hybrid genetic algorithm based on sectional extended permutation-coding scheme is suggested.The coding method can reflect the scheduling policy and common due date simultaneously,and these methods,such as the generation of the initial population,crossover and mutation,are also researched.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 efficient,and is advantageous over heuristic procedures and common genetic algorithms,and has much better parallel characteristics,and is fit for larger scale non-identical parallel machine earliness/tardiness scheduling problem.

关 键 词：并行多机 并行遗传算法 提前/拖后 调度问题 

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