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

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

针对特殊工艺约束下非一致并行多机双目标调度问题,设计了一个双目标调度模型(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.