Two very large-scale neighborhoods for single machine scheduling

被引：8

作者：

Brueggemann, Tobias ^{[1
]}

Hurink, Johann L. ^{[1
]}

机构：

[1] Univ Twente, Dept Appl Math, NL-7500 AE Enschede, Netherlands

来源：

OR SPECTRUM | 2007年 / 29卷 / 03期

关键词：

very large-scale neighborhoods; local search; single machine;

D O I：

10.1007/s00291-006-0052-5

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, the problem of minimizing the total completion time on a single machine with the presence of release dates is studied. We introduce two different approaches leading to very large-scale neighborhoods in which the best improving neighbor can be determined in polynomial time. Furthermore, computational results are presented to get insight in the performance of the developed neighborhoods.

引用

页码：513 / 533

页数：21

共 14 条

[1]

AHMADI RH, 1990, NAV RES LOG, V37, P967, DOI 10.1002/1520-6750(199012)37:6<967::AID-NAV3220370616>3.0.CO

[2]

2-K

[3] A survey of very large-scale neighborhood search techniques [J].

Ahuja, RK ;

Ergun, Ö ;

Orlin, JB ;

Punnen, AP .

DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :75-102

[4]

Baker KR., 1974, Introduction to Sequencing and Scheduling

[5]

CHU CB, 1992, NAV RES LOG, V39, P859, DOI 10.1002/1520-6750(199210)39:6<859::AID-NAV3220390610>3.0.CO

[6]

2-W

[7] An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem [J].

Congram, RK ;

Potts, CN ;

van de Velde, SL .

INFORMS JOURNAL ON COMPUTING, 2002, 14 (01) :52-67

[8]

Graham R. L., 1979, Discrete Optimisation, P287

[9] An exponential neighborhood for a one-machine batching problem Eine exponentielle Nachbarschaft für ein Einmaschinen-Batching-Problem [J].

Johann Hurink .

OR-Spektrum, 1999, 21 (4) :461-476

[10]

KAN AHG, 1976, MACHINE SCHEDULING P, P79

← 1 2 →