Journal of Software Engineering and Applications, 2011, 4, 603-608
doi:10.4236/jsea.2011.411071 Published Online November 2011 (http://www.SciRP.org/journal/jsea)
A Petri Net Model for Part Sequencing and Robot
Moves Sequence in a 2-Machine 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.
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 2-machine 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 2-machine 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, 2-Machine 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 decision-making 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 single-gripper two-machine robotic cells producing
single part-type and having identical robot travel times
between adjacent machines and identical load/unload
times, a 1-unit 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 1-unit
cycle is optimal solution for the class of all cyclic solu-
tions. Hall et al. [5,6] considered the computational com-
plexity of the multiple-type parts three-machine robotic
cell problem under various robot movement policies. I. N.
Kamalabadi et al. [7] provided a new solution for the
cyclic multiple parts three-machine robotic cell. They
also [8,9] considered the minimizing of cycle time in a
blocking flow shop cell. This problem is studied for
no-wait robotic cells too. For example Agnetis [10]
found an optimal part schedule for no-wait robotic cells
with three and two machines. Agnetis and pacciarelli [11]
have studied part scheduling problem for no-wait robo tic
cells, and found the complexity o f the problem. Cra ma et
al. [3,12] studied flow-shop 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 dual-gripper
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 2-Machine Robotic Cell
604
constraints for a two-machine 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 1-unit cycles and 2-unit
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 meta-heuristic.
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 2-machine 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 2-machine robotic cells,
122121 motion cycles have been introduced [1],
and the robot move sequence and the order of parts entry
in 2-machine 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 two-ma-
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 2-machine 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
A
) signifies the robot’s conveying a part
from location i to location j.
Definition 2 :
A n-unit 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
n-unit cycle should be same.
Definition 3 :
The n-unit 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
A
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

A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2-Machine 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
2-unit 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
R
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 WM0
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
A
PTTP
W: weight function associated with each location


1,2,.....P:WA
M0: Initial network markup

0,1,2,.....P0:
M
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
M
to-
kens the following relationship
B
Ait
, whereby SSMC
B
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

A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2-Machine 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:

A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2-Machine 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
X
Xj



nn
n (32)
12
11
1 1,......,
ij ij
jj
X
Xi


 n (33)
220
1 1,......,
in i
X
Xi n (34)
11111 1,......, in i
X
Xi
 n
,
(35)
.1,,1 ,
12211,
ijtj ijtj
ti ti
X
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 2-machine 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 3-machine 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. 331-358.
doi:10.1007/BF01324886
[3] Y. Crama and V. D. Klundert, “Cyclic Scheduling in
3-Machine Robotic Flow Shops,” Journal of Scheduling,
Vol. 2, 1999, pp. 35-54.
doi:10.1002/(SICI)1099-1425(199901/02)2:1<35::AID-J
OS15>3.0.CO;2-J
[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. 20-36
[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.

A Petri Net Model for Part Sequencing and Robot Moves Sequence in a 2-Machine Robotic Cell
608
109, 1998, pp. 43-65.
doi:10.1016/S0377-2217(96)00333-5
[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.
421-439. doi:10.1287/opre.45.3.421
[7] I. N. Kamalabadi, S. Gholami and A. H. Mirzaei, “A New
Solution for the Cyclic Multiple-Part Type Three-Ma-
chine Robotic Cell Problem Based on the Particle Swarm
Meta-Heuristic,” Journal of Industrial and Systems En-
gineering, Vol. 1, No. 4, 2008, pp. 304-317.
[8] I. N. Kamalabadi, “A New Formulation for Scheduling
Problems Through Petri-nets,” 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. 177-180.
doi:10.1287/opre.48.1.177.12451
[10] A. Agnetis, “Scheduling No-Wait Robotic Cells with
Two and Three Machines,” European Journal of Opera-
tional Research, Vol. 123, 2000, pp. 303-314.
doi:10.1016/S0377-2217(99)00258-1
[11] A. Agnetis a nd D. Paccia relli, “Part Sequencing in Three-
Machine No-Wait Robotic Cells,” Operations Research
Letters, Vol. 27, 2000, pp. 185-192.
doi:10.1016/S0167-6377(00)00046-8
[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. 97-124.
[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. 387-426. doi:10.1007/s10951-005-2861-9
[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. 598-631. doi:10.1016/j.ejor.2004.09.019
[15] V. Deineko and G. Steiner, “Robotic-Cell 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. 381-399. doi:10.1007/s10878-005-1778-8
[16] M. S. Akturk, H. Gultekin and O. E. Karasan, “Robotic
Cell Scheduling with Operational Flexibility,” Discrete
Applied Mathematics, Vol. 145, 2000, pp. 334-348.
doi:10.1016/j.dam.2004.02.012
[17] H. Gultekin, M. S. Akturk and O. E. Karasan, “Cyclic
Scheduling of a 2-Machine Robotic Cell with Tooling
Constraints,” European Journal of Operational Research,
Vol. 174, 2006, pp. 777-796.
doi:10.1016/j.ejor.2005.03.021
[18] H. Gultekin, M. S. Akturk and O. E. Karasan, “Schedul-
ing in a Three-Machine Robotic Flexible Manufacturing
Cell,” Computers & Operations Research, Vol. 34, 2007,
pp. 2463-2477. 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. 287-321.
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. 816-854. 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. 136-153.
doi:10.1016/S0377-2217(96)00388-8
[22] J. Maggot, “Performance Evaluation of Concurrent Sys-
tems Using Petri Nets,” Information Processing Letters,
Vol. 8, No. 1, 1984, pp. 7-13.
doi:10.1016/0020-0190(84)90067-X