A New Solution for the Cyclic Multiple-Part Type Three-Machine Robotic Cell Problem based on the Particle Swarm Meta-heuristic

Document Type : Research Paper


1 Department of Industrial Engineering, University of Kurdistan, Sanandaj, Iran

2 Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran


In this paper, we develop a new mathematical model for a cyclic multiple-part type threemachine robotic cell problem. In this robotic cell a robot is used for material handling. The objective is finding a part sequence to minimize the cycle time (i.e.; maximize the throughput) with assumption of known robot movement. The developed model is based on Petri nets and provides a new method to calculate cycle times by considering waiting times. It is proved that scheduling problem of a robotic cell is unary NP-complete. Achieving an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. In this paper we implement an algorithm based on the particle swarm optimisation (PSO) method for solving the problem. To validate the developed model and solution algorithm, various test problems are examined some of which are of small-size and some other of large-size. The computational results show that the proposed algorithm achieves optimum solutions for small sized problems, while for large-sized problems this algorithm can find suitable solutions in acceptable time.


Main Subjects

[1] Asfahl C.R. (1992), Robots and manufacturing automation; 2nd Edition, Wiley, New York.
[2] Agnetis A. (2000), Scheduling no-wait robotic cells with two and three machines; European Journal of
Operational Research 123; 303-314.
[3] Agnetis A., Pacciarelli D. (2000), Part sequencing in three-machine no-wait robotic cells; Operations
Research Letters 27; 185-192.
[4] Brauner N., Finke G. (1999), On a conjecture about robotic cells: New simplified proof for the threemachine
case; INFOR 37(1); 20-36.
[5] Bagchi T.P., Gupta J.N.D., Sriskandarajah C. (2006), A Review of TSP based approaches for flow
shop scheduling; European Journal of Operational Research 169; 816- 854.
[6] Crama Y., Klundert J.J. van de. (1999), Cyclic scheduling in 3-machine robotic flow shops; Journal of
Scheduling 2; 35-54.
[7] Crama Y., Kats V., Klundert, J.J. van de, Levner E. (2000), Cyclic scheduling in robotic flow shops;
Annals of Operations Research: Mathematics of Industrial Systems 96; 97-124.
[8] Drobouchevitch I.G., Sethi S.P., Sriskandarajah C. (2006), Scheduling dual gripper robotic cell oneunit
cycles; European Journal of Operational Research 171; 598-631.
[9] Dawande M., Geismar H.N., Sethi S.P., Sriskandarajah C. (2005), Sequencing and scheduling in
robotic cells:Recent developments; Journal of Scheduling 8; 387-426.
[10] Gultekin H., Akturk M.S., Karasan O.E. (2006), Cyclic scheduling of a 2-machine robotic cell with
tooling constraints; European Journal of Operational Research 174; 777–796.
[11] Gultekin H., Akturk M.S., Karasan O.E. (2007), Scheduling in a three-machine robotic flexible
manufacturing cell; Computers & Operations Research 34; 2463–2477.
[12] Hall N. G., Kamoun H., Sriskandarajah C. (1997), Scheduling in robotic cells: Classification, two and
three machine cells; Operations Research 45; 421-439.
[13] Hall N. G., Kamoun H., Sriskandarajah C. (1998), Scheduling in robotic cells: Complexity and steady
state anhlysis; European Journal of Operational Research 109; 43-65.
[14] Hu X., Shi Y., Eberhart R. (2004), Recent advances in particle swarm, in Proc. of CEC2004, Congress
on Evolutionary Computation, 1; 90–97.
[15] Kennedy J., Eberhart R. (1995), Particle swarm optimization, in Proc. of the IEEE international
conference on neural networks (Perth, Australia), 1942–1948.
[16] Maggot J. (1984), Performance Evaluation of Concurrent Systems Using Petri Nets; inform.
processing lett., 18(1); 7-13.
[17] Sriskandarajah C., Hall N.G., Kamoun H., Wan H. (1998), Scheduling large robotic cells without
buffers; Annals of Operations Research 76; 287–321.
[18] Sethi S.P., Sriskandarajah C., Sorger G., Blazewicz J., Kubiak W. (1992), Sequencing of parts and
robot moves in a robotic cell; International Journal of Flexible Manufacturing Systems 4; 331-358.
[19] Shi Y., Eberhart R. (1998), "A modified particle swarm optimizer", in Proc. of the IEEE international
conference on evolutionary computation, 69–73,.
[20] Tasgetiren MF., Sevkli M., Liang YC., Gencyilmaz G. (2004), "Particle swarm optimization algorithm
for single machine total weighted tardiness problem". In: Proc. of the IEEE congress on evolutionary
computation, Oregon: Portland, 1412-1419.