POLITECNICO DI MILANO
Dipartimento di Meccanica
Performance Evaluation Of
Flow Lines With Multiple
Products
Colledani M., Matta A. and Tolio T.
Outline

System: description and assumptions

Analytical model: building block

Analytical model: decomposition

Numerical results

Conclusions and future developments
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
System description
B1,1
M1






M ...
BK 1,1
Bi ,1
Bi 1,1
M ...
Mi
B1,...
Bi 1,...
Bi ,...
BK 1,...
B1, z
Bi 1, z
Bi , z
BK 1, z
K machines, i=1,…,K
z products, q=1,…,z
Homogeneous buffers
Discrete material/discrete time
Deterministic and equal processing times
Saturated system
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
MK
System description
B1,1
M1
M ...
a 1,1
a 1, q
a1, z






a ..., 1
a ..., q
B1, z
a ..., z
M ...
Mi
Bi 1,...
B1,...
Bi 1, z
BK 1,1
Bi ,1
Bi 1,1
BK 1,...
Bi ,...
a i ,1
a i, q
a i, z
a ..., 1
a K ,1
a ..., q
Bi , z
a..., z
MK
a K ,q
BK 1, z
a K ,z
Machines can fail with multiple failures, j=1,…,Fi
Machines can be failed in only one mode at the same time period
MTTF and MTTR are geometrically distributed
The production rule at machine is local and stochastic (production parameters ai,q)
Buffers have finite capacity, Ni,q
Blocking Before Service
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
System description
Bi ,1
Bi 1,1
Mi
Bi 1,...
Bi ,...
a i ,1
a i, q
a i, z
Bi 1, z
Bi , z
Production parameters of machine Mi at time t are adjusted depending on the
state of the immediately upstream and downstream buffers.
a (t ) 
*
i ,q
a i ,q
1
 a
i,r
r  q: ni 1, r ( t )  0 or ni , r ( t )  N i , r


q  1,  , z
i  1,  , K
(Nemec, 1999) and (Syrowicz, 1999) deal with lines with two products and priority rules.
(Colledani et al., 2003 and 2005) deals with lines with two products and same assumptions.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Two-machine line with z products
B1
a u ,1
Production parameters may change
because of the emptying and/or
filling of buffers.
Mu
p1u
u
p
pu u
F
a u ,q
r1u
ru
r uu
Md
a d ,q
Bq
a u, Z
a d ,Z
F
Production parameters are adjusted as follows:
a d ,1
p1d
d
p
pd d
F
Bz
 u*
a qu
q  1,, z
a q (t ) 
u
1

a
 r

r  q: n r ( t )  N r 

a qd
 a d * (t ) 
q  1,, z
u
 q
1
a
 r

r  q: n r ( t )  0 
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
r1d
rd
r dd
F
ZP2M: two-machine line with z products
a u ,1
Mu
The state of the system is
represented by: (n1,…, nz,xu,xd).
a u ,q
B1
Md
Bq
a u, Z


a d ,q
a d ,Z
Bz
The total number of possible states is:

a d ,1
TNS  F  1 F  1  N q  1
u
d
z
q 1
The corresponding Markov Chain is too complex to be solved
numerically with traditional techniques.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
The behaviour of z-1 products can be modelled in an
approximate way by considering an equivalent aggregate
product.
M
u
B1
Md
B1
Mu
Md
Bq
Aggregate
product
Bz
a
a
Ba
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
a u ,1
Mu
a u ,q
B1
a (1)
M u (1)
a d ,1
Md
Bq
a u, Z
a d ,q
a d ,Z
Bz
B1 (1)
…
a1d (1)
u
1
Ba (1)
a au (1)
a ad (1)
a (q)
a qu (q)
M u (q)
…
d
q
M d (q)
a au (q )
…
M d (1)
a zu (z )
a ad (q )
a zd (z )
…
Bz (z )
M d (Z )
a ad ( z )
a au (z )
M u (Z )
Ba (z )
The system with z products is represented by a set of equivalent z systems,
each one crossed by 2 products: product q and the corresponding aggregate
product.
(Baynat and Dallery, 1995) first proposes this technique for analyzing multiclass queuing systems.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
The production probabilities in the original system are
adjusted as follows:
 u*
