Optimization for manufacturing system based on Pheromone

Published Online June 2011 in MECS

In the current manufacturing environment, manufacturing systems are complex, dynamic, stochastic systems with a wide variety of products, processes, production levels, and unforeseen disturbances as well. These disturbances include: the arrival of new orders, order cancellations, changes in order priority, processing delays, changes in release dates, machine breakdowns, and the unavailability of row materials, personnel, or tools [1, 2]. Hence, such dynamic manufacturing systems require dynamic coordination and control.

The traditional manufacturing control architectures are not designed to exhibit good agility and adaptation. In fact, their centralized and hierarchical control approaches present good production optimization, but the rigidity and centralization of the control structure implies a weak response to disturbances. Therefore the substitutional heterarchical control architecture has been proposed and investigated [3, 4].On the other hand, heterarchical manufacturing control architecture presents a good response to change and unpredictable disturbances, but as autonomous manufacturing cells have different information, knowledge, goals and understanding of current situations, and decisions are based in partial knowledge of the system, their action plan may be disparate or even conflictive. Therefore the global production optimization is not guaranteed [5].Thus we need a good coordination mechanism to coordinate and integrate the behavior of all cells and get coherent system behavior and optimize system performance.

Inspired by the collective behavior of ant colonies, this paper uses an indirect coordination and control mechanism, called stigmergy or pheromone, to optimize manufacturing system performance.

• II.    Problem modeling for manufacturing system

Generally speaking, a manufacturing plant consists of many manufacturing cells. A task can be finished by any cell, the problem is how to make the total cost minimal and balance the loading rate of each cell. Therefore, it is a typical multi-objective optimizing problem. Since these objectives are conflicting, a solution may perform well for one objective, but giving bad results for others. For this reason, any proposed task allocation approach has to find a compromise between them.

In this section, a mathematical model is described firstly. The notations of this model are: j : work piece;

i : manufacturing cell;

k : machine in cell i ;

tjik : processing time of work piece j on machine k of cell i;

d_j : due date of work piece j ;

c_ji : the completion time for work piece j in cell i ;

cjik : the completion time for work piece j on machine k of cell i, cjik = cji(k-1) + j;

a j. : processing cost per time unit for work piece j in cell i ;

в ji : storage charge per time unit for work piece j in cell

i ;

Y ji : delay charge per time unit for work piece j in cell i ;

Q_j : quantity of work piece j in an order;

T ji = max(0, c ji — d j ) : the tardiness time of work piece j in cell i ;

Eji = max(0, dj — Cji) : the earliness time of work piece j in cell i;

• f ₁ : total cost of an order in cell i ;

• f ₂ : processing cost for Q_j in cell i ;

• f ₃ : storage cost for Q_j in cell i ;

• f ₄ : tardiness cost for Q_j in cell i ;

• f ₅ : the loading rate of cell i .

The model for the total cost of an order can be described as:

f = f2 + f3 + f4

m

• ^f 2 = E “Л t jik ^{X Q}j

k=1

f 3 = E ji x p ji x Q j

• ^f 4 = T ji ^x Y ji ^{x Q}j

^max{ t jik ^{} x} Q j.

■ f5

Eq.(1) presents the total cost which is composed of the processing cost for an order (Eq.(2)), the storage cost (Eq.(3)) and the tardiness cost (Eq.(4)). The processing cost is the production of the machine cost per unit time, the required processing time for each work piece and the quantity of work piece in an order (Eq.(2)). The storage or the tardiness cost is the product of the difference between actual finishing time and the due time, the unit storage or tardiness, and the quantity of work piece in an order (Eq.(3) and the tardiness cost Eq.(4)). Eq.(5) presents the largest loading rate of cell i must less than 1.

• III. Pheromone-based optimization for

MANUFACTURING SYSTEM

This coordination is based on the sign-based stigmergy of food foraging ants to integrate the shop floor control system. Pheromones are used as communication mediator. Since those ant agents are not able to perform a direct communication, ant agents need to lay down pheromones in the environment to let other ant agents interpret, and take them into consideration during decision-making. In order to spread pheromones, physical agents (product, order, cell and resource agents) create ant agents. These ant agents travel virtually across the plant topology to retrieve and disseminate information analogous to the food foraging ants from an ant colony.

In this coordination process, ant agents have a specified propagation direction. They can move ‘‘upstream’’ or ‘‘downstream’’ through the distributed location and carry a pheromone with them in the direction. Ant agents from cell agents move upstream and ant agents from order agents move downstream. And the pheromone is updated and stored at a given frequency on public blackboard in order to be utilized by local cell agents.

The pheromone information, which is transferred from shop floor agent downstream can be represented triple as ( o , p , i ), where

• (1)    o is the order information, including order type, the quantity of the order.

• (2)    p is the product information, including product type, the quantity of the product.

• (3)    i is the processing information, including processing steps and needing machines, processing cost and due date, etc.

However, the pheromone information, which is transferred from cell agents upstream can be represented triple as (cell_ID, c , l ), where

• (1)    cell_ID is the cell identifier.

• (2)    c is the total processing cost.

• (3)    l is the information of loading rate of cell.

