Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/1082
Title: | Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine | Authors: | Cheng, TCE Ding, Q |
Issue Date: | Jan-2003 | Source: | Computers and operations research, Jan. 2003, v. 30, no. 1, p. 51-62 | Abstract: | In this paper, we study the feasibility problem of scheduling a set of start time dependent tasks on a single machine with deadlines, processing rates and identical initial processing times. First, we show that the cases with arbitrary deadlines are strongly NP-complete. Second, we show that the cases with two distinct deadlines are NP-complete in the ordinary sense. Finally, we give an optimal polynomial algorithm for the makespan problem with two distinct processing rates. We solve a series of open problems in the literature and give a sharp boundary delineating the complexity of the problems. | Keywords: | Sequencing Time dependence scheduling Computational complexity |
Publisher: | Pergamon Press | Journal: | Computers and operations research | ISSN: | 0305-0548 | EISSN: | 1873-765X | DOI: | 10.1016/S0305-0548(01)00077-6 | Rights: | Computers & Operations Research © 2002 Elsevier Science Ltd. The journal web site is located at http://www.sciencedirect.com. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
initial_140701.pdf | Pre-published version | 145.65 kB | Adobe PDF | View/Open |
Page views
132
Last Week
2
2
Last month
Citations as of Apr 14, 2024
Downloads
221
Citations as of Apr 14, 2024
SCOPUSTM
Citations
32
Last Week
0
0
Last month
0
0
Citations as of Apr 19, 2024
WEB OF SCIENCETM
Citations
29
Last Week
0
0
Last month
0
0
Citations as of Apr 18, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.