Practice
Computing Applications

Self-Organization in Manufacturing Operations

Giving workpieces an active role in searching for processing steps by available machines in a manufacturing system.
Posted
  1. Introduction
  2. An Agent-based Control System
  3. Auctioning Off the Next Processing Steps
  4. Controlling the Workload of a Machine
  5. Avoiding Deadlocks
  6. P2000+ in Operation
  7. Lessons Learned
  8. References
  9. Authors
  10. Footnotes
  11. Figures
  12. Tables

Because of the increasing worldwide overcapacity in industry and the growing competition among suppliers, today’s manufacturing industries are facing a major shift from a supplier’s to a customer’s market. Aware of their market power, customers have become more demanding and less loyal to a particular brand. As a result, companies must shorten product life cycles, reduce time-to-market, increase product variety, and satisfy demand as fast as possible, while maintaining high quality and reducing investment costs. These trends have major consequences on the overall manufacturing process: It must become more flexible in coping with continuous product changes and increasingly volatile demand [1]. Additionally, the need to reduce total investment costs is still increasing and forces operations to better utilize its manufacturing equipment. Thus, at the same time, the manufacturing process should also become more robust with regard to any possible disturbance.

Under the leadership of DaimlerChrysler, an industrial consortium was formed to tackle these challenges for the automotive industry. The consortium developed a new kind of production system for flexible and robust large-series manufacturing, called Production 2000+ (or simply P2000+). This system consists of powerful computerized numerical control (CNC) machines installed along a flexible transportation system (see Figure 1).

The CNC machines operate with three, four, or five axes and can be equipped with different tools, thus covering a wide range of processing steps. The CNC machines are always configured in such a way that each production step can be performed by at least two different machines while avoiding any overcapacities at system level [2]. Thus, at any time, a workpiece can be processed by at least two machines so that a single machine failure never causes the whole production system to stop. This, however, presupposes that the transportation system must be as flexible as the machines. Instead of having just one conveyor, P2000+ has three parallel conveyors: forward, backward, and supply (see Figure 1). A workpiece passes the machines on the forward conveyor until it reaches its goal machine (the next machine that is supposed to process the workpiece). It is then moved by a shifting table from the forward conveyor to the supply conveyor, which moves the workpiece into the machine. The machine takes the workpiece off the supply conveyor, processes it, and puts it back onto the supply conveyor. From there, the workpiece moves to the next shifting table, which puts it either onto the forward or the backward conveyor, depending on the next goal machine. A shifting table is installed between every pair of adjacent machines in order to allow for individual supply of each machine.

Back to Top

An Agent-based Control System

A control system should always optimally utilize the hardware it controls. In the case of P2000+, this means that any control system should do its best at exploiting the high flexibility for processing workpieces. The approach DaimlerChrysler has chosen is known as late commitment: Workpieces are assigned to machines at the latest moment possible [1]. Perhaps the most fundamental decision in the design of the patented control system is that workpieces are given a rather active role in realizing this late commitment: a workpiece auctions off the next processing steps to the machines available, awards one of these machines, and repeats the overall procedure as soon as it is processed by the machine it has awarded.

As it turns out, the idea of an active workpiece fits very well the metaphor of an agent, generally conceived as a software component that is proactive rather than merely reactive [10]. According to the agent-oriented modeling methodology, every real-world object that is involved in some kind of pivotal decision making should be assigned a distinct software agent [3]. Figure 2 shows the different types of agents employed, including their main duties.

Back to Top

Auctioning Off the Next Processing Steps

As soon as a workpiece enters the manufacturing system, it auctions off the processing steps that are due first.1 This kind of auction is very similar to the well-known contract net protocol [9]. Before a workpiece starts any auction, however, it first determines the processing steps that are required next. To this end, the workpiece takes into account its current processing state, as well as a sequence graph describing which processing steps must be applied to the workpiece. The workpiece then sends an invitation to bid to all machines, where the call includes the processing steps required next. If a machine receives such a call, it first checks whether or not it is able to perform any of the requested processing steps. If this is the case, then the machine issues a bid; otherwise, it simply ignores the call. Short-term disturbances are not taken into account here, meaning the machine agent may bid even if the machine itself is currently down. This is because the subject of the auction is a future allocation of the workpiece’s next processing steps and the current situation does not provide much information about a machine’s future state.

The machine issues no bid without making sure it has the capacity to buffer a new workpiece. To this end the machine checks what we call its virtual buffer. The virtual buffer of a machine tracks not only the machine’s work in process, but also the blocked outbound stream of workpieces; the details, however, are deferred to the next section. If the machine’s virtual buffer happens to overflow, then the machine does not answer the call; otherwise, the machine sends a bid, including the following information: the current size of its virtual buffer and the subset of requested processing steps the machine is capable of performing. The workpiece then collects all bids. If there is no bid at all, the workpiece initiates a new auction; otherwise the workpiece ranks the bids and awards the best one. The lower the size of the virtual buffer, the better; and the more processing steps are offered, the better (with the former criterion having a higher priority). The workpiece repeats the overall procedure as soon as it has been processed by the machine that it has awarded.

