Affiliations: [a] School of Computer Science, University of Oklahoma, Norman, OK, USA | [b] School of Industrial Engineering, University of Oklahoma, Norman, OK, USA
Correspondence:
[*]
Corresponding author: Scott Moses, School of Industrial Engineering, University of Oklahoma, 202 West Boyd Street, Room 124, Norman, OK 73019-1022, USA. Tel.: +1 405 325 8698; Fax: +1 405 325 7555; E-mail: [email protected].
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.
