Task scheduling based on probabilistic constraint propagation for distributed workflow enactment

Several architectures for decentralized workflow enactment have been proposed to improve workflow execution through cooperation of geographically distributed agents. To our knowledge, none of them solves the problem of dynamic task scheduling in trans-organizational relations, which are characterized by a limited observability of the global workflow execution state, due to confidentiality reasons. We present a new distributed dynamic scheduling approach for workflow execution in an inter-enterprise context, based on the multi-agent paradigm. We use three types of agents: proactive agents for supervision, reactive agents for resource management and mobile agents for task execution. Apart from essential task constraints that are propagated as probability values, the state of one participant´s workflow instance is hidden from business partners. We implemented the methodology in a multi-agent test bed and executed a number of randomly generated workflows. Results show that the optimal schedule is found in a large majority of test runs, in spite of limited observability