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
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.
András Márkus, József Váncza,
Tamás Kis - MTA SZTAKI
Tel: +36 1 1810 194
return to the contents page