Coordination of Multiple Agents in Distributed Manufacturing Scheduling

Abstract

Distributed Problem Solving (DPS) is concerned with a group of agents, each with only local views, that cooperate and coordinate to solve a given problem in a coherent and efficient manner. As networked computer systems and practical concurrent processing architectures develop, DPS research has seen increasing realization in real world problems. As opposed to using sophisticated agents in problem solving, DPS approaches based on simple reactive agents have received growing interest. These reactive agents are simple in the sense that they do not have representations of their environments and they act by stimulus and response. They are embedded in the environment and follow simple patterns of behavior that can be easily programmed. Generating sophisticated group behavior from coordination and integration of activities of simple individuals has potentially great significance. This thesis presents DPS approaches based on reactive agents, and applied to scheduling in the domain of manufacturing job shops. In general, scheduling deals with organizing possibly related activities over time and limited resources. Scheduling problems occur in many domains, such as manufacturing, transportation, computer processing, communication, services, health care, education, etc. Distributed scheduling typically in concerned with coordinating among resources over processing of related activities in environments where knowledge and control distribution are desired. The objective of this work is the problem solving efficacy of reactive agents in terms of computational cost and solution quality. Our thesis is that multi-agent coordination techniques can provide substantial gains in terms of problem solving efficiency and solution quality. The main contributions of this research are the coordination schemes and the DPS techniques implemented in the two effective multiagent scheduling systems, CORA and COFCAST. In addition, CORA and COFAST are shown to provide equivilent or superior performance to competing centralized scheduling techniques, and therefore, enrich viable approaches to scheduling problems. In a broader view, this work supplements DPS research with innovative approaches to tightly coupled problems and successful demonstration of competetive performance. This work also provides an essential component for larger-scaled DPS research in manufacturing management and control.