特殊工艺约束并行多机双目标调度问题的研究  

Research on bi-objective scheduling problem subjected to special process constraint on parallel machines

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

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

出　　处：《计算机工程与应用》2008年第32期197-199,202,共4页Computer Engineering and Applications

基　　金：国家重点基础研究发展规划(973)(the National Grand Fundamental Research 973 Program of China under Grant No．2005cb321703)。

摘　　要：针对在特殊工艺约束下,非等同并行多机总完工时间最小和总拖后惩罚最小双目标调度问题(BOSP),设计了一个双目标调度模型,进而构造了一个基于向量组编码的遗传算法。此算法的编码方法简单,能有效地反映实际调度方案,收敛速度快。同时为了更好地适应调度实时性和解大型此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法。仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性,并能适用于解大型此类调度问题。The problem of non-identical parallel multi-machine scheduling subjected to special process constraint with the objectives of minimizing the total completion time and the total tardiness penalty（BOSP） is considered.To BOSP,a hi-objective scheduling model is presented in this paper,and a parallel genetic algorithm based on a vector group coding method is also constructed in order to effectively solve this model.lts coding method is simple and can effectively reflect the virtual scheduling policy and has better convergence.Meantime,under the mode of master-slave control networks,parallel genetic algorithm is applied in order to adapt to lager scale and real-time scheduling problems.Numerical experiments show that it is efficient,and is better than the common genetic algorithm,and has the better parallel efficiency.A much better prospect of application can be optimistically expected.

关 键 词：双目标 调度 特殊工艺约束 并行机 并行遗传算法 

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