基于时间递推建模及交叉熵算法求解柔性作业车间调度问题

Time recursive modeling and cross entropy algorithm for flexible job shop scheduling problem

针对以最小化最大完工时间为目标的柔性作业车间调度问题,通过分析作业完成时间的递推关系,发现通常使用的工序编码对解的表示不唯一影响优化效率,提出了一种新的模型刻画和与之相应的改进交叉熵算法。通过建立基于甘特图的解的归总表示,提高概率分布矩阵的收敛速度;引入随机分布筛,确保采样的可行性;以按概率切换的方式将传统交叉熵算法与两阶段优化方法融合,提高收敛速度的同时保证采样分布的广泛性。对典型算例进行的仿真实验表明,新模型解的归总表示对于提高收敛速度有显著作用,提出的算法能有效求解柔性作业车间调度问题。

Aiming at Flexible Job-shop Scheduling Problem(FJSP)with the objective of minimizing the maximum completion time,the non-uniqueness of process coding affects the efficiency of optimization computation through the recurrence relation of job completion time.Consequently,a new model and the corresponding cross entropy algorithm were proposed.The unified representation of solutions based on Gantt chart was established to improve the convergence speed of probability distribution matrix.Random distribution screen was introduced to ensure the feasibility of sampling.By means of stochastic switching,two stage method and cross entropy method were combined to speed up the solution process,and at the same time ensure the universality of solution distribution.Numerical results of typical examples showed that the new model had a significant effect on the convergence speed,and the hybrid algorithm could solve FJSP efficiently.