Back to Top

Controlling the Workload of a Machine

Each machine manages two buffers, input and output. The input buffer contains all those workpieces that awarded this particular machine and have not been processed yet. This is the machine’s work in process. A machine’s output buffer tracks all those workpieces that have already been processed by the machine but have not yet been able to award an appropriate new machine. A workpiece moves from the input to the output buffer after it has been processed by the machine. The input and output buffer together constitute the virtual buffer of the machine (see Figure 3a).

We have just learned that, when awarding a machine for further processing, a workpiece always prefers machines with smaller virtual buffers. As any virtual buffer tracks the work in progress (input buffer), as well as the blocked outbound stream of workpieces (output buffer), load balancing takes into account these two criteria. This distinguishes the control system described here from those discussed in previous literature [4–6, 8].

But there is even more to the P2000+ control system than mere load balancing. A machine’s virtual buffer can be thought of as a funnel whose inbound stream is controlled by its outbound stream. As soon as the number of workpieces in the funnel has reached the upper limit of the virtual buffer, the machine no longer bids for new workpieces. This state persists until a workpiece is processed by the machine and eventually leaves the output buffer. That is, the inbound stream is constrained not only by the cycle time of the machine but also by the current capacity of subsequent machines. In fact, the only way for a workpiece to leave the virtual buffer is getting processed by that machine and awarding a new machine for the next processing steps.

One might object that as soon as the physical buffer capacity of the transportation system is at its limit, the inbound stream is adjusted to the outbound stream anyway. However, a transportation system that is at its physical limit is jammed. It usually takes a long time to resolve jams, thus leading to a loss of performance that may be even greater than the actual cause of the congestion. The point is therefore to adjust the throughput of the machines without forcing the transportation system to its physical limits.

But this is not even the end of the story. Funnels of the type just described are organized in a complex network induced by the admissible material flow (see Figure 3b). The current capacity bottleneck of the overall system propagates through this network in the opposite direction of the admissible material flow, eventually reaching the loading station. An interesting feature of this kind of backward propagation is that the topology of the network is not predefined; it is created dynamically by the workpieces when trying to auction off the next processing steps and by the machines that bid only if they are actually capable of carrying out at least one of the requested processing steps. This induces a network, such as the one in Figure 3b, which may even vary from workpiece to workpiece. But no matter what the network looks like, the current capacity bottleneck always propagates through the network of funnels, each of which limits its inbound stream by its outbound stream. This kind of control algorithm is therefore a truly self-organizing mechanism.


What the current capacity bottleneck always propagates through the network of funnels, each of which limits its inbound stream by its outbound stream.


Back to Top

Avoiding Deadlocks

The control system just described may run into a deadlock: A number of machines then find themselves in a cyclic dependency, each waiting for another machine to be ready to accept a new workpiece. Such a situation would cause a complete standstill of the production and may actually occur whenever the admissible flow of material is cyclic. Cycles in the material flow can be traced by ordering the machines according to the main manufacturing flow, thus partitioning the admissible flow into two disjoint subsets: the forward-directed main flow and the backward-directed minor flow—a distinction made in high-volume production anyway. If the main manufacturing flow is violated, then there is probably a cycle in the material flow (see Figure 3b).

Given this notion, the auction mechanism described earlier can be modified in such a way that it never runs into a deadlock: A machine bids even if the machine is actually not ready to accept a new workpiece because its virtual buffer is full. In such a case, however, a bid is not made without including in it an explicit overflow warning. Only if there is no other possibility, a workpiece may award a bid from the minor flow with an overflow warning—exactly the type of situation that may cause a deadlock not resolvable otherwise. In this case, the award is combined with a request to include the workpiece into the input buffer, irrespective of the current size of the virtual buffer. An enforcement award of this type resolves a deadlock, but also exceeds the upper bound of a machine’s virtual buffer. However, under certain general conditions, this violation of the machine’s individual upper bound never results in a violation of the sum of the upper bounds at system level; details can be found in [2].

Back to Top

P2000+ in Operation

In order to demonstrate the benefits of the new control approach, DaimlerChrysler conducted a large series of simulations based on real data from DaimlerChrysler’s manufacturing operations; in particular, product types, cycle times, and disturbance characteristics were authentic. The simulations have shown that the new control system is extremely robust against disturbances of machines, as well as failures of control units. When compared with the maximal throughput achievable in theory, the performance of our control system turned out to be nearly optimal. The table here summarizes the outcome of a typical simulation run. As indicated by these results, the control system was able to achieve approximately 99.7% of the theoretical optimum.2 At that time, existing manufacturing lines achieved at most 75% of the theoretical throughput.

After passing this benchmark, DaimlerChrysler installed in 1999 a flexible production system as a bypass to an existing large-series manufacturing line for cylinder heads. The control system deployed is basically the one described in this article, implemented and installed by Schneider Electric; for details, see [7]. However, one feature of the implementation worth mentioning here is that the shifting table agents run on the programmable logic controllers (PLCs) controlling the shifting tables, while all other types of agents run on industrial PCs.

