Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/27449
Title: Parallel-machine scheduling of simple linear deteriorating jobs
Authors: Ji, M
Cheng, TCE 
Keywords: Computational complexity
Makespan
Parallel-machine scheduling
Total machine load
Worst-case bound
Issue Date: 2009
Publisher: Elsevier
Source: Theoretical computer science, 2009, v. 410, no. 38-40, p. 3761-3768 How to cite?
Journal: Theoretical computer science 
Abstract: We consider parallel-machine scheduling problems in which the processing time of a job is a simple linear increasing function of its starting time. The objectives are to minimize the makespan, total machine load, and total completion time. We show that all the problems are strongly NP-hard with an arbitrary number of machines and NP-hard in the ordinary sense with a fixed number of machines. For the former two problems, we prove that there exists no polynomial time approximation algorithm with a constant worst-case bound when the number of machines is arbitrary unless P = N P. When the number of machines is fixed, we propose two similar fully polynomial-time approximation schemes for the former two problems.
URI: http://hdl.handle.net/10397/27449
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2009.04.018
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

40
Last Week
0
Last month
1
Citations as of Dec 7, 2018

WEB OF SCIENCETM
Citations

30
Last Week
0
Last month
0
Citations as of Dec 15, 2018

Page view(s)

82
Last Week
0
Last month
Citations as of Dec 10, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.