Knowledge-enhanced multidimensional estimation of distribution hyper-heuristic evolutionary algorithm for semiconductor final testing scheduling problem

The semiconductor final test scheduling problem (SFTSP), recognized as a crucial bottleneck in the semiconductor production process, holds immense significance for improving both quality control and scheduling efficiency within chip and integrated circuit enterprises. This article introduces the knowledge-enhanced multidimensional estimation of distribution hyper-heuristic evolutionary algorithm (KMEDHEA) for addressing the SFTSP with the aim of minimizing the makespan. First, a single-vector encoding scheme is used to represent feasible solutions, and a problem-specific constrained-separable left-shift decoding scheme is devised to transform these solutions into feasible scheduling schedules. Second, eight simple yet effective heuristics with problem-specific knowledge are developed that served as a suite of low-level heuristics (LLHs) for exploring the problem solution space. Third, the multidimensional estimation of distribution algorithm (MEDA) is employed as the high-level strategy to estimate the correlations and connections of the pre-designed LLHs, thereby guiding the search scope towards high-quality individuals. Finally, critical configurations of parameters are systematically analyzed by conducting a design-of-experiment (DOE) approach. Numerical experiments are conducted on well-known benchmark datasets, and the experimental results demonstrate the superiority of the KMEDHEA versus several state-of-the-art approaches. The best-known solutions are updated for nine out of ten benchmark instances, highlighting the effectiveness and efficiency of the proposed KMEDHEA in solving the SFTSP.