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 条

[11] Application of graph search and genetic algorithms for the single machine scheduling problem with sequence-dependent setup times and quadratic penalty function of completion times
Kodaganallur, Viswanathan
Sen, Anup K.
Mitra, Subrata
[J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2014, 67 : 10 - 19
[12] Resende MGC, 2003, INT SER OPER RES MAN, V57, P219, DOI 10.1007/0-306-48056-5_8
[13] Rinnooy Kan A. H. G., 1977, Annals of Discrete Mathematics, V1, P343, DOI [DOI 10.1016/S0167-5060(08)70743-X, 10.1016/S0167-5060(08)70743-X]
[14] Single machine scheduling with early and quadratic tardy penalties
Schaller, J
[J]. COMPUTERS & INDUSTRIAL ENGINEERING, 2004, 46 (03) : 511 - 532
[15] Minimizing the sum of squares lateness on a single machine
Schaller, J
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 143 (01) : 64 - 79
[16] A comparison of lower bounds for the single-machine early/tardy problem
Schaller, Jeffrey
[J]. COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (08) : 2279 - 2292
[17] Minimizing a weighted quadratic function of job lateness in the single machine system
Sen, T
Dileepan, P
Lind, MR
[J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1996, 42 (03) : 237 - 243
[18] A heuristic to minimize a quadratic function of job lateness on a single machine
Su, LH
Chang, PC
[J]. INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 1998, 55 (02) : 169 - 175
[19] An exact approach for the single machine scheduling problem with linear early and quadratic tardy penalties
Valente, Jorge M. S.
[J]. ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2008, 25 (02) : 169 - 186
[20] Improved heuristics for the single machine scheduling problem with linear early and quadratic tardy penalties
Valente, Jorge M. S.
Schaller, Jeffrey E.
[J]. EUROPEAN JOURNAL OF INDUSTRIAL ENGINEERING, 2010, 4 (01) : 99 - 129

← 1 2 3 →