The two-machine open shop problem: To fit or not to fit, that is the question

Marjan Van den Akker; Han Hoogeveen; Gerhard J. Woeginger

doi:10.1016/S0167-6377(03)00018-X

The two-machine open shop problem: To fit or not to fit, that is the question

Marjan Van den Akker, Han Hoogeveen^*, Gerhard J. Woeginger

^*Corresponding author for this work

University of Twente

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

Abstract

We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D₁ and D₂, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0, D₁] and [0, D₂], respectively. We formulate four simple conditions on D₁ and D₂, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D₁, D₂) for which there exists a feasible schedule.

Original language	English
Pages (from-to)	219-224
Number of pages	6
Journal	Operations Research Letters
Volume	31
Issue number	3
DOIs	https://doi.org/10.1016/S0167-6377(03)00018-X
Publication status	Published - May 2003

Bibliographical note

Funding Information:
The authors thank an anonymous referee for his/her comments. The first and second author were partially supported by EC Contract IST-1999-14186 (Project ALCOM-FT).

Keywords

Bicriterion optimization
Flow shop scheduling
Open shop scheduling
Scheduling
Sequencing

Access to Document

10.1016/S0167-6377(03)00018-X

Cite this

@article{169ee24990ff4fcaaaee9161b3a4ff13,

title = "The two-machine open shop problem: To fit or not to fit, that is the question",

abstract = "We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D1 and D2, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0, D1] and [0, D2], respectively. We formulate four simple conditions on D1 and D2, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D1, D2) for which there exists a feasible schedule.",

keywords = "Bicriterion optimization, Flow shop scheduling, Open shop scheduling, Scheduling, Sequencing",

author = "{Van den Akker}, Marjan and Han Hoogeveen and Woeginger, {Gerhard J.}",

note = "Funding Information: The authors thank an anonymous referee for his/her comments. The first and second author were partially supported by EC Contract IST-1999-14186 (Project ALCOM-FT).",

year = "2003",

month = may,

doi = "10.1016/S0167-6377(03)00018-X",

language = "English",

volume = "31",

pages = "219--224",

journal = "Operations Research Letters",

publisher = "Elsevier BV",

number = "3",

}

TY - JOUR

T1 - The two-machine open shop problem

T2 - To fit or not to fit, that is the question

AU - Van den Akker, Marjan

AU - Hoogeveen, Han

AU - Woeginger, Gerhard J.

N1 - Funding Information: The authors thank an anonymous referee for his/her comments. The first and second author were partially supported by EC Contract IST-1999-14186 (Project ALCOM-FT).

PY - 2003/5

Y1 - 2003/5

N2 - We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D1 and D2, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0, D1] and [0, D2], respectively. We formulate four simple conditions on D1 and D2, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D1, D2) for which there exists a feasible schedule.

AB - We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D1 and D2, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0, D1] and [0, D2], respectively. We formulate four simple conditions on D1 and D2, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D1, D2) for which there exists a feasible schedule.

KW - Bicriterion optimization

KW - Flow shop scheduling

KW - Open shop scheduling

KW - Scheduling

KW - Sequencing

UR - http://www.scopus.com/inward/record.url?scp=0037402140&partnerID=8YFLogxK

U2 - 10.1016/S0167-6377(03)00018-X

DO - 10.1016/S0167-6377(03)00018-X

M3 - Article

VL - 31

SP - 219

EP - 224

JO - Operations Research Letters

JF - Operations Research Letters

IS - 3

ER -

The two-machine open shop problem: To fit or not to fit, that is the question

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this