求解多目标混合流水车间调度的改进NSGA-Ⅱ

Improved NSGA-Ⅱalgorithm for hybrid flow shop scheduling problem with multi-objective

针对混合流水车间调度问题,以最小化能耗和最小化最大完工时间为求解目标,建立混合整数线性规划模型,提出求解该问题的改进快速非支配排序遗传算法(NSGA-Ⅱ)。算法染色体采用首阶段工件加工顺序码和设备分配码相结合的编码方式,最大程度确保算法在问题的整个解空间搜索Pareto前沿解。针对染色体编码设计了3种不同解码方法,其中两种解码方法与问题目标密切相关,用于引导算法搜寻方向;设计了一种贪婪变异算子,在提高种群多样性的同时兼顾算法的局部搜索能力。为确保Pareto前沿解集的分布性和收敛性,避免算法陷入局部最优,在采用精英保留策略的基础上提出一种全新的选择算子,并通过实验证明了该选择算子的有效性。为进一步节约能源,针对调度方案提出先右移再左移的调整策略,在不改变总完工时间的前提下大大节约了设备的待机和开关机能量。最后通过实验验证了改进NSGA-Ⅱ的有效性。

Aiming at the hybrid flow shop scheduling problem,a Mixed Integer Linear Programming(MILP)model was set up by taking the makespan and minimum energy consumption as the solving objectives,and an improved multi-objective NSGAⅡalgorithm was proposed to solve it.A novel chromosome coding method was put forward,which could ensure NSGA-Ⅱalgorithm search the whole solution space.Three decoding methods were designed,and two of them were close related with the objectives of the problem and guide the algorithm’s search direction.A greedy mutation operator was used here to improve algorithm’s local searching ability and an improved choice operator was proposed to ensure the variety of chromosome and avoid premature convergence.To reduce the energy consumption,an mobile strategy was proposed to cut down the standby energy consumption and turning-on/off energy consumption.Numerical experiments were carried out to evaluate the performance and efficiency of the proposed approach.