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ü

doi:10.1016/j.cor.2015.03.005

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 publication › Journal article › Academic research › peer-review

9 Citations (Scopus)

Abstract

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 language	English
Pages (from-to)	81-88
Number of pages	8
Journal	Computers and Operations Research
Volume	61
DOIs	https://doi.org/10.1016/j.cor.2015.03.005
Publication status	Published - 1 Sept 2015

Keywords

Iterated local search
Multi-type perturbation
Single machine
Tabu search

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research

More information

10.1016/j.cor.2015.03.005

Cite this

@article{91bab451ab464b53b98c55168b9a108d,

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

abstract = "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.",

keywords = "Iterated local search, Multi-type perturbation, Single machine, Tabu search",

author = "Tao Qin and Bo Peng and Una Benlic and Cheng, {Edwin Tai Chiu} and Yang Wang and Zhipeng L{\"u}",

year = "2015",

month = sep,

day = "1",

doi = "10.1016/j.cor.2015.03.005",

language = "English",

volume = "61",

pages = "81--88",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

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

AU - Qin, Tao

AU - Peng, Bo

AU - Benlic, Una

AU - Cheng, Edwin Tai Chiu

AU - Wang, Yang

AU - Lü, Zhipeng

PY - 2015/9/1

Y1 - 2015/9/1

N2 - 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.

AB - 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.

KW - Iterated local search

KW - Multi-type perturbation

KW - Single machine

KW - Tabu search

UR - http://www.scopus.com/inward/record.url?scp=84926187386&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2015.03.005

DO - 10.1016/j.cor.2015.03.005

M3 - Journal article

SN - 0305-0548

VL - 61

SP - 81

EP - 88

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this