The time dependent machine makespan problem is strongly NP-complete

Authors
Cheng, TCE Ding, Q
Citation
Tce. Cheng et Q. Ding, The time dependent machine makespan problem is strongly NP-complete, COMPUT OPER, 26(8), 1999, pp. 749-754
Citations number
8
Categorie Soggetti
Engineering Management /General
Journal title
COMPUTERS & OPERATIONS RESEARCH
ISSN journal
03050548 → ACNP
Volume
26
Issue
8
Year of publication
1999
Pages
749 - 754
Database
ISI
SICI code
0305-0548(199907)26:8<749:TTDMMP>2.0.ZU;2-Z
Abstract
The computational complexity of the problem of scheduling a set of start-ti me dependent tasks with deadlines and identical decreasing rates of process ing times on a single machine to minimize the makespan is open. In this pap er we show that the problem is strongly NP-complete by a reduction from 3-P artition. (C) 1999 Published by Elsevier Science Ltd. All rights reserved.