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

被引：9

作者：

Qin, Tao ^{[1
]}

Peng, Bo ^{[1
]}

Benlic, Una ^{[2
]}

Cheng, T. C. E. ^{[3
]}

Wang, Yang ^{[1
]}

Lu, Zhipeng ^{[1
,3
]}

机构：

[1] Huazhong Univ Sci & Technol, Sch Comp Sci & Technol, SMART, Wuhan 430074, Peoples R China

[2] Univ Stirling, Comp Sci & Math Sch Nat Sci, Stirling FK9 4LA, Scotland

[3] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2015年 / 61卷

基金：

英国工程与自然科学研究理事会; 中国国家自然科学基金;

关键词：

Single machine; Iterated local search; Multi-type perturbation; Tabu search; QUADRATIC FUNCTION; JOB LATENESS; LINEAR EARLINESS; HEURISTICS; TARDINESS;

D O I：

10.1016/j.cor.2015.03.005

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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. (C) 2015 Elsevier Ltd. All rights reserved.

引用

页码：81 / 88

页数：8

共 23 条

[21] BEAM SEARCH HEURISTICS FOR THE SINGLE MACHINE SCHEDULING PROBLEM WITH LINEAR EARLINESS AND QUADRATIC TARDINESS COSTS
Valente, Jorge M. S.
[J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2009, 26 (03) : 319 - 339
[22] A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties
Valente, Jorge M. S.
Goncalves, Jose Fernando
[J]. COMPUTERS & OPERATIONS RESEARCH, 2009, 36 (10) : 2707 - 2715
[23] Heuristics for the single machine scheduling problem with early and quadratic tardy penalties
Valente, Jorge M. S.
[J]. EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING, 2007, 1 (04) : 431 - 448

← 1 2 3 →