IIS Library: TR-IIS-07-001 Abstract

TR-IIS-07-001 Fulltext

Consistency and Feasibility of Flexible Demand-Supply Constraints

P. H. Tsai and J. W. S. Liu

Abstract

A general schedule specification (GSS) defines constraints on sizes and temporal separation of individual dispatches and upper and lower bounds on the total size of dispatches in specified time intervals. A dispatch may be a dispensing of medications to an individual, a delivery of some fresh produce to a green grocer, the transmission of a multimedia data element to a web surfer, and so on. When given a GSS, the scheduler can choose any schedule that the meets the constraints defined by the specification. The GSS is consistent if the constraints defined by it do not conflict with each other and is feasible if there is a schedule that meets all constraints. This paper describes conditions and algorithms which the scheduler can use to determine whether the specification is consistent and feasible and to schedule dispatches according to the GSS.