Paper Info
Title
On the complexity of interval scheduling with a resource constraint
Abstract
We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job j are: a fixed start time s"j, a fixed finish time f"j, and a resource requirement r"j. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, the problem is to decide whether a feasible schedule for all jobs exists or not. We discuss such a decision problem and prove that it is strongly NP-complete even when the number of resources are fixed to any value R=2. Moreover, we suggest an implicit enumeration algorithm which has O(nlogn) time complexity in the number n of jobs when the number m of machines and the number R of resources per machine are fixed. The role of storage layout and preemption are also discussed.
Year
DOI
Venue
2011
10.1016/j.tcs.2011.03.025
Theor. Comput. Sci.
Keywords
DocType
Volume
parallel identical machine,number R,decision problem,value R,Complexity,Scheduling,fixed start time,fixed finish time,Resource allocation,R unit,number m,number n,Fixed job scheduling,resource constraint,time complexity,interval scheduling
Journal
412
Issue
ISSN
Citations 
29
Theoretical Computer Science
13
PageRank 
References 
Authors
0.61
9
2
Name
Order
Citations
PageRank
Enrico Angelelli129120.58
Carlo Filippi216813.77