Two-machine flowshop scheduling with consecutive availability constraints

Edwin Tai Chiu Cheng; Guoqing Wang

Two-machine flowshop scheduling with consecutive availability constraints

Research output: Journal article publication › Journal article › Academic research › peer-review

Abstract

In this paper we study a special case of the two-machine flowshop problem with an availability constraint imposed on each machine. The two availability constraints are consecutive. We establish some basic properties for the semiresumable case, i.e. if a job cannot be finished before the next down period of a machine, then the job will be partially restarted when the machine becomes available again. We provide a heuristic for the problem and show that it has a worst-case error bound of 2/3 for the nonresumable case.

Original language	English
Pages (from-to)	49-54
Number of pages	6
Journal	Information Processing Letters
Volume	71
Issue number	2
Publication status	Published - 30 Jul 1999

Keywords

Algorithms
Flowshop scheduling
Worst-case analysis

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Cite this

@article{27802ba95e02485b9efa425178190486,

title = "Two-machine flowshop scheduling with consecutive availability constraints",

abstract = "In this paper we study a special case of the two-machine flowshop problem with an availability constraint imposed on each machine. The two availability constraints are consecutive. We establish some basic properties for the semiresumable case, i.e. if a job cannot be finished before the next down period of a machine, then the job will be partially restarted when the machine becomes available again. We provide a heuristic for the problem and show that it has a worst-case error bound of 2/3 for the nonresumable case.",

keywords = "Algorithms, Flowshop scheduling, Worst-case analysis",

author = "Cheng, {Edwin Tai Chiu} and Guoqing Wang",

year = "1999",

month = jul,

day = "30",

language = "English",

volume = "71",

pages = "49--54",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Two-machine flowshop scheduling with consecutive availability constraints

AU - Cheng, Edwin Tai Chiu

AU - Wang, Guoqing

PY - 1999/7/30

Y1 - 1999/7/30

N2 - In this paper we study a special case of the two-machine flowshop problem with an availability constraint imposed on each machine. The two availability constraints are consecutive. We establish some basic properties for the semiresumable case, i.e. if a job cannot be finished before the next down period of a machine, then the job will be partially restarted when the machine becomes available again. We provide a heuristic for the problem and show that it has a worst-case error bound of 2/3 for the nonresumable case.

AB - In this paper we study a special case of the two-machine flowshop problem with an availability constraint imposed on each machine. The two availability constraints are consecutive. We establish some basic properties for the semiresumable case, i.e. if a job cannot be finished before the next down period of a machine, then the job will be partially restarted when the machine becomes available again. We provide a heuristic for the problem and show that it has a worst-case error bound of 2/3 for the nonresumable case.

KW - Algorithms

KW - Flowshop scheduling

KW - Worst-case analysis

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

M3 - Journal article

SN - 0020-0190

VL - 71

SP - 49

EP - 54

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Two-machine flowshop scheduling with consecutive availability constraints

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this