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 paper establishes the problem model and proposes a hyper-heuristic cross-entropy algorithm (HHCEA) whose optimization objective is to minimize the makespan. Firstly, a three-dimensional vector encoding rule based on process sequence, factory assignment and product sequence and a decoding rule combined with greedy strategy are designed, meanwhile, four heuristic 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 learn and accumulate the information of the high-quality permutations which are composed of 11 heuristic operations (i.e., 11 effective 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 heuristic method by repeating the heuristic operation in each permutation which is identified by the upper layer for specified times and adds a disturbance mechanism based on simulated annealing during the execution. Finally, simulations experiments and comparisons demonstrate that HHCEA can effectively solve the DAFJSP. © 2021, Editorial Department of Control Theory & Applications. All right reserved.