Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine

Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine

0.00 Avg rating0 Votes
Article ID: iaor20031402
Country: United Kingdom
Volume: 30
Issue: 1
Start Page Number: 51
End Page Number: 62
Publication Date: Jan 2003
Journal: Computers and Operations Research
Authors: ,
Keywords: combinatorial analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.