Improving local search heuristics for some scheduling problems. Part II

Peter Brucker, Johann L. Hurink, Frank Werner

Research output: Contribution to journalArticleAcademicpeer-review

39 Citations (Scopus)
90 Downloads (Pure)

Abstract

Local search techniques like simulated annealing and tabu search are based on a neighborhood structure defined on the set of feasible solutions of a discrete optimization problem. For the scheduling problems $Pm||C_{max}, 1|prec|\sum U_i,$ and a large class of sequencing problems with precedence constraints having local interchange properties 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. Computational results are presented.
Original languageEnglish
Pages (from-to)47-69
Number of pages23
JournalDiscrete applied mathematics
Volume72
Issue number1-2
DOIs
Publication statusPublished - 10 Jan 1997

Fingerprint

Tabu search
Interchanges
Simulated annealing
Local Search
Scheduling Problem
Scheduling
Heuristics
Precedence Constraints
Discrete Optimization
Local Properties
p.m.
Tabu Search
Simulated Annealing
Sequencing
Computational Results
Optimal Solution
Optimization Problem
Local search (optimization)

Cite this

@article{b6c5102ad8424321b08f82df22397209,
title = "Improving local search heuristics for some scheduling problems. Part II",
abstract = "Local search techniques like simulated annealing and tabu search are based on a neighborhood structure defined on the set of feasible solutions of a discrete optimization problem. For the scheduling problems $Pm||C_{max}, 1|prec|\sum U_i,$ and a large class of sequencing problems with precedence constraints having local interchange properties 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. Computational results are presented.",
author = "Peter Brucker and Hurink, {Johann L.} and Frank Werner",
year = "1997",
month = "1",
day = "10",
doi = "10.1016/S0166-218X(96)00036-4",
language = "English",
volume = "72",
pages = "47--69",
journal = "Discrete applied mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "1-2",

}

Improving local search heuristics for some scheduling problems. Part II. / Brucker, Peter; Hurink, Johann L.; Werner, Frank.

In: Discrete applied mathematics, Vol. 72, No. 1-2, 10.01.1997, p. 47-69.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Improving local search heuristics for some scheduling problems. Part II

AU - Brucker, Peter

AU - Hurink, Johann L.

AU - Werner, Frank

PY - 1997/1/10

Y1 - 1997/1/10

N2 - Local search techniques like simulated annealing and tabu search are based on a neighborhood structure defined on the set of feasible solutions of a discrete optimization problem. For the scheduling problems $Pm||C_{max}, 1|prec|\sum U_i,$ and a large class of sequencing problems with precedence constraints having local interchange properties 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. Computational results are presented.

AB - Local search techniques like simulated annealing and tabu search are based on a neighborhood structure defined on the set of feasible solutions of a discrete optimization problem. For the scheduling problems $Pm||C_{max}, 1|prec|\sum U_i,$ and a large class of sequencing problems with precedence constraints having local interchange properties 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. Computational results are presented.

U2 - 10.1016/S0166-218X(96)00036-4

DO - 10.1016/S0166-218X(96)00036-4

M3 - Article

VL - 72

SP - 47

EP - 69

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 1-2

ER -