Iterated local search based on multi-type perturbation for single-machine earliness/tardiness scheduling

We propose an iterated local search based on a multi-type perturbation (ILS-MP) approach for single-machine scheduling to minimize the sum of linear earliness and quadratic tardiness penalties. The multi-type perturbation mechanism in ILS-MP probabilistically combines three types of perturbation strategies, namely tabu-based perturbation, construction-based perturbation, and random perturbation. Despite its simplicity, experimental results on a wide set of commonly used benchmark instances show that ILS-MP performs favourably in comparison with the current best approaches in the literature.