超启发式交叉熵算法求解分布式装配柔性作业车间调度问题

本文针对一类新型两阶段分布式装配柔性作业车间调度问题(DAFJSP),建立问题模型,以最小化最大完工时间为优化目标并提出一种超启发式交叉熵算法(HHCEA)进行求解.首先,设计基于工序序列、工厂分配和产品序列的三维向量编码规则和结合贪婪策略的解码规则,同时提出4种启发式方法以提高初始解的质量.然后,设计高低分层结构的HHCEA,高层为提高对搜索方向的引导性,采用交叉熵算法(CEA)学习和积累优质排列的信息,其中各排列由结合问题特点设计的11种启发式操作(即11种有效的邻域操作)构成;低层为增加在解空间中的搜索深度,将高层确定的每个排列中的启发式操作依次重复执行指定次数并在执行过程中加入基于模拟退火的扰动机制,以此作为一种新的启发式方法执行搜索.最后,通过仿真实验与算法对比验证HHCEA可有效求解DAFJSP.

Hyper-heuristic cross-entropy algorithm for distributed assembly flexible job-shop scheduling problem

Aiming at a novel two-stage distributed assembly flexible job-shop scheduling problem (DAFJSP), this paperestablishes the problem model and proposes a hyper-heuristic cross-entropy algorithm (HHCEA) whose optimizationobjective is to minimize the makespan. Firstly, a three-dimensional vector encoding rule based on process sequence, factoryassignment and product sequence and a decoding rule combined with greedy strategy are designed, meanwhile, fourheuristic methods are proposed to improve the quality of initial solutions. Then, a high and low stratified HHCEA is designed,the upper layer for improving the guidance of the search direction, using the cross-entropy algorithm (CEA) to learnand accumulate the information of the high-quality permutations which are composed of 11 heuristic operations (i.e., 11effective neighborhood operations) and each heuristic operation is designed based on the characteristics of the problem;and in order to increase the search depth in the solution space, the lower layer performs the search as a new heuristicmethod by repeating the heuristic operation in each permutation which is identified by the upper layer for specified timesand adds a disturbance mechanism based on simulated annealing during the execution. Finally, simulations experimentsand comparisons demonstrate that HHCEA can effectively solve the DAFJSP.