Report Number: CS-TN-98-87
Institution: Stanford University, Department of Computer Science
Title: Scheduling Algebra
Author: Glabbeek, R.J. van
Author: Rittgen, P.
Date: December 1998
Abstract: The goal of this paper is to develop an algebraic theory of
process scheduling. We specify a syntax for denoting
processes composed of actions with given durations.
Subsequently, we propose axioms for transforming any
specification term of a scheduling problem into a term of all
valid schedules. Here a schedule is a process in which all
(implementational) choices (e.g. precise timing) are
resolved. In particular, we axiomatize an operator
restricting attention to the efficient schedules. These
schedules turn out to be representable as trees, because in
an efficient schedule actions start only at time zero or when
a resource is released, i.e. upon termination of the action
binding a required resource. All further delay would be
useless. Nevertheless, we do not consider resource
constraints explicitly here. We show that a normal form
exists for every term of the algebra and establish soundness
of our axiom system with respect to a schedule semantics, as
well as completeness for efficient processes.