Some results on resource constrained scheduling

Abstract

We consider a variant of the resource constrained scheduling problem, which originated from a machine scheduling problem. A number of jobs are to be processed on a single machine with a prespecified capacity. Each job has a size and a processing time, and the machine can process a set of jobs simultaneously as long as the total size of the jobs being processed does not exceed the capacity of the machine. The objective is to find a schedule to minimize the total time (i.e., the makespan) to complete all jobs, subject to the machine capacity constraint. For the problem where the machine is completely available at the starting time, we analyze a previously published algorithm and prove that the worst-case ratio of this algorithm is no more than 7/4, which significantly improves the previous result and thus answers an open question about this algorithm. For the problem where the machine is partially available at the beginning, an algorithm is shown to have a worst-case ratio of no more than two. An on-line algorithm is also presented.