Bounds for Multiprocessor Scheduling with Resource Constraints

Abstract

One well-studied model of a multiprocessing system involves a fixed number n of identical abstract processors, a finite set of tasks to be executed, each requiring a specified amount of computation time, and a partial ordering on the tasks which requires certain tasks to be completed before certain others can be initiated. The nonpreemptive operation of the system is guided by an ordered list L of the tasks, according to the rule that whenever a processor becomes idle, it selects for processing the first unexecuted task on L which may validly be executed. We introduce an additional element of realism into this model by postulating the existence of a set of “resources” with the property that for each resource, the total usage of that resource at any instant of time may not exceed its total availability. For this augmented model, we determine upper bounds on the ratio of finishing times achieved using two different lists, L and $L'$, and exhibit constructions to show that the bounds are best possible.