一种求解多目标柔性JSP的正交遗传算法

Multi-objective Orthogonal Genetic Algorithm for Flexible Job-shop Scheduling Problems

针对柔性作业生产调度问题的特点,提出一种新的多目标正交遗传算法。算法主要特点包括:提出一种基于SPEA改进的个体适应值计算方法,该方法回避了小生境参数设置的难题,且具有更强的相似个体区分能力;设计一种新的基于正交设计的多个体交叉算子,该算子既能增强算法搜索在Pareto前沿均匀分布非劣解的能力,也可提高算法全局寻优的能力;给出一种基于历史搜索信息和变量区间划分的局部解空间跳出机制,以避免算法早熟和提高搜索效率。实验结果表明该算法应用于柔性多目标作业生产调度问题,具有较强的搜索效率和求解性能。

A new multi-objective genetic algorithm based on orthogonal design was proposed for flexible job shop scheduling problems with multiple objectives. Firstly, a new method for calculating fitness of individuals was introduced. The method was an improvement of SPEA, and relied on no niching or crowding parameters while was of greater capability in differentiating alike individuals than SPEA. Secondly, a new multi-parents crossover operator based on orthogonal design was proposed. This operator not only drove the algorithm towards solutions distributed evenly on the Pareto front, but also helped improving the capability of searching the global space effectively. Thirdly, a local solution scope outrunning mechanic utilizing historical searching information and adopting variable zone partitioning technique was designed to avoid premature and to improve efficiency. Experimental results show that, the algorithm presented could produce well-distributed and high-quality solutions in multi-objective flexible job shop scheduling problems.