Flow-Shop Problems with Intermediate Buffers

Peter Brucker, Silvia Heitmann, Johann L. Hurink

Research output: Contribution to journalArticleAcademicpeer-review

55 Citations (Scopus)

Abstract

In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented.
Original languageUndefined
Article number10.1007/s00291-003-0133-7
Pages (from-to)549-574
Number of pages26
JournalOR Spectrum = OR Spektrum
Volume25
Issue number4
DOIs
Publication statusPublished - Oct 2003

Keywords

  • MSC-90B35
  • EWI-3744
  • IR-62907
  • METIS-213409

Cite this

Brucker, Peter ; Heitmann, Silvia ; Hurink, Johann L. / Flow-Shop Problems with Intermediate Buffers. In: OR Spectrum = OR Spektrum. 2003 ; Vol. 25, No. 4. pp. 549-574.
@article{a05ade15f0a54bd1b41a87dc256ea32f,
title = "Flow-Shop Problems with Intermediate Buffers",
abstract = "In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented.",
keywords = "MSC-90B35, EWI-3744, IR-62907, METIS-213409",
author = "Peter Brucker and Silvia Heitmann and Hurink, {Johann L.}",
year = "2003",
month = "10",
doi = "10.1007/s00291-003-0133-7",
language = "Undefined",
volume = "25",
pages = "549--574",
journal = "OR Spectrum = OR Spektrum",
issn = "0171-6468",
publisher = "Springer",
number = "4",

}

Brucker, P, Heitmann, S & Hurink, JL 2003, 'Flow-Shop Problems with Intermediate Buffers', OR Spectrum = OR Spektrum, vol. 25, no. 4, 10.1007/s00291-003-0133-7, pp. 549-574. https://doi.org/10.1007/s00291-003-0133-7

Flow-Shop Problems with Intermediate Buffers. / Brucker, Peter; Heitmann, Silvia; Hurink, Johann L.

In: OR Spectrum = OR Spektrum, Vol. 25, No. 4, 10.1007/s00291-003-0133-7, 10.2003, p. 549-574.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Flow-Shop Problems with Intermediate Buffers

AU - Brucker, Peter

AU - Heitmann, Silvia

AU - Hurink, Johann L.

PY - 2003/10

Y1 - 2003/10

N2 - In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented.

AB - In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented.

KW - MSC-90B35

KW - EWI-3744

KW - IR-62907

KW - METIS-213409

U2 - 10.1007/s00291-003-0133-7

DO - 10.1007/s00291-003-0133-7

M3 - Article

VL - 25

SP - 549

EP - 574

JO - OR Spectrum = OR Spektrum

JF - OR Spectrum = OR Spektrum

SN - 0171-6468

IS - 4

M1 - 10.1007/s00291-003-0133-7

ER -