改进灰狼算法求解多目标柔性作业车间调度问题

Improved Grey Wolf Optimisation for Solving Multi-objective Flexible Job-shop Scheduling Problems

柔性作业车间调度问题(Flexible Jobshop Scheduling Problem,FJSP)是经典的NP-hard(Non-deterministic Polynomial-time hard)问题,针对该复杂问题,需要建立一个多目标的数学模型,采用灰狼优化算法对柔性作业车间的加工完成时间、总耗能和总机器负荷这三个目标进行优化,以加工完成时间、总耗能和总机器负荷作为研究目标。灰狼优化算法(GWO)是一种具有较高的寻优精度和收敛速度的算法,在此基础上对灰狼优化算法的初始化种群进行改进,为了使灰狼算法适用于多目标问题,与非支配排序遗传算法结合,引入非支配排序与拥挤度的概念,用于灰狼算法对种群的更新。对柔性作业车间调度算例进行测试,结果表明改进的灰狼算法针对多目标柔性作业车间调度可以找到最优解,以较少的迭代次数找到最小加工时间、最小总耗能及最小总机器负荷,对车间调度问题进行了优化。

Flexible job-shop scheduling problem(FJSP)is a classical NP-hard problem.For this complex problem,a multi-objective mathematical model is required.This paper proposes to use Grey Wolf optimisation(GWO)algorithm to optimise the three objectives of machining completion time,total energy consumption and total machine load for the flexible job-shop.GWO algorithm is characterised by high optimisation finding accuracy and fast convergence.On this basis,the initialised population of GWO algorithm is improved.In order to make the GWO algorithm applicable to the multi-objective problem,it is combined with the non-dominated sorting genetic algorithm,and the concepts of non-dominated sorting and congestion are introduced for the update of the population by the grey wolf algorithm.The flexible job-shop scheduling algorithm example is tested and the results show that the improved GWO algorithm can find the optimal solution for the multi-objective flexible job-shop scheduling.It finds the minimum processing time,the minimum total energy consumption and the minimum total machine load with fewer iterations,and optimises the shop scheduling problem.