A note on scheduling the two-machine flexible flowshop

Edwin Tai Chiu Cheng; Guoqing Wang

doi:10.1109/70.744613

A note on scheduling the two-machine flexible flowshop

Edwin Tai Chiu Cheng, Guoqing Wang

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

8 Citations (Scopus)

Abstract

In this note we consider the NP-complete one-setup version of the two-machine flexible manufacturing cell scheduling problem studied by Lee and Mirchandani [5]. We provide a pseudopolynomial dynamic programming algorithm to solve the problem, thus establishing that the problem is NP-complete in the ordinary sense. We derive a tight worst-case error bound for the heuristic presented by Lee and Mirchandani, and propose another heuristic with a tight worst-case error bound of 3/2.

Original language	English
Pages (from-to)	187-190
Number of pages	4
Journal	IEEE Transactions on Robotics and Automation
Volume	15
Issue number	1
DOIs	https://doi.org/10.1109/70.744613
Publication status	Published - 1 Dec 1999

Keywords

Flexible manufacturing cell
Flowshop scheduling
Make-span minimization

ASJC Scopus subject areas

Control and Systems Engineering
Electrical and Electronic Engineering

More information

10.1109/70.744613

Cite this

@article{6380f5755c7c42bdb1195fee6368fa1f,

title = "A note on scheduling the two-machine flexible flowshop",

abstract = "In this note we consider the NP-complete one-setup version of the two-machine flexible manufacturing cell scheduling problem studied by Lee and Mirchandani [5]. We provide a pseudopolynomial dynamic programming algorithm to solve the problem, thus establishing that the problem is NP-complete in the ordinary sense. We derive a tight worst-case error bound for the heuristic presented by Lee and Mirchandani, and propose another heuristic with a tight worst-case error bound of 3/2.",

keywords = "Flexible manufacturing cell, Flowshop scheduling, Make-span minimization",

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

year = "1999",

month = dec,

day = "1",

doi = "10.1109/70.744613",

language = "English",

volume = "15",

pages = "187--190",

journal = "IEEE Transactions on Robotics and Automation",

issn = "1042-296X",

publisher = "IEEE",

number = "1",

}

TY - JOUR

T1 - A note on scheduling the two-machine flexible flowshop

AU - Cheng, Edwin Tai Chiu

AU - Wang, Guoqing

PY - 1999/12/1

Y1 - 1999/12/1

N2 - In this note we consider the NP-complete one-setup version of the two-machine flexible manufacturing cell scheduling problem studied by Lee and Mirchandani [5]. We provide a pseudopolynomial dynamic programming algorithm to solve the problem, thus establishing that the problem is NP-complete in the ordinary sense. We derive a tight worst-case error bound for the heuristic presented by Lee and Mirchandani, and propose another heuristic with a tight worst-case error bound of 3/2.

AB - In this note we consider the NP-complete one-setup version of the two-machine flexible manufacturing cell scheduling problem studied by Lee and Mirchandani [5]. We provide a pseudopolynomial dynamic programming algorithm to solve the problem, thus establishing that the problem is NP-complete in the ordinary sense. We derive a tight worst-case error bound for the heuristic presented by Lee and Mirchandani, and propose another heuristic with a tight worst-case error bound of 3/2.

KW - Flexible manufacturing cell

KW - Flowshop scheduling

KW - Make-span minimization

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

U2 - 10.1109/70.744613

DO - 10.1109/70.744613

M3 - Journal article

SN - 1042-296X

VL - 15

SP - 187

EP - 190

JO - IEEE Transactions on Robotics and Automation

JF - IEEE Transactions on Robotics and Automation

IS - 1

ER -

A note on scheduling the two-machine flexible flowshop

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this