Scheduling under Resource Constraints

The scheduling model we consider now is more complicated than the previous ones, because any task, besides processors, may require for its processing some additional scarce resources. Resources, depending on their nature, may be classified into types and categories. The classification into

types

takes into account only the functions resources fulfill: resources of the same type are assumed to fulfill the same functions. The classification into

categories

will concern two points of view. First, we differentiate three categories of resources from the viewpoint of resource constraints. We will call a resource

renewable

, if only its total usage, i.e. temporary availability at every moment, is constrained. A resource is called

non-renewable

, if only its total consumption, i.e. integral availability up to any given moment, is constrained (in other words this resource once used by some task cannot be assigned to any other task). A resource is called

doubly constrained

, if both total usage and total consumption are constrained. Secondly, we distinguish two resource categories from the viewpoint of resource divisibility: discrete (i.e. discretely-divisible) and

continuous

(i.e. continuously-divisible) resources. In other words, by a discrete resource we will understand a resource which can be allocated to tasks in discrete amounts from a given finite set of possible allocations, which in particular may consist of one element only. Continuous resources, on the other hand, can be allocated in arbitrary, a priori unknown, amounts from given intervals.