On the complexity of interval scheduling with a resource constraint

https://doi.org/10.1016/j.tcs.2011.03.025Get rights and content
Under an Elsevier user license
open archive

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 sj, a fixed finish time fj, and a resource requirement rj. 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 R2. 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.

Keywords

Scheduling
Fixed job scheduling
Resource allocation
Complexity

Cited by (0)

1

Tel.: +39 0302988576; fax: +39 0302400925.