a qu
q  1,, z
a q (t ) 
u
1

a
 r

r  q: n r ( t )  N r 

d
a
q
d
*
 a (t ) 
q  1,, z
u
 q
1
a
 r

r  q: n r ( t )  0 
However, the aggregation of all products except q does not allow
to recognize the buffer levels of single aggregated products in
the analysis of the two-machine two-product system, thus we are
forced to find new values for the production parameters.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
B1 (q)
a qu (q)
M u (q)
a au (q )
a qd (q)
a ad (q )
M d (q)
Ba (q)
For each system it is necessary to calculate the parameters:
 Buffer capacities: Nq(q) and Na(q)
 Upstream production parameters: auq(q) and aua(q)
 Downstream production parameters: adq(q) and ada(q)
There are totally 6z unknowns.
(Colledani et al., 2003 and 2005) is used to calculate the performance.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
The sum of production parameters of each machine must be equal to one:
u
u



a
q

a
 q
a q   1
q  1, , z 
d
d


a
q

a

a q   1
 q
The buffer capacity of the product q corresponds to that in the original system:
N q (q)  N q
q  1,..., z
The buffer capacity of the aggregate product is the sum of the buffer
capacities in the original system of the single aggregated products:
N a (q) 
 Nq
q  1,..., z
r  q
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
We define uq as the set containing all the combinations, in the two-machine line
original system, of buffers full and not full obtained without considering buffer
Bq:
uq    (1,...,q 1,q 1,z ) :  one or more s : s  q,s  Ns  q  1,, z
The new value of the upstream production probability of product q is
calculated as a weighted combination of the adjusted auq values overall
the possible combinations belonging to the set uq :
a qu q  
 P , q   1 
  uq
a qu
a
s :n s  N s
 P , q 
u
s
q  1,, z
  uq
probability associated to the occurrence
of combination  uq
P , q    Pr r  q  1,, z
r  q
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
We define dq as the set containing all the combinations, in the original system,
of buffers empty and not empty obtained without considering buffer Bq:
dq    (1,..., q 1, q 1, z ) :  one or more s : s  q, s  0
q  1,, z
The new value of the upstream production probability of product q is
calculated as a weighted combination of the adjusted adq values overall
the possible combinations belonging to the set dq :
a qd q  
 P , q   1 
  dq
a qd
a


s :
 P , q 
  dq
probability associated to the occurrence
of combination  dq
s
0
d
s
q  1,, z
P , q    Pr  r  q  1,, z
r q
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
12
0,5
E tot
0,45
10
0,4
0,35
8
n average
0,3
E1
0,25
n1
0,35
Ps 1
0,3
6
0,2
0,25
Pb1
E2
0,15
0,4
0,2
4
0,15
0,1
E3
0,05
0,1
2
n2,n3
25
23
21
N1
19
17
15
13
11
9
7
5
0
0
0,05
0
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
N1
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Pb, Ps
0,45
E
0,5
Long lines with Z products
…
M D (1)
M U (1)
M D (2)
M U (2)
l (1)
M U (i )
M D (i )
l (i )
l (i )M U (i  1)
M D (i  1)
…
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Long lines with Z products
M u (i )
Local failures
p1u
u
p
pu u
F
Remote failures
(starvation)
u
prem
M d (i)
r1u
ru
r uu
p1d
d
p
pd d
l (i )
F
F
d
prem
u
rrem
r1d
rd
r dd
Local failures
F
Remote failures
(blocking)
d
rrem
(Tolio and Matta, 1998)
The new production parameters are calculated as follows:

