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

Tao Qin, Bo Peng, Una Benlic, Edwin Tai Chiu Cheng, Yang Wang, Zhipeng Lü

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)81-88
Number of pages8
JournalComputers and Operations Research
Publication statusPublished - 1 Sep 2015


  • Iterated local search
  • Multi-type perturbation
  • Single machine
  • Tabu search

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this