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

32
Last Week
0
Last month
1
Citations as of Sep 10, 2017

WEB OF SCIENCETM
Citations

24
Last Week
0
Last month
0
Citations as of Sep 20, 2017

Page view(s)

52
Last Week
4
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



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