Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/26603
Title: The time dependent machine makespan problem is strongly NP-complete
Authors: Cheng, TCE 
Ding, Q
Keywords: Computational complexity
Scheduling
Sequencing
Time dependence
Issue Date: 1999
Publisher: Pergamon Press
Source: Computers and operations research, 1999, v. 26, no. 8, p. 749-754 How to cite?
Journal: Computers and operations research 
Abstract: The computational complexity of the problem of scheduling a set of start-time dependent tasks with deadlines and identical decreasing rates of processing times on a single machine to minimize the makespan is open. In this paper we show that the problem is strongly NP-complete by a reduction from 3-Partition. Scope and purpose There has been increasing interest in scheduling models where the job processing times are a function of their starting times. There are many practical scheduling problems that can be modeled in this way. We study one such model where the job processing times decrease linearly with their starting times. The jobs have the same processing time decreasing rates but each job has an individual deadline which cannot be exceeded. The problem is to find a feasible schedule satisfying the deadline constraints that minimizes the makespan. This is an open problem in the literature and we show that it is strongly NP-complete. Thus, future research on this model should be focussed on the design of effective heuristics.The computational complexity of the problem of scheduling a set of start-time dependent tasks with deadlines and identical decreasing rates of processing times on a single machine to minimize the makespan is open. In this paper we show that the problem is strongly NP-complete by a reduction from 3-Partition.
URI: http://hdl.handle.net/10397/26603
ISSN: 0305-0548
EISSN: 1873-765X
DOI: 10.1016/S0305-0548(98)00093-8
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

8
Last Week
0
Last month
0
Citations as of Jul 29, 2017

WEB OF SCIENCETM
Citations

8
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

96
Last Week
1
Last month
Checked on Aug 14, 2017

Google ScholarTM

Check

Altmetric



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