基于交叉熵算法求解多目标柔性作业车间调度问题  

Multi-objective flexible job shop scheduling problem based on cross entropy algorithm

作　　者：杨艳华 潘鑫[2] 张丽丽 姚立纲[3] YANG Yanhua;PAN Xin;ZHANG Lili;YAO Ligang(College of Engineering,Fujian Jiangxia University,Fuzhou 350108,China;College of Science,Tianjin University of Technology and Education,Tianjin 300222,China;College of Mechanical Engineering and Automation,Fuzhou University,Fuzhou 350116,China)

机构地区：[1]福建江夏学院工程学院,福建福州350108 [2]天津职业技术师范大学理学院,天津300222 [3]福州大学机械工程及自动化学院,福建福州350116

出　　处：《武汉大学学报（工学版）》2024年第4期497-508,共12页Engineering Journal of Wuhan University

基　　金：国家自然科学基金项目(编号:51775114);福建省自然基金项目(编号:2020J01937);天津市教委科研计划项目(编号:2022ZD013)。

摘　　要：柔性作业车间调度问题不仅要安排工序的加工顺序,还要选择当前工序所使用的机器,是一类灵活性和复杂性较高的NP(non-deterministic polynomial)-hard问题。以最小化最大完工时间、最小化总机器负荷、最小化最大机器负荷为目标,建立多目标优化模型,将非占优排序融入交叉熵算法,提出求解多目标柔性作业车间调度问题的交叉熵方法(cross-entropy method for multi-objective optimization,CEMO),以“随机分布筛”处理工序排列约束函数,确保采样点的可行性并提高收敛速率。对CEMO的机理分析表明,该方法可以利用非占优排序所得精英样本的引导作用,使收敛速度比应用交叉熵方法求解单目标问题更快。同时,针对最大完工时间优化时易出现的早熟现象,提出基于总机器负荷和最大机器负荷的机器分配预训练技术及采样矩阵提前停止更新技术,促进精英样本的进化。最后,通过数值实验验证了CEMO的机理,结果表明该方法可行,且具有收敛快、解的分布更广更均匀的优点。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 nondominated 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 nondominated 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.

关 键 词：柔性作业车间调度 交叉熵算法 多目标优化 非占优排序 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置] TP391[自动化与计算机技术—控制科学与工程]