A Dominance Relations-Based Variable Neighborhood Search for Assembly Job Shop Scheduling with Parallel Machines

This study addresses the assembly job shop scheduling problem (AJSSP) with parallel machines. In an assembly job shop, product structures are represented through hierarchical tree diagrams, where components and subassemblies are sequentially assembled to form the final product. A mixed-integer linear programming (MILP) model is formulated to minimize the total completion time. A dominance relations-based variable neighborhood search (DR-VNS) is proposed for solving AJSSP with parallel machines. The proposed approach integrates dominance relations among operations in the initialization phase and employs tailored neighborhood structures to address sequencing and assignment challenges, thereby enhancing the generation of neighboring solutions. Experimental studies conducted on test cases of varying scales and complexities demonstrate the effectiveness of the proposed algorithms in solving the AJSSP with parallel machines.