A scalable approach for estimation of resource availability using bitfields

Abstract

Determining the time when a resource will be available to perform a task is a fundamental sub-problem in a variety of scheduling applications. This paper describes a model of resource capacity and an efficient representation that together facilitate rapid estimation of the time when a resource is available. A special-purpose data structure called a bitfield is used to represent capacity in discrete time. Although the bitfield representation is simple, it closely matches facilities provided by the hardware, so that searches for available capacity can be executed very efficiently. Results demonstrate the scalability of the approach relative to other approaches that do not store data contiguously in memory and as a result require significantly more memory accesses to compute availability.