Job-Shop Scheduling with Limited Capacity Buffers

Peter Brucker, Silvia Heitmann, Johann L. Hurink, T. Nieberg

Research output: Contribution to journalArticleAcademicpeer-review

36 Citations (Scopus)
149 Downloads (Pure)

Abstract

In this paper we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are present. In such a problem setting, 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 a prespecified buffer. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. Besides a general buffer model, also specific configurations are considered. The aim of this paper is to find a compact representation of solutions for the job-shop problem with buffers. In contrast to the classical job-shop problem, where a solution may be given by the sequences of the jobs on the machines, now also the buffers have to be incorporated in the solution representation. In a first part, two such representations are proposed, one which is achieved by adapting the alternative graph model and a second which is based on the disjunctive graph model. In a second part, it is investigated whether the given solution representation can be simplified for specific buffer configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation is necessary, whereas for specific buffer configurations possible simplifications are presented.
Original languageUndefined
Article number10.1007/s00291-005-0008-1
Pages (from-to)151-176
Number of pages26
JournalOR Spectrum = OR Spektrum
Volume28
Issue number2/2
DOIs
Publication statusPublished - 12 Jan 2006

Keywords

  • MSC-90B35
  • IR-66029
  • METIS-238055
  • EWI-3743

Cite this

Brucker, P., Heitmann, S., Hurink, J. L., & Nieberg, T. (2006). Job-Shop Scheduling with Limited Capacity Buffers. OR Spectrum = OR Spektrum, 28(2/2), 151-176. [10.1007/s00291-005-0008-1]. https://doi.org/10.1007/s00291-005-0008-1
Brucker, Peter ; Heitmann, Silvia ; Hurink, Johann L. ; Nieberg, T. / Job-Shop Scheduling with Limited Capacity Buffers. In: OR Spectrum = OR Spektrum. 2006 ; Vol. 28, No. 2/2. pp. 151-176.
@article{3d0e7a284a6448c88c4b6aa96bdf98bf,
title = "Job-Shop Scheduling with Limited Capacity Buffers",
abstract = "In this paper we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are present. In such a problem setting, 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 a prespecified buffer. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. Besides a general buffer model, also specific configurations are considered. The aim of this paper is to find a compact representation of solutions for the job-shop problem with buffers. In contrast to the classical job-shop problem, where a solution may be given by the sequences of the jobs on the machines, now also the buffers have to be incorporated in the solution representation. In a first part, two such representations are proposed, one which is achieved by adapting the alternative graph model and a second which is based on the disjunctive graph model. In a second part, it is investigated whether the given solution representation can be simplified for specific buffer configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation is necessary, whereas for specific buffer configurations possible simplifications are presented.",
keywords = "MSC-90B35, IR-66029, METIS-238055, EWI-3743",
author = "Peter Brucker and Silvia Heitmann and Hurink, {Johann L.} and T. Nieberg",
note = "10.1007/s00291-005-0008-1",
year = "2006",
month = "1",
day = "12",
doi = "10.1007/s00291-005-0008-1",
language = "Undefined",
volume = "28",
pages = "151--176",
journal = "OR Spectrum = OR Spektrum",
issn = "0171-6468",
publisher = "Springer",
number = "2/2",

}

Brucker, P, Heitmann, S, Hurink, JL & Nieberg, T 2006, 'Job-Shop Scheduling with Limited Capacity Buffers' OR Spectrum = OR Spektrum, vol. 28, no. 2/2, 10.1007/s00291-005-0008-1, pp. 151-176. https://doi.org/10.1007/s00291-005-0008-1

Job-Shop Scheduling with Limited Capacity Buffers. / Brucker, Peter; Heitmann, Silvia; Hurink, Johann L.; Nieberg, T.

In: OR Spectrum = OR Spektrum, Vol. 28, No. 2/2, 10.1007/s00291-005-0008-1, 12.01.2006, p. 151-176.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Job-Shop Scheduling with Limited Capacity Buffers

AU - Brucker, Peter

AU - Heitmann, Silvia

AU - Hurink, Johann L.

AU - Nieberg, T.

N1 - 10.1007/s00291-005-0008-1

PY - 2006/1/12

Y1 - 2006/1/12

N2 - In this paper we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are present. In such a problem setting, 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 a prespecified buffer. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. Besides a general buffer model, also specific configurations are considered. The aim of this paper is to find a compact representation of solutions for the job-shop problem with buffers. In contrast to the classical job-shop problem, where a solution may be given by the sequences of the jobs on the machines, now also the buffers have to be incorporated in the solution representation. In a first part, two such representations are proposed, one which is achieved by adapting the alternative graph model and a second which is based on the disjunctive graph model. In a second part, it is investigated whether the given solution representation can be simplified for specific buffer configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation is necessary, whereas for specific buffer configurations possible simplifications are presented.

AB - In this paper we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are present. In such a problem setting, 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 a prespecified buffer. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. Besides a general buffer model, also specific configurations are considered. The aim of this paper is to find a compact representation of solutions for the job-shop problem with buffers. In contrast to the classical job-shop problem, where a solution may be given by the sequences of the jobs on the machines, now also the buffers have to be incorporated in the solution representation. In a first part, two such representations are proposed, one which is achieved by adapting the alternative graph model and a second which is based on the disjunctive graph model. In a second part, it is investigated whether the given solution representation can be simplified for specific buffer configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation is necessary, whereas for specific buffer configurations possible simplifications are presented.

KW - MSC-90B35

KW - IR-66029

KW - METIS-238055

KW - EWI-3743

U2 - 10.1007/s00291-005-0008-1

DO - 10.1007/s00291-005-0008-1

M3 - Article

VL - 28

SP - 151

EP - 176

JO - OR Spectrum = OR Spektrum

JF - OR Spectrum = OR Spektrum

SN - 0171-6468

IS - 2/2

M1 - 10.1007/s00291-005-0008-1

ER -

Brucker P, Heitmann S, Hurink JL, Nieberg T. Job-Shop Scheduling with Limited Capacity Buffers. OR Spectrum = OR Spektrum. 2006 Jan 12;28(2/2):151-176. 10.1007/s00291-005-0008-1. https://doi.org/10.1007/s00291-005-0008-1