解特殊工艺约束下提前／拖后调度问题的新遗传算法  

A New Genetic Algorithm for Solving Earliness/Tardiness Scheduling Problem Subjected to Special Process Constraint

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

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

出　　处：《数学的实践与认识》2008年第16期18-24,共7页Mathematics in Practice and Theory

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

摘　　要：针对非一致并行机环境下特殊工艺约束提前/拖后调度问题,设计了一个基于向量组编码的新遗传算法,此算法的编码方法简单,能有效地反映实际调度方案,即清楚地反映出每机器加工产品的代号和顺序.引入浓度概念,对种群中浓度高的个体进行抑制,从而增加群体多样性,同时,利用爬山算法对种群中个体进行局部搜索,提高了种群质量,加快了收敛速度.仿真结果表明,此算法是有效的,适用于解实际的此类调度问题.In order to solve the problem of earliness/tardiness scheduling subjected to special process constraint on non-identical parallel machines more efficiently, a new genetic algorithm based on vector group coding method is presented. The algorithm shows the following advantages： its coding method is simple and can effectively reflect the virtual scheduling policy, which can vividly reflect the numbers and sequences of these processed products from every machine. A concentration concept is adopted to increase varieties of population. Meantime, a climbing method is adopted to adjust local solutions of population to improve qualities of solutions and furthermore accelerate the algorithm＇s convergence. The computational results show that it is effective, and has a better prospect of application.

关 键 词：遗传算法 提前/拖后 特殊工艺约束 调度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]