A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags

P. Brucker; T. Hilbig; Johann L. Hurink

doi:10.1016/S0166-218X(99)00015-3

A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags

P. Brucker, T. Hilbig, Johann L. Hurink

Research output: Contribution to journal › Article › Academic › peer-review

45 Citations (Scopus)

62 Downloads (Pure)

Abstract

Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced by Roy in connection with the Metra Potential Method. They allow the consideration of positive and negative time-lags between the starting times of jobs. It is shown that complex scheduling problems like general shop problems, problems with multi-processor tasks, problems with multi-purpose machines, and problems with changeover times can be reduced to single-machine problems with positive and negative time-lags between jobs. Furthermore, a branch and bound algorithm is developed for solving such single-machine scheduling problems. The reductions can be used to construct test problems for this algorithm. Computational results for randomly generated single-machine problems and for shop scheduling problems (without time-lags) are reported.

Original language	English
Pages (from-to)	77-99
Number of pages	23
Journal	Discrete applied mathematics
Issue number	94
DOIs	https://doi.org/10.1016/S0166-218X(99)00015-3
Publication status	Published - 1999

Access to Document

10.1016/S0166-218X(99)00015-3Licence: Other

branchFinal published version, 1.72 MBLicence: Other

Cite this

@article{bc392f8ca5064e949bd734a88fad8e11,

title = "A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags",

abstract = "Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced by Roy in connection with the Metra Potential Method. They allow the consideration of positive and negative time-lags between the starting times of jobs. It is shown that complex scheduling problems like general shop problems, problems with multi-processor tasks, problems with multi-purpose machines, and problems with changeover times can be reduced to single-machine problems with positive and negative time-lags between jobs. Furthermore, a branch and bound algorithm is developed for solving such single-machine scheduling problems. The reductions can be used to construct test problems for this algorithm. Computational results for randomly generated single-machine problems and for shop scheduling problems (without time-lags) are reported.",

author = "P. Brucker and T. Hilbig and Hurink, {Johann L.}",

year = "1999",

doi = "10.1016/S0166-218X(99)00015-3",

language = "English",

pages = "77--99",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "94",

}

TY - JOUR

T1 - A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags

AU - Brucker, P.

AU - Hilbig, T.

AU - Hurink, Johann L.

PY - 1999

Y1 - 1999

N2 - Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced by Roy in connection with the Metra Potential Method. They allow the consideration of positive and negative time-lags between the starting times of jobs. It is shown that complex scheduling problems like general shop problems, problems with multi-processor tasks, problems with multi-purpose machines, and problems with changeover times can be reduced to single-machine problems with positive and negative time-lags between jobs. Furthermore, a branch and bound algorithm is developed for solving such single-machine scheduling problems. The reductions can be used to construct test problems for this algorithm. Computational results for randomly generated single-machine problems and for shop scheduling problems (without time-lags) are reported.

AB - Positive and negative time-lags are general timing restrictions between the starting times of jobs which have been introduced by Roy in connection with the Metra Potential Method. They allow the consideration of positive and negative time-lags between the starting times of jobs. It is shown that complex scheduling problems like general shop problems, problems with multi-processor tasks, problems with multi-purpose machines, and problems with changeover times can be reduced to single-machine problems with positive and negative time-lags between jobs. Furthermore, a branch and bound algorithm is developed for solving such single-machine scheduling problems. The reductions can be used to construct test problems for this algorithm. Computational results for randomly generated single-machine problems and for shop scheduling problems (without time-lags) are reported.

U2 - 10.1016/S0166-218X(99)00015-3

DO - 10.1016/S0166-218X(99)00015-3

M3 - Article

SP - 77

EP - 99

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 94

ER -

A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags

Abstract

Access to Document

Fingerprint

Cite this