a qu i  
P  , i  1 
uq
a i ,q
1   a i , s ( )
s ( ): s  0
 P , i  1
uq
a i  
d
q
 P , i  1  1 
 dq
a i 1,q
a
i 1, s ( )
s ( ): s  0
 P , i  1
q  1,, z; i  1,, K  1
 dq
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Numerical results: 3P3M
err ( E q ) 
E qanalytical  E qsimulation
tot
E simulation
 100 ; err (nq ) 
nqanalytical  nqsimulation
Nq
 100 ; q  1,...,z
CASE
1 (buffer 4-4-4/4-4-4)
2 (buffer 4-4-4/4-4-4)
3 (buffer 6-6-6/6-6-6)
4 (buffer 4-4-4/4-4-4)
MAC
H
M1
M2
M3
M1
M2
M3
M1
M2
M3
M1
M2
M3
p
0.049
0.092
0.009
0.104
0.09
0.064
0.104
0.09
0.064
0.12
0.039
0.105
r
0.62
0.16
0.102
0.62
0.12
0.102
0.7
0.28
0.32
0.42
055
0.37
a1
0.6
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.5
0.5
0.5
a2
0.3
0.3
0.3
0.2
0.2
0.2
0.35
0.35
0.35
0.4
0.4
0.4
a3
0.1
0.1
0.1
0.2
0.2
0.2
0.25
0.25
0.25
0.1
0.1
0.1
PART
P1
P2
P3
P1
P2
P3
P1
P2
P3
P1
P2
P3
E sim
0.366
0.191
0.068
0.271
0.110
0.110
0.296
0.261
0.190
0.369
0.301
0.084
E anal
0.362
0.198
0.064
0.265
0.114
0.114
0.296
0.261
0.190
0.368
0.304
0.094
Err
-0.59
1.31
-0.70
-1.31
0.69
0.69
-0.03
-0.02
-0.01
-0.16
0.4
1.37
n1 sim
3.38
3.58
3.75
3.43
3.62
3.62
4.98
5.02
5.11
1.69
1.67
1.6
n1 anal
3.06
3.24
3.46
3.11
3.18
3.18
4.26
4.33
4.45
1.60
1.58
1.9
Err
-8.03
-8.51
-7.2
-8.0
-10.7
-10.7
-11.9
-11.4
-11
-2.27
-2.05
7.55
n2 sim
0.67
0.5
0.37
1.75
1.71
1.71
1.79
1.76
1.68
2.25
2.26
2.29
n2
anal
0.87
0.71
0.56
1.8
1.86
1.86
2.11
2.26
2.19
2.15
2.21
1.94
Err
5.21
5.22
4.88
1.12
3.76
3.72
5.34
6.69
8.5
-2.45
-1.28
-8.75
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Numerical results: 4P3M
err ( E q ) 
CASE
MACH
P
R
a1
a2
a3
a
PART
E sim
E anal
Err
E qanalytical  E qsimulation
tot
E simulation
 100 ; err (nq ) 
nqanalytical  nqsimulation
Nq
 100 ; q  1,...,z
5 (buffer 4-4-4-4/4-4-4-4)
M1
M2
M3
0.12
0.039
0.105
0.42
0.55
0.37
0.5
0.5
0.5
0.2
0.2
0.2
0.2
0.2
0.2
0.1
0.1
0.1
6 (buffer 4-4-4-4/4-4-4-4)
M1
M2
M3
0.067
0.029
0.0376
0.319
0.109
0.319
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
7 (buffer 4-4-4-4/4-4-4-4)
M1
M2
M3
0.001
0.019
0.08
0.125
0.217
0.6
0.4
0.4
0.4
0.3
0.3
0.3
0.2
0.2
0.2
0.1
0.1
0.1
P1
P2
P3
P4
P1
P2
P3
P4
P1
P2
P3
P4
0.368
0.362
-0.78
0.156
0.159
0.39
0.156
0.159
0.39
0.08
0.083
0.4
0.287
0.279
-1.12
0.221
0.221
-0.06
0.154
0.157
0.45
0.083
0.086
0.4
0.343
0.344
0.11
0.260
0.257
-0.28
0.176
0.174
-0.27
0.091
0.097
0.69
Test on 50 cases:
0.66 % error on average throughput
6.4 % error on average buffer levels.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Conclusions and future developments
New model to estimate the performance of multiple product flow
lines.
Ongoing work
 Split/merge systems with z different products
