ERCIM News No.26 - July 1996 - SZTAKI

A Market-Based Control in Distributed Manufacturing

by András Márkus, József Váncza and Tamás Kis

A market mechanism has been defined and developed into a prototype system for coordinating the activities of intelligent agents in dynamic order processing and scheduling of discrete manufacturing systems.

In discrete manufacturing developments of information technology led to factories that carry on manufacturing in a computer integrated way. These architectures are of high structural and dynamic complexity, so it is no wonder that the increased turbulence in economy disfavors their rigid control structures. No matter how, it is next to impossible to be prepared with pre-programmed, top-down responses to abrupt changes and to complete real-time computations on sophisticated decision models before the results themselves are invalidated. For some time, there is a complementary trend that aims at cooperative manufacturing - our research belongs to this direction.

In distributed control, autonomous agents rely on their own situation assessment in deciding the course of actions to take and how to attune their actions with those of the others. The primary concern of the agents is to do the best for themselves, however, the extent to which their individual goals can be fulfilled depends on the actions of the entire community: in general, high level overall performance serves the individual goals. Thus inclination to cooperation and altruism may serve not only the interests of the others, but the individual goals and the system wide objectives as well.

Job shops are typical manufacturing environments for producing low volume or high variety products under dynamic, scattered demand. Job shop scheduling is a complex constrained optimization problem: one has to find a task-machine assignment that satisfies the capacity and precedence constraints and approaches some global performance objective. The main difficulty is caused by job interactions as the jobs compete for limited machining resources. In the dynamic case (the case we are actually dealing with) no complete specification of the problem is known ahead and scheduling decisions must be made on the fly, considering the actual state of the system.

We have developed a market mechanism which enables the distributed control of job shops. Particularly, we investigate a production planning and control problem that integrates dynamic order processing and dynamic job shop scheduling. There are two kinds of agents defined: the first is the Management that interacts with the outside world by selecting orders and making the administration and accounting of the accepted orders. The second kind of agents is the Machine; in the model of the job shop there are several machine agents, each having different technological capacities. The agents try to maximize their own profit; however, the profitability of each agent depends on the whole system's performance as well.

The agents and the messages

The agents know their own state of affairs only, consider their schedule variants as branching futures, and communicate under a simple and reasonable set of market rules. These rules of the game define a negotiation process and say, among other things, that each agent has to make decisions that are rational, at least, in a local way. Coalitions may not be formed. Collective responsibility, eg, in the case of lateness of jobs in progress due to the machines preferring new, more promising jobs, is inspired by a penalty mechanism.

At the present, rather early stage of work we are making systematic experiments. The ways of comparing our results with those of some other approaches are far from being obvious, since there is an unusual flexibility allowed in our model. However, we deem that just these features could make our approach a practical one if applied in an actual manufacturing environment.

Up to now, above research has not belonged to any kind of concerted action; we are open to participate with it in some form of joint research.

Please contact:
András Márkus, József Váncza,
Tamás Kis - MTA SZTAKI
Tel: +36 1 1810 194

return to the contents page