The bypass has undergone a series of performance tests. The tests indicated the results of the simulations are still valid under actual manufacturing conditions: The prototype achieved nearly the same throughput as predicted by the simulation. The prototype was then moved to a different location to produce cylinder heads, while being augmented with two additional machines, as well as more handling devices. This prototype was in operation for five years up to the end of the life cycle of the cylinder heads. It thus demonstrated that the agent-based control system is able to fulfill industrial requirements even in day-to-day operations.

Back to Top

Lessons Learned

In spite of the very successful field test of the prototype, DaimlerChrysler has not installed a second P2000+ system. This might initially seem to be a contradiction. Here, we analyze why this is actually no contradiction at all.

The reason why the P2000+ has not experienced a widespread implementation at DaimlerChrysler is that a technical advantage is not necessarily an economic advantage, or, more precisely, an economically measurable advantage. Apart from the robustness of the system and the higher productivity resulting from this, the main advantage of the P2000+ system is its enormous flexibility with respect to changes (of products or manufacturing processes). Flexibility, however, is a future advantage that requires an immediate investment. The company must invest today in order to be prepared for upcoming changes. From an economic perspective, there are definitive costs, but only potential benefits. If the costs of the flexibility are higher than the increase of productivity, this is a weak business case.

Another aspect is that there are always technical alternatives, and this is also true for the P2000+ system. There seems to be no real alternative if one requires maximum flexibility: The P2000+ system is able to process nearly any kind of product. In practice, however, no more than two or three major product variants are ever produced on a single line simultaneously; thus, limited flexibility will often be sufficient. For such cases, there are currently alternatives (for example, gantry loading systems) that provide very limited flexibility but achieve comparable productivity gains without requiring a transportation system as costly as the one of P2000+. In fact, nearly all the manufacturing systems DaimlerChrysler has installed since the project P2000+ are of this type.

The bottom line is that agent technology is technically very attractive and, as in our case, can be very successful; however, in order to become a widespread application technology it is necessary to more closely look at the business aspects of the technology, in particular whether it truly creates an economic benefit. P2000+ did improve the overall throughput. However, alternative manufacturing systems, such as the gantry loading systems, do so too but at less investment costs (on the other hand, with no or very limited flexibility). The real advantage of the agent-based approach is thus flexibility, which is hardly measurable and sometimes not required.

This assessment is strongly biased toward the automotive industry. In different industries, the same system may have a quite different economic impact. But we believe that, in general, research projects should consider right from the beginning how a new technology will fit into the overall industrial landscape and what business advantages it will ultimately provide.

Back to Top

Back to Top

Back to Top

Back to Top

Figures

F1 Figure 1. P2000+ topology.

F2 Figure 2. Different types of agents employed.

F3A Figure 3a. Virtual buffer of a machine.

F3B Figure 3b. Network of funnels. The admissible material flow is divided into two disjoint sets: forward-directed main flow (solid arrows) and backward-directed minor flow (dotted arrows).

Back to Top

Tables

UT1 Table. Sample result of the simulation.

Back to top

    1. Bussmann, S. and McFarlane, D.C. Rationales for holonic manufacturing control. In Proceedings of the 2nd International Workshop on Intelligent Manufacturing Systems, (Leuven, Belgium, 1999), 177–184.

    2. Bussmann, S. and Schild, K. Self-organizing manufacturing control: An industrial application of agent technology. In Proceedings of the 4th International Conference on Multi-Agent Systems (ICMAS 2000), (Boston, MA, 2000), 87–94.

    3. Bussmann, S., Jennings, N.R., and Wooldridge, M. Multiagent Systems for Manufacturing Control—A Design Methodology. Springer, Berlin, Germany, 2004.

    4. Kis, T., Vancza, J., and Markus, A. Controlling distributed manufacturing systems by a market mechanism. In Proceedings of the 12th European Conference on AI (ECAI'96), (Budapest, Hungary, 1996), 534–538.

    5. Maley, J. Managing the flow of intelligent parts. In Robotics and Computer-Integrated Manufacturing 4, 3/4 (1988), 525–530.

    6. Parunak, H.V.D. et al. Kindrick: An architecture for heuristic factory control. In Proceedings of the American Control Conference, (Seattle, WA, 1986), 548–558.

    7. Schoop, R. and Neubert, R. Agent-oriented material flow control system based on DCOM. In Proceedings of the 3rd IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC 2000), 2000.

    8. Shaw, M. and Whinston, A. Task bidding and distributed planning in flexible manufacturing. In Proceedings of the 2nd Conference on AI Applications (CAIA'85), (Miami, FL, 1985), 184–189.

    9. Smith, R.G. The contract net protocol: High-level communication and control in distributed problem solving. In IEEE Transactions on Computers C-29, 12 (Dec. 1980), 1104–1113.

    10. Weiss, G., Ed. Multi-Agent Systems. MIT Press, Cambridge, MA, 1999.

    1Whenever understood, we ignore the distinction between an agent and the physical object it represents.

    2The optimal throughput assumes not only an ideal distribution of the overall flow, but also unbounded physical buffers.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More