A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

Liying Kang; Chi To Ng

doi:10.1016/j.ijpe.2006.11.014

A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

Liying Kang, Chi To Ng

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

45 Citations (Scopus)

Abstract

In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.

Original language	English
Pages (from-to)	180-184
Number of pages	5
Journal	International Journal of Production Economics
Volume	109
Issue number	1-2
DOIs	https://doi.org/10.1016/j.ijpe.2006.11.014
Publication status	Published - 1 Sep 2007

Keywords

Deteriorating jobs
Fully polynomial-time approximation scheme
Parallel-machine scheduling

ASJC Scopus subject areas

Business, Management and Accounting(all)
Economics and Econometrics
Management Science and Operations Research
Industrial and Manufacturing Engineering

More information

10.1016/j.ijpe.2006.11.014

Cite this

@article{2f196b638cca4fbb8d6fcfcd76e31f84,

title = "A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs",

abstract = "In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.",

keywords = "Deteriorating jobs, Fully polynomial-time approximation scheme, Parallel-machine scheduling",

author = "Liying Kang and Ng, {Chi To}",

year = "2007",

month = sep,

day = "1",

doi = "10.1016/j.ijpe.2006.11.014",

language = "English",

volume = "109",

pages = "180--184",

journal = "International Journal of Production Economics",

issn = "0925-5273",

publisher = "Elsevier",

number = "1-2",

}

TY - JOUR

T1 - A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

AU - Kang, Liying

AU - Ng, Chi To

PY - 2007/9/1

Y1 - 2007/9/1

N2 - In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.

AB - In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.

KW - Deteriorating jobs

KW - Fully polynomial-time approximation scheme

KW - Parallel-machine scheduling

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

U2 - 10.1016/j.ijpe.2006.11.014

DO - 10.1016/j.ijpe.2006.11.014

M3 - Journal article

VL - 109

SP - 180

EP - 184

JO - International Journal of Production Economics

JF - International Journal of Production Economics

SN - 0925-5273

IS - 1-2

ER -

A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Cite this