Slide 1

Report
Queueing Model for an Assemble-to-Order
Manufacturing System- A Matrix Geometric
Solution Approach
Sachin Jayaswal
Department of Management Sicences
University of Waterloo
Beth Jewkes
Department of Management Sciences
University of Waterloo
1
Outline

Motivation

Model Description

Literature Review

Analysis

Future Directions
2
Motivation
Get a better understanding of Assemble-to-Order
(ATO) production systems
Develop a queuing model for a two stage ATO
production system and evaluate the following measures
of performance:
Distribution of semi-finished goods inventory
Distribution of order fulfillment time
3
Model Description
External Supplier
1
Q1
Infinite Store
Semi finished
goods
BO
B1
Finished
goods
2
Q2
N2
N1
Stage 1
Stage 2
λ
Demand Arrival
4
Model Description
Notations:







λ : demand rate (Poisson arrivals)
μj : service rate at stage j, j=1, 2 (exponential service times)
B1: base stock level at stage 1 (parameter)
N1: queue occupancy at stage 1
N2: queue occupancy at stage 2
I1 : semi-finished goods inventory after stage 1. I1 = [B1 – N1]+
BO :Number of units backordered at stage 1. BO = [N1 – B1]+
5
Model Description
If B1 = 0, the system is MTO and operates like an
ordinary tandem queue:
The process describing the departure of units from
each stage is Poisson with rate λ
Individual queues behave as if they are operated
independently. In equilibrium, N1 and N2 are
independent
6
Model Description
For the ATO with B1 > 0:
Arrival process to stage 2 is no longer poisson.
There is a positive dependence between the arrival
of input units from stage 1 to stage 2. Times
between successive arrivals to stage 2 are correlated.
7
Related Literature
Buzacott et al. (1992) observe that C.V. of inter-arrival
times at stage 2 is between 0.8 and 1 and, therefore,
recommend using an M/M/1 approximation for stage2 queue. Lee and Zipkin (1992) also assume M/M/1
approximation for stage 2. (BPS-LZ approximation)
Buzacott et al. (1992) further improve upon this
approximation by modeling the congestion at stage 2 as
GI/M/1 queue. (BPS approximation)
Gupta and Benjaafar (2004) use BPS-LZ approximation
to compare alternative MTS and MTO systems
8
Solution – Matrix Geometric Method
State space representation 1

Consider a finite queue before stage 2 with size k

State description:
{N = (N1, N2) : N1 ≥ 0; 0 ≤ N2 ≤ k+1}
9
Infinitesimal Generator
Q=
 B0
A
 2











A0
A1
A2
A0
A1

A0

A2

A1
A2
A0
A1
A2
A0
A
A2
A0
A1

A0













 
This is a special case of a level dependent QBD
10
Solution…
State space representation 2
 Consider
 State
a finite queue before stage 1 with size k
description:
{N = (N2, N1) : N2 ≥ 0; 0 ≤ N1 ≤ k+1}
11
Infinitesimal Generator
 B0
A
Q= 2



A0
A1
A0
A2
A1

A0







Q is a level independent QBD process and hence can be
solved using standard Matrix-Geometric Method
12
An Exact Solution
 The
above methods are not truly exact as one of
the queues is truncated
 We next present an exact solution for the doubly
infinite problem, using censoring (Grassmann &
Standford (2000); Standford, Horn & Latouche
(2005))
 State
description: {N = (N2, N1) : N1 ≥ 0, N2 ≥ 0}
13
Censoring
Infinitesimal Generator
 B0'
 '
A2

Q=



'
A0
'
A1
'
A2


'
A0

'
'

A1 A0

   
14
Censoring
Transition Matrix: P   1Q  I ;   maxqii 
P
 B0
A
2

=



A0
A1
A2
A0
A1

A0







15
Censoring
Censoring all states above level 1 gives the
following transition matrix:
 B0 A0 
P(1) = 

 A2 U 
Censoring level 1 gives:
P0  B0  A0 I  U 1 A2
 B0  RA2
where R  A0 I  U 1
P(0) infinite only in one dimension
However, P(0) may no longer be QBD
16
Censoring
R matrix: R  A0  RA1  R A2
2
R
 R00
R
 10
=  R20
 
 Rk 0

 
