Discrete-time models and a lower bound binary search procedure for scheduling an assembly problem with precedence and resource constraints

This work investigates a complex scheduling problem arising in vehicle manufacturing, where assembly operations require the simultaneous allocation of a machine and a worker, and the operations of each vehicle are constrained by a special rooted in-tree precedence structure. The problem combines elements of Dual-Resource Constrained scheduling and Resource-Constrained Project Scheduling Problems. Building on previous contributions, we propose enhancements to a recently presented Constraint Programming model and, leveraging the connection with project scheduling, we introduce eight new discrete-time Mixed Integer Linear Programming models that incorporate disaggregated precedence and tightened resource constraints. The core contribution of this work is a binary search procedure that exploits the linear programming relaxation of these models to compute superior lower bounds for the problem. Experimental results demonstrate that combining these superior lower bounds with the upper bounds of the refined Constraint Programming model significantly improves the quality of solutions, reducing the average optimality gap to just 1% across a diverse set of benchmark instances.