TASK ALLOCATION BASED ON PHEROMONE

Wang Lei,Tang Dunbing,Ling Xue

(1.School of Mechanical and Automotive Engineering,Anhui Polytechnic University,Wuhu,241000,P.R.China;2.College of Mechanical and Electronical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing,210016,P.R.China;3.School of Humanities,Anhui Polytechnic University,Wuhu,241000,P.R.China)

INTRODUCTION

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.

Inspired by the collective behavior of ant colonies,ant colonies can always find shorter paths from a nest to a food source by pheromone trail laying and following.Dorigo,et al[3]first used pheromone-based coordination for solving the traveling salesman problem(TSP)which is based on ant foraging.Later pheromone-based coordination approach was successfully applied to many other combinatorial optimization problems,including manufacturing scheduling problems[4-7].Moreover,the collectiveintelligence in the colony is realized,most of the time,not by direct communication among individual insects, but instead by indirect coordination[8].It can reduce communication during coordination and make coordination simple and flexible[1]. Based on these advantages, a pheromone-based coordination approach is used to deal with task allocation problems in this paper.Although the coordination mechanism based on pheromone has the advantage of dynamic adaptation,in order to demonstrate its coordination validity and optimization ability for task allocation problems in shop floor,its performance is verified in a static environment in this paper.Meanwhile,a prototype system to simulate the performance of the used approach for task allocation is built.

1 PHEROMONE-BASED COORDINATION MECHANISM

The pheromone-based coordination mechanism is inspired by the foraging behavior of real ants.Real ants are capable of finding the shortest path from a food source to their nest without using any direction communication.Instead,they communicateinformation about the food source via depositing a chemical substance,called pheromone,on the paths.The following ants are attracted by the pheromone.Since the shorter paths have higher traffic densities,these paths can accumulate higher proportion of pheromone. Hence, the probability of ants following these shorter paths would be higher than that of those following the longer ones.

Much to our surprise,just using this simple strategy,an ant colony can find the optimal route from nest to food sourcequickly in a very complex environment(in contrast with their intelligence)[9].

Fig.1 can explain why an ant colony can achieve such good performance[10].When an ant is searching for the nearest food source and comes across with several possible paths(Path 1 and Path 2),it tends to choose the path with the largest concentration of pheromone, with a certain probability.After choosing the path,it deposits a certain quantity of pheromone,thus increasing the concentration of pheromones on this path. The ants return to the nest using always the same path,depositing other portion of pheromone in the way back.Imagine then,that two ants at thesame location choose two different paths at the same time. The pheromone concentration on the shortest path(Path 2)will increase faster than the other(Path 1),and the ant that chooses this way,will deposit more pheromones in a smaller period, because it returns earlier.If a whole colony of thousands of ants follows this behavior,soon the concentration of pheromone on the shortest path will be much higher than the concentration on other paths.Then the probability of choosing any other way will be very small and only very few ants among the colony will fail to follow the shortest path.There is another phenomenon related with the pheromone concentration.Since it is a chemical substance,it tends to evaporate in theair,so the concentration of pheromones vanishes with time.In this way,the concentration on the less used paths will be much lower than that on the most used ones,not only because the concentration increases in the other paths,but also because their own concentration decreases[10].

Fig.1 Process for real ants to find shorter path

A further research indicates that the behavior model for an ant colony to choose paths for food can be presented as[5]

where pi is the probability for ant to choose path i for food,ci and cj are the quantity of pheromone on paths i and j respectively,k is the attractive degree for no pheromone paths,and n the nonlinear coefficient.

2 PHEROMONE-BASED COORDINATION FOR TASK ALLOCATION

In ants’food foraging process,pheromone is the basic information element and resides in the associated route.The function of pheromone is to indicate the attraction of its resident route.The prominent characteristic of pheromone is simplicity[10].Therefore,the task allocation can be looked as ants’food foraging process.Generally speaking,a task can be finished by several machines.In order to make each machine have a chance to be selected,therefore at the beginning,an initial value is set for each machine that has ability to finish the given task,as shown in Eqs.(2-3).

When a work piece selects a machine,it firstly perceives the pheromone value of each feasible machine and selects a machine by machine’s selecting probability,which can be obtained from Eq.(1),as shown in Eq.(4).

where i is the machine,j the work piece,p(i)the selecting probability of machine i,and d[i][j]the machine i’s pheromone to work piece j.

After the selecting algorithm generates a random number and chooses a machine for processing work piece j according to calculated selecting probability,the selected machine can get an award, and the "effective pheromone"increases,as shown in Eq.(5).

where c is the processing cost of the selected machine,and T(c)the increased pheromone value. And the increment is inversely proportional to the processing cost,meanwhile,the pheromone of other machines can be penalized a bit,as shown in Eq.(6).

where U(c)is the penalty coefficient of other machines’pheromone value, and it is an increasing function of total processing cost.

When the machine is malfunction, its pheromone value is set to zero.The flow chart of pheromone-based coordination for task allocation is shown in Fig.2.

Fig.2 Pheromone-based task allocation processes

3 EXPERIMENT AND RESULTS

3.1 Prototype system

A prototype system is built to simulate the performance of the approach for task allocation.The system hardware structure is shown in Fig.3.The hardware system is implemented by using ARM 7 controller which serves as shop floor controller.Several single chips(PIC18F4585)serve as cell(machine)controllers. These cell controllers are linked through local area net(LAN).In addition,most of the related data are stored in a"Microsoft Access"database.In the shop floor,an ARM is looked as a main controller,and the intra-cell communication is implemented by CAN bus.Meanwhile,a wireless communication technology is adopted to control AGV. The pheromone-based coordination algorithm is written by using language C and is embedded in ARM controllers.

