This paper studies an unrelated parallel machine scheduling problem arising in heterogeneous manufacturing systems. The production environment features machine-dependent processing times, sequence-dependent setup times, and workforce-driven productivity differences modeled through two non-cyclic shifts with distinct processing rates. Jobs must be assigned and sequenced on eligible machines, and the objective is to minimize total tardiness. The problem is computationally challenging due to the strong coupling between assignment, sequencing, and timing decisions induced by setup effects and shift-dependent processing speeds. A Mixed-Integer Linear Programming (MILP) formulation is developed to obtain optimal solutions for small instances. For large-scale instances, we propose an Adaptive Large Neighborhood Search (ALNS) algorithm that combines a constructive initial heuristic with multiple destruction and repair operators. Computational experiments show that the proposed ALNS consistently outperforms state-of-the-art MILP solvers and benchmark metaheuristics.

Keywords

Unrelated parallel machine scheduling, Sequence-and-machine-dependent setups, Shift-dependent productivity, Tardiness minimization, Adaptive large neighborhood search