3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints

Edwin Tai Chiu Cheng; Zhaohui Liu

doi:10.1016/j.ipl.2003.08.002

3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints

Edwin Tai Chiu Cheng
, Zhaohui Liu

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

17 Citations (Scopus)

Abstract

We consider in this paper the two-machine no-wait flowshop problem in which each machine may have an unavailable interval. We present 3/2-approximation algorithms for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap. These algorithms improve on existing results.

Original language	English
Pages (from-to)	161-165
Number of pages	5
Journal	Information Processing Letters
Volume	88
Issue number	4
DOIs	https://doi.org/10.1016/j.ipl.2003.08.002
Publication status	Published - 30 Nov 2003

Keywords

Approximation algorithms
Scheduling

ASJC Scopus subject areas

Computational Theory and Mathematics

More information

10.1016/j.ipl.2003.08.002

http://hdl.handle.net/10397/473

Cite this

@article{78b49a7c0c114cc0ba2dc2ffab6b2311,

title = "3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints",

abstract = "We consider in this paper the two-machine no-wait flowshop problem in which each machine may have an unavailable interval. We present 3/2-approximation algorithms for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap. These algorithms improve on existing results.",

keywords = "Approximation algorithms, Scheduling",

author = "Cheng, \{Edwin Tai Chiu\} and Zhaohui Liu",

year = "2003",

month = nov,

day = "30",

doi = "10.1016/j.ipl.2003.08.002",

language = "English",

volume = "88",

pages = "161--165",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - 3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints

AU - Cheng, Edwin Tai Chiu

AU - Liu, Zhaohui

PY - 2003/11/30

Y1 - 2003/11/30

N2 - We consider in this paper the two-machine no-wait flowshop problem in which each machine may have an unavailable interval. We present 3/2-approximation algorithms for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap. These algorithms improve on existing results.

AB - We consider in this paper the two-machine no-wait flowshop problem in which each machine may have an unavailable interval. We present 3/2-approximation algorithms for the problem when the unavailable interval is imposed on only one machine, or the unavailable intervals on the two machines overlap. These algorithms improve on existing results.

KW - Approximation algorithms

KW - Scheduling

UR - https://www.scopus.com/pages/publications/0142106799

U2 - 10.1016/j.ipl.2003.08.002

DO - 10.1016/j.ipl.2003.08.002

M3 - Journal article

SN - 0020-0190

VL - 88

SP - 161

EP - 165

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

3/2-approximation for two-machine no-wait flowshop scheduling with availability constraints

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this