To be developed
 The continuous model with different processing times
 Closed systems with z different products
 Different production policies
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
System description
B1,1
M1
M ...
a 1,1
a 1, q
a1, z


a ..., 1
a ..., q
B1, z
a ..., z
M ...
Mi
Bi 1,...
B1,...
Bi 1, z
BK 1,1
Bi ,1
Bi 1,1
BK 1,...
Bi ,...
a i ,1
a i, q
a i, z
a ..., 1
a K ,1
a ..., q
Bi , z
MK
a..., z
a K ,q
BK 1, z
Eq is the average production rate of the system related to product q, with q=1,…,z
E is the overall average production rate of the system
z
E   Eq
q 1
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
a K ,z
The aggregation technique
B1 (q)
2P2M: twoproduct twomachine system
a1u ( q )
M u (q)
a au (q )
a1d (q)
a ad (q )
M d (q)
Ba (q)
Some relationships:
E (q )  E1 (q)  Ea (q )
q  1, , z
Ea ( q )   Er ( r )
q  1, , z
r q
E1 (q )  Ea (q )  E1 (q  1)  Ea (q  1) q  1,  , z  1
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
Algorithm
Step 1: Initialization of 2P2M systems.
Set the production probabilities of 2P2M systems to some initial value and the
buffer capacities.
Step 2: Solve 2P2M systems.
For q=1,…,Z solve the 2P2M system producing products q and a(q) using the
method in (Colledani et al., 2005).
Step 3: Calculate alphas.
For q=1,…,Z calculate the new values of production probabilities auq(q), aua(q),
adq(q) and ada(q).
Step 4. Check convergence.
The algorithm converges if all the production probabilities do not significantly
change from one iteration to another, otherwise go back to Step2.
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
p
r
a1
a2
a3
M
d
M
u
M
d
M
u
M
0.1200
0.1200
0.0104
0.2800
0.0320
0.12
0.12
0.12
0.12
0.06
0.5
0.5
0.5
0.5
0.5
0.4
0.4
0.4
0.4
0.3
0.1
0.1
0.1
0.1
0.2
d
0.0400
0.10
0.5
0.3
0.2
Case
u
1
2
3
M
N1
N2
N3
4
4
4
4
4
4
4
4
4
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione
The aggregation technique
0,5
0,45
E tot
0,45
0,4
0,4
E tot
0,35
0,35
0,3
0,25
E1
0,25
E
E2
0,2
0,2
E2
0,15
0,15
E1
0,1
0,1
E3
0,05
E3
0,05
0
0,
82
0,
78
0,
74
0,
7
0,
66
0,
62
0,
58
0,
54
0,
5
0,
42
25
23
N1
21
19
17
15
13
11
9
7
5
0
0,
46
E
0,3
a2
12
0,5
0,45
10
0,7
0,4
0,6
0,35
Ps 1
0,25
Pb1
0,2
4
0,15
0,4
E
6
E tot
0,5
0,3
Pb, Ps
0,3
0,2
E1
E2
E3
0,1
2
0,1
0,05
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
N1
0,
4
0,
42
0,
44
0,
3
0,
32
0,
34
0,
36
0,
38
0,
2
0,
22
0,
24
0,
26
0,
28
0
0
0,
1
0,
12
0,
14
0,
16
0,
18
n2,n3
0
0,
04
0,
06
0,
08
n average
8
n1
rd
Dipartimento di Meccanica
Sezione Tecnologie Meccaniche e Produzione