Improving local search heuristics for some scheduling problems .1.

被引：26

作者：

Brucker, P ^{[1
]}

Hurink, J ^{[1
]}

Werner, F ^{[1
]}

机构：

[1] OTTO VON GUERICKE UNIV, INST MATH OPTIMIERUNG, D-39016 MAGDEBURG, GERMANY

来源：

DISCRETE APPLIED MATHEMATICS | 1996年 / 65卷 / 1-3期

关键词：

D O I：

10.1016/0166-218X(95)00030-U

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Local search techniques like simulated annealing and tabu search are based on a neighborhood structure defined on a set of feasible solutions of a discrete optimization problem. For the scheduling problems P2 // C-max, 1/prec/ Sigma C-i and 1 // Sigma T-i we replace a simple neighborhood by a neighborhood on the set of all locally optimal solutions. This allows local search on the set of solutions that are locally optimal.

引用

页码：97 / 122

页数：26

共 11 条

[1] TABU SEARCH TECHNIQUES - A TUTORIAL AND AN APPLICATION TO NEURAL NETWORKS
DEWERRA, D
HERTZ, A
[J]. OR SPEKTRUM, 1989, 11 (03) : 131 - 141
[2] MINIMIZING TOTAL TARDINESS ON ONE MACHINE IS NP-HARD
DU, JZ
LEUNG, JYT
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) : 483 - 495
[3] Glover F., 1990, ORSA Journal on Computing, V2, P4, DOI [10.1287/ijoc.1.3.190, 10.1287/ijoc.2.1.4]
[4] Lawler E.L., 1978, Annals of Discrete Mathematics, V2, P75
[5] Lawler E. L., 1977, ANN DISCRETE MATH, V1, P331, DOI [10.1016/S0167-5060(08)70742-8, DOI 10.1016/S0167-5060(08)70742-8]
[6] LARGE-STEP MARKOV-CHAINS FOR THE TSP INCORPORATING LOCAL SEARCH HEURISTICS
MARTIN, O
OTTO, SW
FELTEN, EW
[J]. OPERATIONS RESEARCH LETTERS, 1992, 11 (04) : 219 - 224
[7] MINIMIZING TOTAL COSTS IN ONE-MACHINE SCHEDULING
RINNOOYKAN, AHG
LAGEWEG, BJ
LENSTRA, JK
[J]. OPERATIONS RESEARCH, 1975, 23 (05) : 908 - 927
[8] THOLE M, 1993, THESIS U OSNABRUCK
[9] ULDER NLJ, 1990, THESIS EINDHOBEN U T
[10] van Laarhoven P. J. M., 1987, Simulated annealing, P7

← 1 2 →