解特殊工艺约束双目标调度问题的新遗传算法  

New Genetic Algorithm for Solving Bi-objective Scheduling Problem Subjected to Special Process Constraint

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

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

出　　处：《系统仿真学报》2009年第14期4235-4237,共3页Journal of System Simulation

基　　金：国家973基础研究发展规划资助项目(2005cb321703)

摘　　要：针对特殊工艺约束下非一致并行多机双目标调度问题,设计了一个双目标调度模型(BOSP)。进而基于遗传算法和免疫理论的思想,提出了新的遗传算法(IGA)。算法的编码采用了向量组编码方法,能有效地反映实际调度方案;免疫算子的引入,保证了种群的多样性和种群的质量,加快了算法收敛速度。仿真结果表明,算法是有效的,免疫算法的引入,使算法能较好地收敛到最优解,优于没有引入免疫算子的遗传算法,并能适用于解实际的此类调度问题。In order to solve the problem of non-identical parallel multi-machine scheduling subjected to special process constraint with the objectives of minimizing the maximum completion time （makespan） and minimizing the total tardiness penalty, a hi-objective scheduling model （BOSP） was designed, and then a new genetic algorithm （IGA） based on genetic algorithm and immune theory was proposed in order to effectively solve this model. A vector group encoding method was adopted in IGA to effectively reflect the virtual scheduling policy. Meantime, an immune operator was adopted in order to guarantee diversity of the population and quality of the population. Numerical experiments show that it is efficient, and can be better convergent to the optimal solution, and is superior to genetic algorithm without the immune operator. A much better prospect of application can be optimistically expected.

关 键 词：双目标调度 遗传算法 免疫算子 特殊工艺约束 

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