Makespan minimisation with sequence-dependent machine deterioration and maintenance events

This paper addresses the minimal makespan parallel machine problem where machines are subject to preventive maintenance events of a known deterministic duration. The processing time of a job depends on its predecessors since the machine’s last maintenance. The paper proposes some dominance criteria for sequences of jobs assigned to a machine, and uses these criteria to design constructive heuristics to this NP-hard problem. The computational investigation determines the parameters that make a hard instance and studies the sensitivity of the heuristics to these parameters.