Parallel-machine scheduling with simple linear deterioration to minimize total completion time

Min Ji; Edwin Tai Chiu Cheng

doi:10.1016/j.ejor.2007.04.050

Parallel-machine scheduling with simple linear deterioration to minimize total completion time

Min Ji, Edwin Tai Chiu Cheng

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

76 Citations (Scopus)

Abstract

We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.

Original language	English
Pages (from-to)	342-347
Number of pages	6
Journal	European Journal of Operational Research
Volume	188
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2007.04.050
Publication status	Published - 16 Jul 2008

Keywords

Deteriorating jobs
FPTAS
Parallel-machine scheduling

ASJC Scopus subject areas

Information Systems and Management
Management Science and Operations Research
Statistics, Probability and Uncertainty
Applied Mathematics
Modelling and Simulation
Transportation

More information

10.1016/j.ejor.2007.04.050

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

Cite this

@article{890d7e6321e244aabd7812e631f73862,

title = "Parallel-machine scheduling with simple linear deterioration to minimize total completion time",

abstract = "We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.",

keywords = "Deteriorating jobs, FPTAS, Parallel-machine scheduling",

author = "Min Ji and Cheng, \{Edwin Tai Chiu\}",

year = "2008",

month = jul,

day = "16",

doi = "10.1016/j.ejor.2007.04.050",

language = "English",

volume = "188",

pages = "342--347",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Parallel-machine scheduling with simple linear deterioration to minimize total completion time

AU - Ji, Min

AU - Cheng, Edwin Tai Chiu

PY - 2008/7/16

Y1 - 2008/7/16

N2 - We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.

AB - We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years.

KW - Deteriorating jobs

KW - FPTAS

KW - Parallel-machine scheduling

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

U2 - 10.1016/j.ejor.2007.04.050

DO - 10.1016/j.ejor.2007.04.050

M3 - Journal article

SN - 0377-2217

VL - 188

SP - 342

EP - 347

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Parallel-machine scheduling with simple linear deterioration to minimize total completion time

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this