Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups.

This article focuses on developing novel domain-independent dynamic programming (DIDP) and constraint programming (CP) models to exactly solve the type 1 and type 2 assembly line balancing problems with sequence-dependent setup times (SUALBP-1 and SUALBP-2). SUALBP involves assigning and sequencing tasks on assembly stations while respecting precedence constraints and setup times that depend on task order. The DIDP models, formulated as state-based transition systems and solved via complete anytime beam search, incorporate new state-based dual bounds to enhance efficiency. Experimental results on a large benchmark dataset demonstrate that DIDP significantly outperforms state-of-the-art mixed-integer programming (MIP) and CP models in finding and proving optimal solutions for both SUALBP-1 and SUALBP-2, and notably surpasses the leading exact algorithm based on logic-based Benders decomposition (FFLBBD) for SUALBP-2 by solving more instances to optimality and closing previously open cases. A local improvement algorithm for SUALBP-2, which reoptimizes task sequences within stations, was also proposed but found to offer limited practical benefit. The study highlights DIDP’s promise for complex scheduling problems and suggests further research into its broader applicability and solver enhancements.