Abstract

Workflow applications are involved with sequencing activities, monitoring and routing jobs, and coordinating work schedules. These applications must often track changing information about temporal relationships, and maintain a correct set of dependencies among those relationships during the workflow (Egger and Wagner, 1992). Constraint propagation provides a mechanism for updating temporal relationships. Research in temporal reasoning has focused on the problem of constraint propagation, especially for interval-based temporal relations (Allen, 1983; Kautz and Ladkin, 1991). Allen’s model of interval- based temporal relations (1983) uses a transitivity table to infer sets of possible relations among any three events. For example, if we know that A occurs before B, and B occurs during C, then A and C may participate in any of the following relations: before, overlaps, meets, during, and starts. We do not know which relation is correct, however, until we receive additional information about A and C; we have only a set of constraints on the possible truthfulness of the system’s state. As new information is introduced in the form of additional temporal relations (e.g., a work schedule being “firmed up”), the network of temporal constraints needs to be re-computed and checked for correctness. Thus new information about A and C means that previous relations produced from the transitivity table can be eliminated, and relations between C and B need to be re-computed.

Download

Share

COinS