Flow-shop problems with intermediate buffers

P. Brucker, S. Heitmann, Johann L. Hurink

Research output: Book/ReportReportOther research output

76 Downloads (Pure)

Abstract

In this paper the following extension of the classical flow-shop problem is considered: Between each two successive machines a buffer of limited capacity is given in which jobs can be stored. 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, 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 languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2002

Publication series

NameMemorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1625
ISSN (Print)0169-2690

Fingerprint

Flow Shop
Buffer
Graph Model
Tabu Search
Computational Results
Schedule
Benchmark
Theorem
Model

Keywords

  • MSC-90B35
  • IR-65812
  • EWI-3445

Cite this

Brucker, P., Heitmann, S., & Hurink, J. L. (2002). Flow-shop problems with intermediate buffers. (Memorandum; No. 1625). Enschede: University of Twente, Department of Applied Mathematics.
Brucker, P. ; Heitmann, S. ; Hurink, Johann L. / Flow-shop problems with intermediate buffers. Enschede : University of Twente, Department of Applied Mathematics, 2002. (Memorandum; 1625).
@book{90f183dd9ce14392846d0b34631316ce,
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 successive machines a buffer of limited capacity is given in which jobs can be stored. 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, 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, IR-65812, EWI-3445",
author = "P. Brucker and S. Heitmann and Hurink, {Johann L.}",
year = "2002",
language = "English",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1625",

}

Brucker, P, Heitmann, S & Hurink, JL 2002, Flow-shop problems with intermediate buffers. Memorandum, no. 1625, University of Twente, Department of Applied Mathematics, Enschede.

Flow-shop problems with intermediate buffers. / Brucker, P.; Heitmann, S.; Hurink, Johann L.

Enschede : University of Twente, Department of Applied Mathematics, 2002. (Memorandum; No. 1625).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Flow-shop problems with intermediate buffers

AU - Brucker, P.

AU - Heitmann, S.

AU - Hurink, Johann L.

PY - 2002

Y1 - 2002

N2 - In this paper the following extension of the classical flow-shop problem is considered: Between each two successive machines a buffer of limited capacity is given in which jobs can be stored. 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, 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 successive machines a buffer of limited capacity is given in which jobs can be stored. 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, 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 - IR-65812

KW - EWI-3445

M3 - Report

T3 - Memorandum

BT - Flow-shop problems with intermediate buffers

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Brucker P, Heitmann S, Hurink JL. Flow-shop problems with intermediate buffers. Enschede: University of Twente, Department of Applied Mathematics, 2002. (Memorandum; 1625).