A cooperative repair method for a distributed scheduling system

Abstract

For some time, we have been studying the is-sues involved in job-shop scheduling in an envi-ronment of cooperative distributed agents, none of which has a complete view of the resources a~allable, or of the tasks to be scheduled. Sched-ules produced cooperatively by such distributed agents using constraint satisfaction methods are often not optimal because of the inherent asyn-chronicity 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 cou-pled distributed processing methods are supple-mented with a tightly coupled parallel repair pro-cess. V~Ie cxplorc the implications on the repair process of a distributed environment in which the designer of the repair algorithm must ad-dress issues of agent communication and orga-nization. We describe a search algorithm and a set of heuristics for guiding the repair process and present some experimental results in the con-text of the Distributed ARM, an airline resource scheduling systcm.