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 ; maxqii 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: P0 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,ik Rk i R matrix possesses asymptotically block Toeplitz form 17 Censoring P0 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 P1 P2 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 P1 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 Q1 Q0 Q1 Q2 Q1 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 Q1 Q0 Q1 choose B0 to be sufficiently large to contain those elements Q2 Q1 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 Q1 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 Q1 Q0 20 Censoring Transition matrix with all states beyond level n censored (Grassmann & Standford, 2000) n 1 Q Q Q 0 1 2 Q0 Q1n1 Pn 1 Q1 n 1 n 1 n 1 Q Q Q 2 1 0 Qn3 2 Qn2 2 Qn1 2 Q3n 2 Q2n 2 Q1n 2 Q0n 2 21 Censoring Qi* Qi* Ci* Qi Qi* j j 1 Qi Q*j j 1 I i0 i0 * * 1 * Ci j I Q0 Q j j 1 1 Q*j I Q0* Bi* j j 1 Ci B0 Ci* j 1 i0 * 1 * Q0 Qi j Bi* Bi B0* I * 1 * Q0 Q j I i0 * 1 * Q0 Bi 22 Solution to level-0 probabilities Non-normalized probabilities αj for censored process 0 0 B0* ; 00 1 n1 n n1Qi* i 1 n 1 i 1 I * 1 Q0 n1Vi 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 1R 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