The physical structure of the hardware simulation platform is shown in Fig.4.It consists of three manufacturing cells and an automated storage and retrieval system(AS/RS).Each cell con-sists of one machine,one robot,and an AGV is shared by these three cells. LED screen monitor can show a real time operation situation of the whole system.

Fig.3 Hardware structure of prototype system

Fig.4 Physical simulation platform

3.2 Experimental results

Although pheromone-based coordination has the advantage of dynamic adaptation, to demonstrate its coordination validity and optimization ability,its performance is verified in a static environment in this paper.

The static environment means: The processing time of one specific machine to one operation is fixed,the order is fixed as well all machines would keep working and be free from maintenance and malfunction.

Table 1 lists the production information for performing order 001,and this order can be processed on each manufacturing cell.

Table 1 Production inf ormation for order 001

These pheromone-based parameters selected in the experiment are as follows:c0=10,T(c)=300/c,U(c)=0.5(c is the processing cost on manufacturing cell).

The experimental logic diagram is shown in Fig.5,and the specific realization process is as follows:

(1)Initialize initial pheromone value of each manufacturing cell in shop floor controller and cell controllers.Meanwhile,initialize reward and penalty pheromone values of each manufacturing cell.

(2)According to the pheromone value of each cell, the shop floor controller selects randomly a manufacturing cell to process the next work piece and sends the selected result to the corresponding cell controller through CAN bus.

Fig.5 Experimental logic diagram

(3)The selected cell is rewarded a pheromone value,and the unselected cell is decreased a penalty pheromone value.

(4)Each cell controller updates its pheromone value and sends it to the shop floor controller to save.

(5)If there are work pieces that need to be selected,implement steps(2-4),otherwise end.

Table 2 shows the coordination results for ten experiments,and it can be found that the pheromone-based coordination approach has a better stability. The pheromone change of different cells for attracting work pieces is shown in Fig.6, and experimental results of the corresponding pheromone-based coordinations at different stages are shown in Fig.7.In the first ten work pieces,there are only four work pieces selecting Cell 1,five work pieces selecting Cell 2 and one work pieces selecting Cell 3.However,in the first 50 work pieces,there are 30 work pieces selecting Cell 1,only 13 work pieces selecting Cell 2 and seven work pieces selecting Cell 3.It is obvious that in a static environment the pheromone-based approach has excellent optimization performance.Actually it can find the optimal solution quickly and stick to it.Each work piece of this order arriving in the system selects a manufacturing cell to process it.At the beginning,each cell has equal probability to be selected,but after a period of time,the good cell(Cell 1)will be released more pheromone than other bad ones, therefore the good cell is reinforced and more work pieces select it.The result is consistent with and even much better than the practical instance.

Table 2 Coordination results

Fig.6 Pheromone change of different cells for attracting work pieces

Fig.7 Experimental results of pheromone-based coordination

4 CONCLUSION

Pheromone-based coordination approach has the potential to solve task allocation problem in the shop floor. Therefore,in this paper,the approach is applied to coordination task allocation, aiming at handling static task allocation and dynamic changes or disturbances.The approach has the capacity to automatically find efficient manufacturing cells for processing orders.Based on thepheromone-like technique,a prototype system is developed to control a shop floor system, and the experimental results confirm that the approach has excellent optimization performance and stability for the static environment.The future work is to make a further research on dynamic or variable task allocation problems.

[1] Xiang W,Lee H P.Ant colony in telligence in multiagent dynamic manufacturing scheduling [J].Engineering Applications of Artificial Intelligence,2008,21(1):73-85.

[2] Hall N G,Potts C N.Rescheduling for new orders[J].Operations Research,2004,52(3):440-453.

[3] Dorigo M,Maniesso V,Colorni A.Distributed optimization by ant colonies [C]//European Conference on Artificial Life.Pairs:France,1991:134-142.

[4] Blum C,Sampels M.An ant colony optimization algorithm for shop scheduling problems[J].Journal of Mathematical Modeling and Algorithms,2004,3(3):285-308.

[5] Gao Qinglu, Luo Xin,Yang Shuzi. Stigmergic cooperation mechanism for shop floor control system[J]. International Journal of Advanced Manufacturing Technology,2005,25(7/8):743-753.

[6] Renna P. Job shop scheduling by pheromone approach in a dynamic environment[J].International Journal of Computer Integrated Manufacturing,2010,23(5):412-424.

[7] Zhou R,Nee A Y C,Lee H P.Performance of an ant colony optimization algorithm in dynamic job shop scheduling problems[J].International Journal of Production Research,2009,47(11):2903-2920.

[8] Cicirello V A,Smith S F.Insect societies and manufacturing[C]//Proceedings IJCAI-01Workshop on Artificial Intelligence and Manufacturing.Seattle:WA,2001:33-38.

[9] Camazine S,Deneubourg J,Franks N R,et al.Selforganization in biological systems[M].New Jersey:Princeton University Press,2001.

[10]Kumar S,Rao C S P.Application of ant colony,genetic algorithm and data mining-based techniques for scheduling [J]. Robotics and Computer-Integrated Manufacturing,2009,25(6):901-908.