A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem

The distributed assembly permutation flow-shop scheduling problem (DAPFSP) is a typical NP-hard combinatorial optimization problem that has wide applications in advanced manufacturing systems and modern supply chains. In this work, an innovative three-dimensional matrix-cube-based estimation of distribution algorithm (MCEDA) is first proposed for the DAPFSP to minimize the maximum completion time. Firstly, a matrix cube is designed to learn the valuable information from elites. Secondly, a matrix-cube-based probabilistic model with an effective sampling mechanism is developed to estimate the probability distribution of superior solutions and to perform the global exploration for finding promising regions. Thirdly, a problem-dependent variable neighborhood descent method is proposed to perform the local exploitation around these promising regions, and several speedup strategies for evaluating neighboring solutions are utilized to enhance the computational efficiency. Furthermore, the influence of the parameters setting is analyzed by using design-of-experiment technique, and the suitable parameters are suggested for different scale problems. Finally, a comprehensive computational campaign against the state-of-the-art algorithms in the literature, together with statistical analyses, demonstrates that the proposed MCEDA produces better results than the existing algorithms by a significant margin. Moreover, the new best-known solutions for 214 instances are improved.

Automated summary

This paper introduces an innovative three-dimensional matrix-cube-based estimation algorithm to solve the DAPFSP problem, which improves computational efficiency through global exploration and local exploitation, achieving significantly better results than existing algorithms.