As soon as an order arrives at the shop floor, each order agent creates an order ant agent. And the order ant agent carries the following information: (o, p, i). With this information, the order ant’ agent follows the steps below to find an attractive cell to be finished:

Step 1: an order ant agent lays down the pheromone information ( o , p , i ) on the public blackboard.

Step 2: each cell agent creates a cell ant agent to perceive the information ( o , p , i ).

Step 3: If each cell has the capability to finish it, then each cell ant agent carries the pheromone information (cell_ID, c , l ) upstream and lays down on the public blackboard.

Step 4: When order ant agent has found a proper processing cell with the minimal processing cost to reserve, the order agent ant checks whether it is reserved before.

If (an order ant agent has not yet reserved the cell) Then {

Reserve the pheromone information (cell_ID, c , l ) of this cell;

}

Else

{

Order ant agent has to do a validity check:

{

If ( l ＜ 1) Then

{

Dispatch this order to this cell_ID, and update the pheromone information (cell_ID, c , l ).

}

If ( l ＞ 1) Then

{

Dispatch this order to other cell-ID, which has a good compromise between processing cost and loading rate, and reserve the pheromone information (cell_ID, c , l ).

}

}

}

Step 5: Place the pheromone on the public blackboard that informs the order agent about its selecting result. Step 6: Repeat from Step 1 to Step 5;

Step 7: Stop until all orders select proper cell to finish them.

• IV. Adaptation control for disturbances

There are many sources of uncertainty in real-world manufacturing system, which trigger disturbance events in dynamic adaptation control manufacturing system. Generally speaking, there are two types of disturbances, namely, resource-related disturbance, and source-related disturbance [1].

• (1)    Resource-related disturbance refers to the disturbance caused by unreliability coming from resources (machines) in the shop, including machine breakdown and machine recovery. The unreliability is expressed in terms of mean time between failure (MTBF) and the mean time to repair (MTTR).

• (2)    Source-related disturbance refers to the disturbance caused by the changes in production orders, including new order/job arrival and existing order/job cancellation.

The resource-related disturbance is considered in this work. Fig.1 shows the progress of adaptive coordination and control the condition of a malfunction machine by using pheromone like techniques.

• (1)    In stationary state (Fig.1 (a)), task allocation is executed by using pheromone-based coordination and control techniques mentioned in section 4.2.

• (2)    In the case of a machine malfunction ( m 3 ) (Fig.1 (b)), the operational entity creates an ant agent to propagate pheromone information to its cell controller firstly during recovering from the malfunction, the pheromone information includes the order number, unfinished quantities and required machine type.

• (3)    And then, the cell controller creates a number of cell ant agents to propagate the pheromone information to other cell controllers (coordination controllers) and the upper level shop floor controller (supervisory controller). Other cell controllers and the supervisory controller sense the pheromone information.

• (4)    For those cells with similar types of machines, which have abilities to finish the related task, their related cell controllers will create cell ant agents to propagate the pheromone information to the needing cooperation cell, the pheromone information includes the finished time, processing cost, loading rate and machine number.

• (5)    Aiming at the pheromone information submitted by other cell ant agents, the cell ant agent will make comprehensive comparison by combining the finished time, processing cost with loading rate of each cell, then selects a proper machine ( m 4 ), as shown in Fig.1 (c), to process the task, which needs to be processed on the malfunction machine ( m ₃ ).

• (6)    If there are conflicts in the use of machines, the supervisory controller will stand out to resolve conflicts among schedules. Finally they reorganize themselves into different dynamic logical manufacturing cells.

• (7)    After the recovery from the malfunction, the operational entity ends the propagation of the pheromone information, and the system evolves to the initial distributed control structure, as shown in Fig.1 (a).

it can be found from the above mentioned that, like the task allocation and scheduling process, abnormal conditions are also handled by using pheromone like techniques. Also, deadlocks that may occur among cell controllers during the negotiation period can be avoided by using this technique. To sum up, the coordination and control for manufacturing system based on pheromone technique embodies good agility, controllability, stability, intelligence, adaptability, and robustness.

(a) Initial state of the hybrid control structure

(b) Coordination and control based on Pheromone-like Techniques

(c) Dynamic adaptive coordination control result

Figure 1 Coordination and control using Pheromone-like Techniques

• IV. Example and results

In this section, an example for task allocation with four orders is used to test the proposed coordination and control mechanism based on the pheromone approach. There are three manufacturing cells and twelve machines which include three machines 1, three machines 2, three machines 3 and three machines 4. Each cell include four machines, namely, one machine 1, one machine 2, one machine 3 and one machine 4.The production information is shown in Table I. Each order can be finished by any cell, taking order A001 for example, it can be machined in cell_1, and the production sequence of the order A001 in cell_1 is machine 2, machine 3 and machine 4. The required processing time for machine 2 of cell_1 is 18 time unit. The required processing cost per time unit is 25, and others have the same meaning. Table II shows information of due date, storage cost per time unit and tardiness cost per time unit about orders.

According to the steps mentioned in section 4.2, the concrete steps are shown as following:

