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

针对非一致并行机环境下特殊工艺约束提前/拖后调度问题,设计了一个基于向量组编码的新遗传算法,此算法的编码方法简单,能有效地反映实际调度方案,即清楚地反映出每机器加工产品的代号和顺序.引入浓度概念,对种群中浓度高的个体进行抑制,从而增加群体多样性,同时,利用爬山算法对种群中个体进行局部搜索,提高了种群质量,加快了收敛速度.仿真结果表明,此算法是有效的,适用于解实际的此类调度问题.

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

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.