Temporal reasoning in workflow systems

In a workflow system, autonomous agents perform various activities cooperatively to complete a common task. Successful completion of the task often depends on correct synchronization and scheduling of agents' activities. It would greatly enhance the capabilities of current workflow systems if quantitative temporal constraints on the duration of activities and their synchronization requirements can be specified and reasoned about. This paper investigates such requirements and related reasoning algorithms. In particular, the paper studies the consistency, prediction and enactment services in a workflow system, and provides corresponding algorithms. The consistency service is to ensure that the specification of the temporal constraints is possible to satisfy; the prediction service is to foretell the time frame for the involved activities; and the enactment service is to schedule the activities so that, as long as each agent starts and finishes its task within the specified time period, the overall constraints will always be satisfied. For the enactment service, the paper identifies two practically interesting families of enactment schedules for autonomous agents, namely "free schedules" and "restricted due-time schedules". In a free schedule, an agent may use any amount of time to finish the task as long as it is between the minimum and maximum time declared by the agent when the workflow is designed. A restricted due-time schedule is a more restrictive one in which the maximum amount of time that an agent may use is limited to a smaller number than the declared maximum. The paper presents efficient algorithms to find free and restricted due-time schedules. The paper also provides algorithms for the above services when multiple time granularities are involved in the temporal constraint specification.