柔性作业车间调度问题不仅要安排工序的加工顺序,还要选择当前工序所使用的机器,是一类灵活性和复杂性较高的NP(non-deterministic polynomial)-hard问题.以最小化最大完工时间、最小化总机器负荷、最小化最大机器负荷为目标,建立多目标优化模型,将非占优排序融入交叉熵算法,提出求解多目标柔性作业车间调度问题的交叉熵方法(cross-entropy method for multi-objective optimization,CEMO),以"随机分布筛"处理工序排列约束函数,确保采样点的可行性并提高收敛速率.对CEMO的机理分析表明,该方法可以利用非占优排序所得精英样本的引导作用,使收敛速度比应用交叉熵方法求解单目标问题更快.同时,针对最大完工时间优化时易出现的早熟现象,提出基于总机器负荷和最大机器负荷的机器分配预训练技术及采样矩阵提前停止更新技术,促进精英样本的进化.最后,通过数值实验验证了 CEMO的机理,结果表明该方法可行,且具有收敛快、解的分布更广更均匀的优点.
Multi-objective flexible job shop scheduling problem based on cross entropy algorithm
Flexible job-shop scheduling problem is a kind of NP(non-deterministic polynomial)-hard problem with high flexibility and complexity,which is related to the processing sequence and machines.A cross-entropy method for multi-objective optimization(CEMO)for multi-objective flexible job-shop scheduling problem is proposed by establishing multi-objective optimization model of minimizing the maximum completion time,the total machine load and the maximum machine load,and integrating the cross-entropy algorithm with non-dominated sorting.The random distribution sieve is used to deal with the constraint functions of process arrangement to ensure the feasibility of sampling points and improve the rate of convergence.The mechanism analysis of CEMO shows that this method can make use of the guiding effect of elite samples obtained by non-dominated sorting,and the convergence rate is faster than that of applying cross-entropy method to solve single objective problems.In view of the phenomenon of prematurity in the optimization of the maximum completion time,the machine allocation pre-training technology based on the total machine load and the maximum machine load and the sampling matrix advance stop update technology are proposed to promote the evolution of elite samples.Finally,the mechanism of CEMO method is verified by numerical experiments,and the numerical experiment results show that the method is feasible and has the advantages of fast convergence,wider and more uniform distribution of solutions.
NETL
NSTL
万方数据
