Coordination of Multiple Agents in Distributed Manufacturing Scheduling

Jyi Shane Liu
doctoral dissertation, tech. report CMU-RI-TR-96-16, Robotics Institute, Carnegie Mellon University, April, 1996

  • Adobe portable document format (pdf) (7MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Sponsor: ARPA
Grant ID: F30602-90-C-0119, F33615-93-1-1330
Number of pages: 179

Text Reference
Jyi Shane Liu, "Coordination of Multiple Agents in Distributed Manufacturing Scheduling," doctoral dissertation, tech. report CMU-RI-TR-96-16, Robotics Institute, Carnegie Mellon University, April, 1996

BibTeX Reference
   author = "Jyi Shane Liu",
   title = "Coordination of Multiple Agents in Distributed Manufacturing Scheduling",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   month = "April",
   year = "1996",
   number= "CMU-RI-TR-96-16",
   address= "Pittsburgh, PA",