Journal of Software Engineering and Applications, 2011, 4, 603608 doi:10.4236/jsea.2011.411071 Published Online November 2011 (http://www.SciRP.org/journal/jsea) Copyright © 2011 SciRes. JSEA A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2Machine Robotic Cell Mohammad Fathian1, Isa Nakhai Kamalabadi2, Mehdi Heydari1, Hiwa Farughi1 1Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran; 2Department of Industrial Engi neering, Tar b iat Modares University, Tehran , Ira n. Email: h_farughi@iust.ac.ir Received September 6th, 2011; revised October 10th, 2011; accepted October 22nd, 2011. ABSTRACT This paper deals with part sequencing and optimal robot moves sequence in 2machine robotic cells according to Petri net graph. We have assumed tha t the robotic cell is cap able of producing same and different parts . We have considered a new motion cycle for robot moves sequence which is the development of existing motion cycles in 2machine robotic cells. The main goal of this study is to minimize the cycle time by determining the optimal part sequencing and robot moves sequence in the ro botic cell. So, we have proposed a model based on Petri network. Keywords: Cycle Time, 2Machine Ro b oti c Cel l, Petri Networks, Part Sequencing, Robot Moves Sequence 1. Introduction In the present competitive world, time is an important and determining factor in industries. Along with techno logical progress in industries and organizations, manag ers’s decisionmaking and their organizational activities and strategies have become increasingly complex. One of these strategies is the development of automation in in dustries and manufacturing organizations, which invol ves the use mechanical and programmable devices called robots for moving parts between the different stations. By establishing machines in cellular layout and using robots for automating the process, managers try to reduce the production time in ord er to increase the effectiveness of the production line, and to increase the productivity output in robotic manufacturing cells. In the last few years, researchers have been concerned with optimizing the robot move sequence in order to reduce production time in robotic manufacturing cells and many studies have been done in this regard. The study of Sethi et al. [1] is considered as the begin ning point of the robotic cell scheduling literature. They discussed on minimizing the cycle time in the single ma chine robotic cell. Sethi et al. [2] proved that in buffer less singlegripper twomachine robotic cells producing single parttype and having identical robot travel times between adjacent machines and identical load/unload times, a 1unit cycle provides the minimum per unit cy cle time in the class of all solutions, cyclic or otherwise. For three machine case, Crama and van de Klundert [3], and Brauner and Finke [4] shown that the best 1unit cycle is optimal solution for the class of all cyclic solu tions. Hall et al. [5,6] considered the computational com plexity of the multipletype parts threemachine robotic cell problem under various robot movement policies. I. N. Kamalabadi et al. [7] provided a new solution for the cyclic multiple parts threemachine robotic cell. They also [8,9] considered the minimizing of cycle time in a blocking flow shop cell. This problem is studied for nowait robotic cells too. For example Agnetis [10] found an optimal part schedule for nowait robotic cells with three and two machines. Agnetis and pacciarelli [11] have studied part scheduling problem for nowait robo tic cells, and found the complexity o f the problem. Cra ma et al. [3,12] studied flowshop scheduling problems, models for such problems, and complexity of these problems. Dawande et al. [13] reviewed the recent developments in robotic cells and, provided a classification scheme for ro botic cells scheduling problem. Some other special cases have been studied such as: Drobouchevitch et al. [14] provided a model for cyclic production in a dualgripper robotic cell. Deineko et al. [15] studied the special case of two ma chine flex ible robo tic cell th at the firs t machine p er forms one operation, and the second machine processes K operations s tep by step. Akturk et al. [16] studied on robotic cell scheduling with operational flexibility. Gultekin et al. [17] studied robotic cell scheduling problem with tooling
A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2Machine Robotic Cell 604 constraints for a twomachine robotic cell where some operations can only be processed on the first machine and some others can only be processed on the second machine and the remaining can be processed on both machines. Gultekin et al. [18] considered a flexible manufacturing robotic cell with identical parts in which machines are able to do different operations and the op eration time is not system parameter and is variable. They proposed a lower bound for 1unit cycles and 2unit cycles. Sriskandarajah et al. [19] classified the part se quence problems associated with different robot move ment policies, in this paper a robot movement policy is considered, which its part scheduling problem is NP Hard, and Baghchi et al. [20] proposed to solve this problem, by a heuristic or metaheuristic. It is obvious that the two fundamental problems in ro botic cell scheduling are part sequencing and optimizing the robot move sequence. If the cell is meant to produce identical parts, the scheduling problem will depend on finding the optimal robot move sequence. In this paper, we have defined a new cycle for robot move sequence in a 2machine robotic manufacturing cell, which is devel opment of existing robot motion cycles. Our purpose is to obtain the optimal cycle time by determining the op timal parts entry to the cell. For the modeling this prob lem, timed Petri network has been used. In Section 2, assumptions, concepts and the robot move sequence for the proposed new cycle are introduced and the cycle time is calculated. In Section 3, concepts and relations in a Petri network are described. Then, the proposed motion cycle is described in full detail according to Petri net model. At first the mathematical model for the problem of producing identical parts in the production cycle is obtained, and then the model is generalized to the prob lem of producing different parts. Thereby, by determin ing the optimal part sequencing for the proposed cycle the minimum cycle time is obtained. In section 4 the re sults are analyzed and concluded. 2. Problem Definitio n In robotic manufacturing cell scheduling, the major pro blem is how to determine the sequence of robot moves and order the parts entry in a cell that produces different parts. In past studies about 2machine robotic cells, 122121 motion cycles have been introduced [1], and the robot move sequence and the order of parts entry in 2machine robotic cells have been studied [2]. In 3 Machine robotic cells, the sequence of robot moves and parts entry to the cell has been investigated for both the same parts and different parts manufacturing cells [3,21]. In this paper, we have defined a new cycle for twoma chine robotic cells and have considered the problem of different parts entry sequencing to obtain the optimum cycle time by a timed Petri net model. In most studies on scheduling 2machine robotic cells the problem of flow shop has been considered. Thereby, each part is process ed on the first machine and then conveyed by the robot to the second machine to be processed on. Indeed, each part must be processed on both machines. It is also assumed that the two machines are identical, i.e. the processing time of a same operation is the same on both machines. In addition, the rob ot’s movement time between an y two consecutive locations is the same and it is additive be tween different locations. Also, the robot’s loading and unloading time in all condition s is the same and the robot has a linear movement in the cycle. ,,SSS S Definition 1 : Activity (ij ) signifies the robot’s conveying a part from location i to location j. Definition 2 : A nunit cycle means that the robot has entered n parts into the cycle and for doing all the requ ired processes on n parts each activity has been repeated n times. At the end of each cycle, n part should be taken out of the cell by robot. Also, the beginning and the end mode of the nunit cycle should be same. Definition 3 : The nunit cycle time is defined as the time needed to produce n parts in a cyclic process that a robot starts from the initial state and moves in a sp ecific sequen ce, so that the necessary operations for producing n parts is performed and then the ro bot goes on the initial position . Also, if we assume that the machines are flexible, in other words if each machine is capable of performing all operations on each part so that every part is processed completely by a single machine, then a new motion cycle can be defined with a sequence of moves as the follow ing: At the beginning of the cycle, a part is being processed by the second machine and the robot is located opposite the input area. According to definition 1, th e sequence of the robot movements is012302 13 AAA, i.e. the robot picks a part on the input buffer (the needed time is ) and takes the part to the first machine (). Then it loads the part on the first machine ( ) and moves towards the second machine ( ) and waits opposite this machine until it completes processing the part (w2), after the sec ond machine has completed the process, the robot unloads the part from the second machine ( ) and takes it to the output buffer ( ), then it loads it on the output buffer ( ). Then the robot comes back to the input buffer (3 ), pick a part from the input buffer (s ), moves it to the second machine (2 ), and loadit on it (s ), then it tus back to the first machine ( ) and waits opposite the machine until it completes processing the part (w1). rn Copyright © 2011 SciRes. JSEA
A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2Machine Robotic Cell605 When processing is finished, the robot unloads the part from the first machine ( ), taks it to the output (2e ) and then loads it on output area ( ). Ten it comes back to the input buffer (3). Tereby, the cycle is finished and the robot returns to the initial position. During this cycle, two parts are produced, so the cycle is called 2unit cycle. In this cycle, it is assumed that the robot has no waiting time in the input and the output buffer. It should be noted that since each machine has the ability to perform all operations, in the process of producing n parts and in each sequence of cyclic moves, after one stage we have a repetitive sequences of robot movements which continues until n parts are produced. In this pro posed cycle, the starting point of the mentioned repetitiv e process is the beginning of the cycle. h h In this case, the cycle time for producing two parts is calculated as follows, and its parameters are: : Loading or unloading time : The time in which the robot moves between two successive locations P: Processing time of each part on the machines i w: Waiting time in front of machine i Ct: Cycle time: 2 2unit3 2 814 t 1 3w1 2 w w2 Cw 4 4 2 w ,wP ,wP 1 2 (1) Max 08 (2) 2Max 0 (3) Therefore, the time needed to produce a part in this cycle is: 12 w81 1 unitt w C 4 2 (4) 0, 4 2 1 1unit42 4 2 1 Ma0,8 2 t CMaxP Pw 7 x (5) The layout of the proposed cycle and the initial posi tion are shown in Figure 1. Inp ut Machine 1 hine 2 O utput Bu Linear Mac ffer obot Part Figure 1. Layout of the new cycle. 3. Petri Network Model Many systems can be modeled on Petri nets and it is pos sible to show their features using these networks [22]. Petri network is a suitable device for mathematical and graphical modeling. The graphical behavior of variables and the ability to convert them into flowchart and dia gram is one of the important features of Petri nets [8]. Petri networks were introduced for the first time by Adam Petri in 1962. Lee and Yung (1955) presented a new method for planning flexible process sequences us ing Petri networks [22]. Petri nets are directed split graphs which are divided into two groups of place and transition. The directed arcs link some places to some transitions or link some transitions to some places. Nota tion in a Petri network is a vector whose elements show the number of arcs. Each Petri network is shown as ,,, ,PNPTA WM0 P: a finite set of places [22] in which: 12 ,...., n PPPP, ....,ttt T: a finite set of transitions 12 m t A: a finite set of arcs PTTP W: weight function associated with each location 1,2,.....P:WA M0: Initial network markup 0,1,2,.....P0: P Mark ch an ges in a Petri network involving firing (tran sposition) is as the following: 1) The firing is performed when the location Pi has at least W (Pi, t) token, whereby W (Pi, t) is the arc weight of Pi to t. 2) An active transposition may lead to firing depend ing on whether its movement is performed or not. 3) If the transition t is fired, W (Pi, t) of tokens is re duced from each Pi to t input place and W (P0, t) number of tokens is added to each P0 output location of transition t. are added. W (t, P0) is the arc weight of t to P0 [22]. Theorem 1: In a marked graph, for each location that has i to kens the following relationship Ait , whereby SSMC S, are the starting times of transitions of B and A, and t is the cycle time in timed Petri network. Figure 2 shows this marked graph. A S C 3.1. Timed Petri Network Model for Producing Identical Parts in the New Cycle At the beginning of th e proposed cycle, it is assumed that a part on the second machine is being processed and the Figure 2. Marked graph related to theorem 1. B A Copyright © 2011 SciRes. JSEA
A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2Machine Robotic Cell 606 robot is located opposite the input buffer. For simplicity of calculation and drawing Petri networks, in modeling the problem and drawing its graph we assume that the starting point of the cycle moves to the moment when the robot loads the first machine and leaves for the second machine; at this moment a part is being processed by both machines. At the end of the cycle the robot returns to this situation. Accordingly, the graph for the same parts production cycle is shown in “Figure 3”. The parameters needed for modeling this problem by Petri network are the following: R1: moving toward the second machine and waiting opposite the second machine () 2 R2: unloading the part from the second machine ( w ) R3: moving towards the output buffer, loading the part on the output buffer, moving towards the input buffer, unloading the part from the input buffer and moving to wards second machine (62 ) R4: loading the part on the second machine ( ) R5: moving toward the first machine and waiting op posite the first machine () 1 R6: the robot’s unloading the part on the first machine ( W ) R7: moving towards the output buffer and loading the part on the output buffer, moving towards the input buffer, unload the part from the input buffer, and moving toward the first machine (62 ) R8: loading the part on the first machine ( ) ' : starting moment of the first machine’s processing M1 : The moment that the first machine has finished its 1 P 1 R 2 P 8 R 8 P 7 R 26 7 P 6 R 5 P 6 P 5 R 4 R 3 R 4 P 3 P 26 P 2 w 1 w P 2 R Figure 3. Petri network graph for same parts production cycle. task and is waiting for the robot to unload the part from it : starting moment of the second machine’s proc essing (M2) : The moment that the second machine has finished its task and is waiting for the robot to unload the part from it P: operating time of the first or the second machine Mathematical model for production planning problem of producing same parts in the proposed cycle are the following: Min Ct Subject to: (6) 11 8 :t PS SC (7) 22 12 :PS Sw (8) 33 2 :PS S (9) 44 3 :6PS S2 (10) 55 4 :PSS (11) 66 51 :PS Sw (12) 776 :PS S (13) 88 7 :6PS S2 (14) 68 :t SSCP (15) 24 :t SSCP (16) 12 ,, 0 i Sww (17) In this model, the objective function is to minimize the cycle time of producing same parts. The constraints are written according to the properties of timed Petri network and what were written in “Theorem 1”. 3.2. Mathematical Model for Production Planning Problem of Producing Different Parts in the Proposed Cycle In the proposed new cycle, we assume that n different parts must be produced, and that the processing time for all parts is specified. Therefore, we can model the Petri network in a way that the optimal sequence of parts’ en tering the cell is determined. According to this model, n parts are produced by this production cycle in the mini mum possible time. Petri network graph related to the production of these n parts is obtained by repeating the same parts production cycle 2n times as described in the previous section. Because in the proposed same parts production cycle 2 parts are produced, for producing n parts in the cycle, the mentioned sequence must be re peated 2n times. For modeling the new proposed dif ferent parts production cycle, in addition to the parame ters used for producing identical parts, the following pa rameters are needed: Copyright © 2011 SciRes. JSEA
A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2Machine Robotic Cell607 X1ij: if the part i, is the jth part given to the first machine X2ij: if the part i, is the jth part given to the second ma chine t: part counter t i Mathematical model for production planning problem with different parts are the following: min Ct Subject to: (18) 1,1 1,18, :nt PS SC (19) 1, 1,8, : 2,...., jj j PS Sjn (20) 2, 2,1,2 : 1,...., jj j PS Swjn (21) 3, 3,2, : 1,.... , jj j PS Sjn (22) 4, 4,3, :62 1,...., jj j PS Sjn (23) 5, 5,4, : 1,...., jj j PS Sjn (24) 6, 6,5,1 : 1,...., jj j PS Swjn (25) 7, 7,6, : 1,...., jj j PS Sjn (26) 8, 8,7, :62 1,...., jj j PS Sjn (27) 16,18,11 1 :n tini i SSC xa (28) 6, 8,1 1 : 2,...., n jj jiji i SSxajn (29) 12,4,2 1 :n nnt in i SSC Xbi (30) 2, 4,2 1 : 1,....,1 n jj jij i SSXbijn (31) 12 11 1 1,......, nn ij ij ii Xj nn n (32) 12 11 1 1,......, ij ij jj Xi n (33) 220 1 1,......, in i Xi n (34) 11111 1,......, in i Xi n , (35) .1,,1 , 12211, ijtj ijtj ti ti XX Xit j (36) 12 ,,0 ij Sww (37) 12 ,0 ij jj XX,1 (38) Constraints added to this model are the following: Constraint (32) states that at any stage only one part must enter and it must be assigned only to one machine. Constraint (33) states that part i must enter only in one stage of the cycle. Constraint (34) states that the part being processed on the second machine at the beginning of cycle is the nth part in the previous cycle and represents the sequence in new cycle. Constraint (35) states that the part being processed by the first machine at the beginning of cycle is n + 1st part in the previous production cycle. Constraints (36) state that the sequence of parts enter ing the new cycle must be observed, i.e. if in a stage one part is given to one of the machines, in next stage the next part is given to the other machine. Constraints Pi,j are written according to “Theorem 1”. Also, the objective function of the problem is to mini mize the cycle time to produce n various parts in the new proposed cycle. 4. Conclusions In this paper, at first the existing feasible robot moves cycles in a 2machine robotic cells reviewed, then a new cycle with assumption that the machines are identical and flexible with the ability to perform all the necessary op erations for producing the same and different parts, was introduced. The main problem in this research was to minimize the cycle time in producing same and different parts by optimizing part sequencing in the robotic cell. Accordingly, we provided a mathematical programming model based on Petri network. Among the issues that can be considered in future researches are: 1) to provide methods for solving the problem model and comparing the results; 2) to test the performance of the existing ro bot move sequences in the form of new proposed cycle; 3) to extend these problem to 3machine rob otic cells. REFERENCES [1] S. P. Sethi and D. Groupe, “D’Études et de Recherche en Analyse des, Sequencing of Robot Moves and Multiple Parts in a Robotic Cell,” Groupe D’Études et de Recher che en Analyse des Decision s, Montréal, 1989. [2] S. P. Sethi, C. Sriskandarajah, G. Sorger, J. Blazewicz and W. Kubiak, “Sequencing of Parts and Robot Moves in a Robotic Cell,” International Journal of Flexible Manufacturing Systems, Vol. 4, 1992, pp. 331358. doi:10.1007/BF01324886 [3] Y. Crama and V. D. Klundert, “Cyclic Scheduling in 3Machine Robotic Flow Shops,” Journal of Scheduling, Vol. 2, 1999, pp. 3554. doi:10.1002/(SICI)10991425(199901/02)2:1<35::AIDJ OS15>3.0.CO;2J [4] N. Brauner and G. Finke, “On a Conjecture About Ro botic Cells: New Simplified Proof for the Three machine Case,” INFOR, Vol. 37, No. 1, 1999, pp. 2036 [5] N. G. Hall, H. Kamoun and C. Sriskandarajah, “Schedul ing in Robotic Cells: Complexity and Steady State Analy sis,” European Journal of Operational Research, Vol. Copyright © 2011 SciRes. JSEA
A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2Machine Robotic Cell Copyright © 2011 SciRes. JSEA 608 109, 1998, pp. 4365. doi:10.1016/S03772217(96)003335 [6] N. G. Hall, H. Kamoun and C. Sriskandarajah, “Schedul ing in Robotic Cells: Classification, Two and Three Ma chine Cells,” Operations Research, Vol. 45, 1997, pp. 421439. doi:10.1287/opre.45.3.421 [7] I. N. Kamalabadi, S. Gholami and A. H. Mirzaei, “A New Solution for the Cyclic MultiplePart Type ThreeMa chine Robotic Cell Problem Based on the Particle Swarm MetaHeuristic,” Journal of Industrial and Systems En gineering, Vol. 1, No. 4, 2008, pp. 304317. [8] I. N. Kamalabadi, “A New Formulation for Scheduling Problems Through Petrinets,” In The Iranian Mathe matical Conference, Iran, 1996. [9] I. N. Kamalabadi, N. G. Hall and H. Sriskandarajah, “Minimizing Cycle Time in a blocking Flowshop,” Op erations Research, Vol. 48, 2000, pp. 177180. doi:10.1287/opre.48.1.177.12451 [10] A. Agnetis, “Scheduling NoWait Robotic Cells with Two and Three Machines,” European Journal of Opera tional Research, Vol. 123, 2000, pp. 303314. doi:10.1016/S03772217(99)002581 [11] A. Agnetis a nd D. Paccia relli, “Part Sequencing in Three Machine NoWait Robotic Cells,” Operations Research Letters, Vol. 27, 2000, pp. 185192. doi:10.1016/S01676377(00)000468 [12] Y. Crama, V. Kats and V. D. Klundert, “Cyclic Schedul ing in Robotic Flow Shops,” Annals of Operation Re search: Mathematics of Industrial Systems, Vol. 96, 2000, pp. 97124. [13] M. Dawande, H. N. Geismar, S. P. Sethi and C. Sriskan darajah, “Sequencing and Scheduling in Robotic Cells: Recent Developments,” Journal of Scheduling, Vol. 8, 2005, pp. 387426. doi:10.1007/s1095100528619 [14] I. G. Drobouchevitch, S. P. Sethi and C. Sriskandarajah, “Scheduling Dual Gripper Robotic Cell One Unit Cy cles,” European Journal of Operational Research, Vol. 171, 2006, pp. 598631. doi:10.1016/j.ejor.2004.09.019 [15] V. Deineko and G. Steiner, “RoboticCell Scheduling: Special Polynomially Solvable Cases of the Traveling Salesman Problem on Permuted Monge Matrices,” Jour nal of Combinatorial Optimization, Vol. 9, No. 4, 2005, pp. 381399. doi:10.1007/s1087800517788 [16] M. S. Akturk, H. Gultekin and O. E. Karasan, “Robotic Cell Scheduling with Operational Flexibility,” Discrete Applied Mathematics, Vol. 145, 2000, pp. 334348. doi:10.1016/j.dam.2004.02.012 [17] H. Gultekin, M. S. Akturk and O. E. Karasan, “Cyclic Scheduling of a 2Machine Robotic Cell with Tooling Constraints,” European Journal of Operational Research, Vol. 174, 2006, pp. 777796. doi:10.1016/j.ejor.2005.03.021 [18] H. Gultekin, M. S. Akturk and O. E. Karasan, “Schedul ing in a ThreeMachine Robotic Flexible Manufacturing Cell,” Computers & Operations Research, Vol. 34, 2007, pp. 24632477. doi:10.1016/j.cor.2005.09.015 [19] C. Sriskandarajah, N. G. Hall, H. Kamoun and H. Wan, “Scheduling Large Robotic Cells without Buffers,” An nals of Operations Research, Vol. 76, 1998, pp. 287321. doi:10.1023/A:1018952722784 [20] T. P. Bagchi, J. N. D. Gupta and C. Sriskandarajah, “A Review of TSP Based Approaches for Flow shop Sched uling,” European Journal of Operational Research, Vol. 169, 2006, pp. 816854. doi:10.1016/j.ejor.2004.06.040 [21] Y. Crama, “Combinatorial Optimization Models for Pro duction Scheduling in Automated Manufacturing Sys tems,” European Journal of Operational Research, Vol. 99, 1997, pp. 136153. doi:10.1016/S03772217(96)003888 [22] J. Maggot, “Performance Evaluation of Concurrent Sys tems Using Petri Nets,” Information Processing Letters, Vol. 8, No. 1, 1984, pp. 713. doi:10.1016/00200190(84)90067X
