A hybrid constraint programming and cross-entropy approach for balancing U-Shaped disassembly line with flexible workstations and spatial constraints

Disassembly lines are an effective means for the large-scale, industrialized recycling of end-of-life products. Among these, U-shaped disassembly lines are particularly noted for their combination of flexibility and production efficiency. This study addresses the U-shaped disassembly line balancing problem, considering the coexistence of separate stations and spatial limitations within workstations. A mixed-integer nonlinear programming model and a constraint programming model are developed to accurately capture this complex problem. Additionally, a novel hybrid constraint programming with a goal-driven cross-entropy optimization algorithm (CP-GDCE) is introduced. This algorithm combines a multi-objective cross-entropy grouping framework, a constraint programming-based heuristic initialization, a multi-point crossover recombination mechanism, and large neighborhood search techniques, significantly enhancing solution efficiency and accuracy. Extensive benchmarking and experimental validation indicate that the CP-GDCE not only excels in addressing the specific problem of this study but also demonstrates superiority in classic disassembly line balancing issues. In 21 test cases, the CP-GDCE achieved superior hypervolume and inverted generational distance values compared to 11 benchmark algorithms. A practical application using a printer disassembly example shows that the proposed U-shaped configuration is highly flexible and efficient, compatible with both traditional U-shaped and straight disassembly lines. This configuration significantly reduces the total length of the disassembly line, improving space utilization and highlighting its practical potential and advantages.