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 条

[1] [Anonymous], 2003, Handbook of Metaheuristics
[2] Benlic U., 2013, Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI '13, P461
[3] Breakout local search for the quadratic assignment problem
Benlic, Una
Hao, Jin-Kao
[J]. APPLIED MATHEMATICS AND COMPUTATION, 2013, 219 (09) : 4800 - 4815
[4] Breakout Local Search for maximum clique problems
Benlic, Una
Hao, Jin-Kao
[J]. COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (01) : 192 - 206
[5] ONE-PROCESSOR SCHEDULING WITH SYMMETRIC EARLINESS AND TARDINESS PENALTIES
GAREY, MR
TARJAN, RE
WILFONG, GT
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (02) : 330 - 348
[6] Glover F., 1989, ORSA Journal on Computing, V1, P190, DOI [10.1287/ijoc.2.1.4, 10.1287/ijoc.1.3.190]
[7] Glover F, 2006, OPER RES COMPUT SCI, V36, P53
[8] MINIMIZING A QUADRATIC FUNCTION OF JOB LATENESS ON A SINGLE-MACHINE
GUPTA, SK
SEN, T
[J]. ENGINEERING COSTS AND PRODUCTION ECONOMICS, 1983, 7 (03): : 187 - 194
[9] KIM YD, 1994, NAV RES LOG, V41, P913, DOI 10.1002/1520-6750(199412)41:7<913::AID-NAV3220410705>3.0.CO
[10] 2-A

← 1 2 3 →