R01
R02  R0 k
R11
R12
R21
R22  R2 k


 R1k


Rk 1
Rk 2  Rkk












limi Ri,ik  Rk i
R matrix possesses asymptotically block Toeplitz form
17
Censoring
P0  B0  RA2
P(0) =
P01
P02
 P00
 P
P11
P12
 10
 P20
P21
P22



 
 Pk 0
Pk1
Pk 2
P
Pk 11 Pk 12
 k 10
 Pk  20 Pk  21 Pk  22




 P0 k
 P1k
 P2 k
 
 P0
 P1
 P2
 
P0 k 1 P0 k  2 P0 k 3 
P1k 1 P1k  2 P1k 3 
P2 k 1 P2 k  2 P2 k 3 



 
P1 P2  
P0
P1  

P1 P0  

   
P(0) is also asymptotically of block Toeplitz form
Hence, one can use GI/G/1 type Markov chains to study P(0)
18
Censoring
GI/G/1 type Markov chain is of the form:

 B0

B
 1
P= 
B
 2
B
 3
 
C1
C2
C3
Q0
Q1
Q2
Q1
Q0
Q1
Q2
Q1
Q0






 





 
19
Censoring

 B0

B
 1

B
 2
B
 3
 
C1
C2
C3
Q0
Q1
Q2






 





 
To make P(0) conform to GI/G/1 type Markov chain, we
Q1 Q0 Q1
choose B0 to be sufficiently large to contain those
elements
Q2 Q1 Q0
not within a suitable tolerance of their asymptotic
forms
P(0) =
P01
P02
 P00
 P
P11
P12
 10
 P20
P21
P22



 
 Pk 0
Pk1
Pk 2
P
Pk 11 Pk 12
 k 10
 Pk  20 Pk  21 Pk  22






P0 k
P1k
 P2 k
 
 Q0
 Q1
 Q 2
 
P0 k 1 P0 k  2 P0 k 3 
P1k 1 P1k  2 P1k 3 
P2 k 1 P2 k  2 P2 k 3 



 
Q1 Q2  
Q0 Q1  

Q1 Q0  

   
20
Censoring
Transition matrix with all states beyond level n censored
(Grassmann & Standford, 2000)





n 1
Q
Q
Q
0
1
2

Q0
Q1n1
Pn 1   Q1

n 1
n 1
n 1

Q
Q
Q
2
1
0

 Qn3 2  Qn2 2  Qn1 2 






Q3n 2 
Q2n 2 
Q1n 2 
Q0n 2 









21
Censoring
Qi*
Qi*
Ci*

 Qi  
Qi* j
j 1

 Qi  
Q*j
j 1


I
i0


i0
*
* 1 *
Ci j I  Q0 Q j
j 1

1
Q*j I  Q0* Bi* j
j 1
 Ci  

 B0  
Ci*
j 1
i0
* 1 *
 Q0 Qi  j

Bi*  Bi  
B0*
I
* 1 *
 Q0 Q j

I

i0

* 1 *
 Q0 Bi
22
Solution to level-0 probabilities
Non-normalized probabilities αj for censored process
 0   0 B0* ;  00  1
n1
n  
 n1Qi*
i 1
n 1

i 1
I

* 1
 Q0
 n1Vi   0Cn*
*
I
  0Cn*

I
1
 Q0*

* 1
 Q0
;
Vi 
*
Qi*
I

* 1
 Q0
Normalized probabilities for censored process
 0  x0 0, x1 0, x2 0,...
x j 0 
j
t
t determined using generating function
(Grassmann & Standford (2000))
23
Solution
Stationary vector at positive levels
 k    k 1R
Performance measures
 EK2: Expected no. of units stage 2 still needs to
produce to meet the pending demands. EK2 = E(N2+BO)
 EI: Expected no. of work-in-process units.
EI = E(I1+N2)
24
Initial Results
B1
EK2
EI
1
4.1693
1.1693
3
3.0006
2.0006
5
2.2709
3.2709
7
1.8100
4.8100
9
1.5171
6.5171
λ=1; μ1 =1.25; μ2 =2
25
Future Directions
To construct an optimization model using the
performance measures obtained
To compare the results obtained with the
approximations suggested in the literature
26
27

similar documents