A Cooperative Repair Method for a Distributed Scheduling System

Proceedings Of The Third Artificial Intelligence Planning Systems Conference

Volume

Proceedings Of The Third Artificial Intelligence Planning Systems Conference

Contents

For some time, we have been studying the issues involved in job-shop scheduling in an environment of cooperative distributed agents, none of which has a complete view of the resources available, or of the tasks to be scheduled. Schedules produced cooperatively by such distributed agents using constraint satisfaction methods are often not optimal because of the inherent asynchronicity of the distributed scheduling process, the bounded rationality of the scheduling agents, and the difficulty in completely integrating meta-level heuristics into an agent’s local scheduling processes. This paper describes a modification to distributed scheduling in which the loosely coupled distributed processing methods are supplemented with a tightly coupled parallel repair process. We explore the implications on the repair process of a distributed environment in which the designer of the repair algorithm must address issues of agent communication and organization. We describe a search algorithm and a set of heuristics for guiding the repair process and present some experimental results in the context of the Distributed ARM, an airline resource scheduling system.