We consider a scheduling problem where jobs have to be carried out by parallel identical machines. The attributes of a job are: a fixed start time , a fixed finish time , and a resource requirement . Every machine owns 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 . 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 . Moreover, we suggest an implicit enumeration algorithm which has time complexity in the number of jobs when the number of machines and the number of resources per machine are fixed.
The role of storage layout and preemption are also discussed.