Optimize assembly-line scheduling with changeovers
Overview
This question evaluates combinatorial optimization and scheduling competencies, specifically reasoning about NP-hardness, sequence-dependent setup times, precedence and downtime constraints, and designing exact and heuristic solvers for makespan minimization.
You are scheduling a simplified car-assembly line with two parallel stations S1 and S2. Each job must be processed on exactly one station, processing times differ by station, and there are sequence-dependent setup times on each station. Precedence: J2 cannot start before J1 finishes. Maintenance: S1 is down from t=60 to t=70. Data: processing times (minutes) — J1: S1=20, S2=25; J2: S1=30, S2=22; J3: S1=18, S2=15. Setup times (minutes) on either station (first job has no setup): J1→J2=5, J1→J3=3, J2→J1=4, J2→J3=6, J3→J1=2, J3→J2=1. Goal: minimize makespan subject to precedence and downtime. Tasks: (a) Argue NP-hardness by relating this to SDST flow-shop/job-shop scheduling. (b) Compute the optimal schedule for this instance (explicit sequences per station with start/finish times and the final makespan); you may use branch-and-bound or DP with bitmask over job subsets, carefully handling downtime and setups. (c) For general n,m, propose a practical solver: either an ILP with assignment/order and time-index or disjunctive constraints, or a metaheuristic (e.g., NEH initialization + tabu/SA). Analyze complexity, pruning rules, and any approximation guarantees or known bounds.