Step 1, an order A001 ant agent moves downstream and lays down the pheromone information ( o , p , i ) on the public blackboard.

Step 2, each cell agent of the three creates a cell ant agent respectively to perceive the information ( o , p , i ).

Step 3, after transferring to the computing result information, each cell ant agent carries the pheromone information (cell_ID, c , l ) upstream and lays it down on the public blackboard, namely, cell_1 pheromone information is (cell_1, 6915, 0.51), cell_2 pheromone information is (cell_2, 5063, 0.65), and cell_3 pheromone information is (cell_3, 6545, 0.43).

Step 4, the order A001 ant agent perceives the pheromone information placed by three cell ant agents, and selects a proper cell, namely, cell_2, to finish it.

Step 5, the order A001 ant agent checks whether it is reserved before. If not, reserve the cell_2 pheromone information; if pheromone information of the cell_2 has been reserved, then update its loading rate information, and checks whether l ＞ 1, if not, then the order A001 selects cell_2 to finish it, if l ＞ 1, then select other proper cell to finish it.

Step 6, repeat step 3- step 5, and at last, because the cell_2 has the minimal cost and its loading rate l ＜ 1, the order A001 select cell_2 to finish it.

By using the same approach, each order can select a satisfied cell to process it. The selecting results are shown in Table III.

As mentioned above, the major objectives for task allocation is to minimize the production cost and ensure that the loading rate of each manufacturing cell is less than 1. From this example, it can be found that orders A001 and A003 select cell_2 to process them, because cell_2 can process them with the least production cost, what’s more, its loading rate is less than 1, as shown in Table III. Similarly, orders A002 and A004 select cell_3 to process their jobs, although the cell_2 has the least production cost, its loading rate is bigger than 1, therefore, they don’t select cell_2 to process them. In addition, the communication overhead can be reduced remarkably compared with contract net protocol.

T able I.

THE PRODUCTION INFORMATION ABOUT ORDERS

Order_ID	Quantity	Cell_ID	Production sequence/machine/processing time /cost per time unit
A001	6	1	1/2/18/25	2/3/12/20	3/4/15/30
		2	1/1/25/10	2/2/15/15	3/3/12/30
		3	1/2/15/25	2/3/10/25	3/4/15/30
A002	4	1	1/2/18/25	2/3/12/20	3/4/15/30
		2	1/1/25/10	2/2/15/15	3/3/12/30
		3	1/2/15/25	2/3/10/25	3/4/15/30
A003	3	1	1/2/18/25	2/3/12/20	3/4/15/30
		2	1/1/25/10	2/2/15/15	3/3/12/30
		3	1/2/15/25	2/3/10/25	3/4/15/30
A004	5	1	1/2/18/25	2/3/12/20	3/4/15/30
		2	1/1/25/10	2/2/15/15	3/3/12/30
		3	1/2/15/25	2/3/10/25	3/4/15/30

T able II ．

THE DUE DATE AND OTHER INFORMATION ABOUT ORDERS

Order_ID	Storage cost per time unit	Tardiness cost per time unit	Due time
A001	1	2	210
A002	1	2	230
A003	1	2	285
A004	1	2	240

T able III ．

THE SELECTING RESULTS FOR ORDERS

Order_ID	Due time	Cell_1		Cell_2		Cell_3		Select results
		cost	l	cost	l	cost	l
A001	210	6915	0.51	5063	0.65	6545	0.43	Cell_2
A002	230	4691	0.31	3434	1.09	4445	0.26	Cell_3
A003	285	3651	0.19	2533	0.89	3380	0.46	Cell_2
A004	240	5823	0.38	4449	1.46	5455	0.67	Cell_3

• VI. Conclusion

In this paper an indirect cooperation and control mechanism for manufacturing system is presented that is based on coordination mechanism inspired by social insects. According to that, a pheromone-based task allocation and coordination control scheme was introduced. Based on pheromone technique, an example is given and a prototype implementation is established to coordinate and control a hybrid shop floor control system. Experiments confirm that the proposed approach has excellent optimization performance and adaptability to disturbances and changes.

Pheromone-based coordination and control mechanism has the potential to solve the control problem for the shop floor control system. The main advantages of the pheromone concept are [7]: (i) a simple coordination mechanism (ii) the automatic guidance to the optimized solution, and (iii) the capability to handle dynamic situations. As a potential coordination mechanism, stigmergic coordination mechanism owns its advantage and characteristics compared with contract net protocol mentioned above.

Our application of stigmergic coordination mechanism in manufacturing system is focused on task allocation and selection, therefore it is still preliminary and further research work is needed. Future work should consider how to design the related ant colony parameters, such as award and punishment parameters of system and control algorithms so as to decrease the adaptation time. In addition, future work will also focus on exploring ant agent coordination for dynamic re-scheduling which can provide a schedule immediately and efficiently.

Acknowledgement

This paper is supported by Youth Foundation of Anhui Polytechnic University, the New Century Excellent Talents in University, China (NCET-08), and the Research Fund for Doctoral Program of Higher Education, China (No.20093218110020). The authors would like to thank the referees, the editors and the anonymous reviewers for their helpful comments and constructive suggestions.