ISSN:
1572-9338
Keywords:
multi-agent problem solving, coordination, production scheduling
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract The new challenges of "Agile Manufacturing" and distributed decision making entailed by decentralized organizations led to our interest in the study of computational cooperative problem solving models and coordination techniques for distributed production management. The goal of our research is to address the technical need of distributed production management and develop appropriate computational approaches to support adaptive, cost-effective responsiveness. In particular, we focus on the challenging problem of job shop scheduling, which has been one of the primary foci of production scheduling research. This paper presents a multi-agent problem solving model and an effective coordination technique for job shop scheduling. The model involves a group of agents; each agent is associated with either a job or a resource. A solution to a production scheduling problem is the result of coordinated conflict resolution in the iterative and asynchronous multi-agent decision making process. It is well known in distributed systems research that for tightly interacting, non-decomposable problems, such as job shop scheduling, the need for communicating partial solution results among parts of the system rapidly degrades system performance. On the other hand, limiting communication degrades solution quality. One can limit communication by employing shared memory, but this has the drawback that the shared memory becomes a bottleneck and, in addition, using shared memory limits decentralization. In our approach, we judiciously balance the above concerns. We limit interagent communication through a scheme that employs efficient, small and distributed shared memories, each of which is associated with and shared by a limited number of agents. We also exploit problem characteristics (e.g. disparity among subproblems) to design an effective coordination technique for the job shop scheduling problem. We have evaluated the utility of our approach through extensive experimentation on a variety of job shop constraint satisfaction and optimization problems with different optimization objectives. Our results show that our approach outperforms or gives comparative results with other state-of-the-art scheduling techniques on benchmark problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1018911613698
Permalink
