Copyright
Rodrigo Rubio.

Product-form make-to-stock queueing networks online

. (page 1 of 2)
Online LibraryRodrigo RubioProduct-form make-to-stock queueing networks → online text (page 1 of 2)
Font size
QR-code for this ebook


iiliii



M.f.T. U'^*^'.^fi - D^^WEY



HD28
.M414



@



Dewey



WORKING PAPER
ALFRED P. SLOAN SCHOOL OF MANAGEMENT



Product-Form Make-to-Stock Queueing
Networks

Rodrigo Rubio

Lawrence M. Wein



#3672-94-MSA



April 1994



MASSACHUSETTS

INSTITUTE OF TECHNOLOGY

50 MEMORIAL DRIVE

CAMBRIDGE, MASSACHUSETTS 02139



Product-Form Make-to-Stock Queueing
Networks

Rodrigo Rubio

Lawrence M. Wein

#3672-94-MSA April 1994



Product-Form Make-to-Stock Queueing Networks

Rodrigo Rubio

Operations Research Center, M.I.T.

and

Lawrence M. Wein

Sloan School of Management, M.I.T

Abstract

A manufacturing facility produces multiple products in a make-to-stock manner, and
unsatisfied demand is backordered. A simple production control policy is analyzed: when the
amount of work-in-process inventory plus finished goods inventory for a particular product
falls below a base stock level, then release another unit of product onto the shop floor. Under
a set of stationarity assumptions, we show that the cost minimizing base stock level for each
product satisfies a critical fractile expression for the steady state distribution of the products
total work-in-process inventory. By exploiting the relationship between the make-to-stock
system and an open queueing network, we identify specific formulas for the base stock levels
under standard product-form assumptions. For the lost sales case, a similar relation to a
closed queueing network can be used to characterize the optimal control parameters.

April 1994



1. Introduction

We consider a manufacturing system that produces a variety of products in a make-
to-stock mode; that is, completed units enter a finished goods inventory that services ex-
ogenous customer demand, and unsatisfied demand is backordered. Production control in
this production- inventory environment has been moving away from the push philosophy em-
bodied in materials requirement planning (MRP) systems, and towards the pull philosophy
typified by kanban systems. Unfortunately, kanban control policies are difficult to imple-
ment for multi-product systems, particularly if a different buffer level is set for each prod-
uct at each production stage. Moreover, even single-product kanban-controlled production-
inventory systems axe difficult to analyze (see, e.g., Mitra and Mitrani 1991), and to our
knowledge, multi-product kanban systems have not been analyzed in the literature. Mo-
tivated by the difficulty of implementing and analyzing kanban policies in multi-product
production-inventory systems, we propose and analyze a very simple pull-type production
control policy for a multi-product make-to-stock environment. Our policy could not be
simpler or more natural: release a new unit of a product onto the shop floor whenever the
total work-in-process (WIP) plus finished goods (FG) inventory (where backordered demand
represents negative inventory) for this product falls below a specified base stock level.

This policy can be viewed as a make-to-stock analog of the CONWIP (constant WIP)
policy (see Spearman et al. 1990, and Koenigsberg 1958, Jackson 1963, Gordon and .Xewell
1967, Solberg 1977 and Whitt 1984 for earlier studies), and has its roots in Clark and Scarf's
(1960) echelon inventory policy for multistage uncapacitated inventory systems. The policy
enjoys some of the same advantages as the traditional CONWIP policy, as articulated by
Whitt, Spearman et al. and Muckstadt and Tayur (1993): it is very easy to implement,
robust (since controlling inventory is easier than controlling throughput), and prevents bot-
tleneck starvation.



1



Readers are referred to Buzacott and Shanthikumax (1992) for an excellent literature
survey of various production control strategies for multistage systems. The starting point for
our analysis is Buzacott et al. (1992) and Lee and Zipkin (1992), who develop approximate
performance measures for a tgmdem single-product production-inventory system, in which
each station is controlled by a base stock policy. In the initial development of their work,
both make observations to the effect that, when the base stock level of all stations except the
last one is set to zero, the system can be analyzed by means of a traditional open queueing
network. Our paper employs this observation in a more general setting.

In Section 2, a multi-product production-inventory system is considered under the
proposed base stock policy. We address the problem of choosing the optimal base stock level
for each product to minimize the long run expected average cost of holding WIP and FG
and backordering FG. The optimal base stock level for each product is characterized as a
critical fractile of the steady state distribution of the total WIP for that product; moreover,
the optimal base stock levels are independent of the WIP holding costs. Since the shop floor
is viewed here as a black box, rather than as a network of queues, this result holds as long
as the total WIP process for each product possesses a steady state distribution with finite
mean, regardless of distributional assumptions, setup times, scheduling policy or routing
structure. In Section 3, the result is specialized to the case where the shop is modeled as a
Jackson queueing network; that is, each machine has exponential service times, exogenous
demand is Poisson, job routing between workstations is Markovian, and the first-come first-
served (FCFS) policy is employed at each station. Under these product-form assumptions, a
formula characterizing the optimal base stock level is derived. Since a closed form expression
for the optimal base stock level is not available, we numerically compute optimal base stock
levels for some balanced production-inventory systems. Of particular interest is the fact that
the optimal base stock level appears to grow almost linearly in the number of stations; this



linearity is partially explained by an application of Chernoff 's exponential bound.

Section 4 briefly discusses three generalizations. By modeling the shop floor as a net-
work of quasireversible queues, we show how the powerful results for product-form multiclass
queueing networks (see Baskett et al. 1975 and Kelly 1979) can be employed to determine
the optimal base stock level for each product in a multi-product system. The remainder of
the section deals with the single-product and multi-product cases for production-inventory
systems in which unserved demand is lost. Although additional difficulties arise from the
fact that the related queueing network is closed, our analysis allows for a practical means to
find the optimal base stock policy.

There axe several straightforward generalizations that we do not investigate here. One
example is a mixed system (see Carr et al. 1993 and Nguyen 1993 for the single queue case),
where some products are produced in a make-to-stock fashion and others in a make-to-stock
mode. Another example is to incorporate infinite server queues with general service time
distributions to model the transportation delays incurred in material handling systems on
the shop floor or in production-distribution systems.

2. Base Stock Control of Make-to-Stock Systems

Consider a manufacturing facility that produces I products indexed by i = 1, . . . , /.
Completed units enter a finished goods inventory that is depleted by exogenous customer
demand, and unsatisfied demand is backordered. Let A^{t) denote the cumulative number
of type i items demanded in [0,i]. Without loss of generahty, we assume that the system
starts with Zi units in FG for product i and no WIP. The proposed control policy releases
a new unit of a product onto the shop floor whenever a unit of that product is demanded
by a customer. For product i, let Zi{t) denote the FG inventory, where a negative quantity
represents backordered demand, and let A^,(i) be the amount of WIP inventory on the shop



floor at time t. Since the demand for one unit of product i simultaneously depletes the
FG inventory and increases the WIP inventory by one unit, the total inventory position
Ni{t) + Zi{t) for product i, which is the total physical inventory net backorders, is held
constant at its initial value of z,. Although product vs FG inventory is never larger than
the base stock level 2,, backordered demand allows the WIP inventory to attain arbitrarily
high levels.

In Section 3, the manufacturing facility will be modeled as a queueing network with
individual workcenters and corresponding service time distributions, and a specific routing
structure and queueing discipline. Here, no specific assumptions are made regarding the
demand distributions, the routing structure of the facihty, the scheduling policy, the service
time distributions, machine breaicdowns and repair, or setups. Instead, we treat the facility
as a black box that is characterized by a vector of stationary departure processes, where
Di{t) is the number of completed units of product i delivered to FG by time t; of course, the
departure processes axe a function of the demand processes, which act as the input processes
to the black box.

Under the proposed policy, it follows that N^i^t) = ^4,(0 - A(0 and Z,(i) = ^, +
Di{t) — Ai{t) for z = 1, . . . , / and t > 0. Our primary assumption is that the WIP process
{Nt{t),t > 0} possesses a steady state distribution with finite mean for i = 1, . . . . /. We
do not delve into the fundamental problem of characterizing the class of demand processcn^
and the class of stochastic models for the black box that give rise to a WIP process having
a steady state distribution with finite mean. If the traffic intensity is less than one ai each
station, then this property is possessed by all Jackson-type networks with jointly slalintiarv
and ergodic inputs, services and routing (Baccelli and Foss 1994) and all prodiici-lnrrn
multicla^s queueing networks (Kelly, Chapter 3). However, the characterization of - lalili'
multiclass queueing networks is an open problem, and is currently the subject of intiri>nf



research activity (see, for example, Rybko and Stolyar 1992, Bramson 1993, Dai 1993 and
Kumar and Meyn 1993).

Let Ct denote the cost of holding one unit of product i in WIP inventory per unit of
time, hi be the corresponding FG holding cost rate, and 6j be the cost of backordering one
unit of product i per unit time. The optimization problem is to find the base stock levels Zi
to minimize the long run expected average cost of holding and backordering inventory. If we
denote the steady state WIP inventory for product z by A^,, then the problem is to choose
(zi,. . . ,zi) to minimize



/ /



^a(z.)=i] qE "^(^' = '^) + ^'E ^^(^' = z,-k)-b,Y. kP{N, = z,- k)]

t=l 1=1 \ n=0 fc=0 *:=-oo /



/



=E (^> + ^0



t=i



oo



z,P{N, < z, - I) + Y.^P{N, = n)



n=2.



b,z, + {c-K)E[NM.{\)



Thus, it suffices to study the steady state WIP Ni to determine the optimal base stock level
z*. The main result of this section is the following.

Proposition 1 The optimal base stock level z* is the smallest integer that satisfies

// this condition is satisfied with equality, then the expected cost obtained by using the optimal
base stock level is

E C^'iz*) = E f (c + k)E[N,] - {K + k) E nP(7V. = n)) .

i=l 1=1 \ n=0 /

Proof. Equation (1) implies that | {Q{z^ - 1) + Q{z, + 1)) = C,{z^)+^{k+K)P{N^ =
Zi) > Ci{zi), and so Ci{zi) is a convex function of 2,. Furthermore, E[Ni\ < oo by as-
sumption, so that C,(0) = (1 4- bi)E[Ni] < oo and C,(oo) = oo. Since the cost is a
convex fimction of 2, that must increase at some point, the optimal value for the base



stock level is found by increasing 2, until C,(2, + 1) — Ci{z,) > 0. Equation (1) gives
C,(z, + 1) - Cx{zi) = (/i, + bi)P{Ni < Zx) - 6,, which proves the desired result. ■

A few remarks are in order. First, Proposition 1 characterizes the optimal base stock
level as a critical fractile of the W'lP distribution. Since the W'lP process {Ni{t),t > 0} is
independent of the base stock level, it is not surprising that the WIP holding cost c, does
not appear in the expression for z' . Also, because the optimal value for z' is restricted
to be integer, the cost J2i=i C^'^iz') in Proposition 1 is in genergd only a lower bound; the
true optimal cost J2i=i Ci{z') is obtained by substituting z' into equation (1). Notice that
C,{z') - Ct\z*) = ^; [(/i, +6,)P(iV, < z;) - b,] > 0, which is zero when the optimality
condition is satisfied with equality, but will otherwise yield a value that is linear in z*.

Although Proposition 1 is easy to derive, the result is deceptively powerful, because
very few conditions are imposed on the production-inventory system; for example, no as-
sumptions are made regarding the distributions of the service and demand processes, the
routing structure, or the queueing discipline. Consequently, factories can gather historiced
data to generate an empirical distribution of the total WIP inventory for each product, and
then employ Proposition 1 to find the optimal base stock levels. Alternatively, a detailed
Monte Carlo simulation model could be used to generate the WIP distributions. In the
next section, we model the shop floor as a queueing network to obtain an analytical WIP
distribution.

3. Make-to-Stock Jackson Networks

Because each demand simultaneously depletes the FG inventory and triggers an arri\al
to the shop, the shop floor can be modeled as an open queueing network willi arrivals
corresponding to exogenous demands. Therefore, the steady state WIP inventory ,V, is
given by the steady state number of type i customers in an open queueing network, hi ihis



section, we look at the special case / = 1, and model the shop floor as an open Jackson
network; to simplify notation, the subscript denoting the product type will be omitted for
the remainder of this section.

Consider K single-server stations, where the server at station j has an exponential
service time distribution with service rate /i^; although multiserver stations also give rise to a
product-form solution, we restrict ourselves to single-server stations to keep the subsequent
analysis relatively simple. Let the demand for the single product follow a Poisson process
with rate A. Suppose the corresponding arrivals to the shop floor are routed randomly to the
K stations, so that the arrivals are independent Poisson processes with rate \j,j = \...,K
where SjLi Aj = A. After completing its service requirement at station z, an item visits
station j with probability Ptj , and exits the shop floor (and hence enters the FG inventory)
with probability 1 — Y^f=\ Pij, where we assume that the spectral radius of the routing matrix
P — [pij] is less than 1 so that all items eventually exit the system. Define the vector of
effective arrival rates (i^i, . . . , v^) to be the solution to v^ — X^-^- Yl!k.= \ ^kPkj, J — I,. . ■ , K.
The traffic intensity at station j is Pj = u-,/ p,^ where, to guarantee the existence of a steady
state distribution, we assume that p^ < 1, j = 1,...,/C. Finally, assume that the FCFS
service discipline is used throughout the network.

Under these assumptions, the shop floor is modeled as a Jackson network, and the
classic product-form solution implies that the steady state total WIP distribution is given by
the sum of K independent geometric random variables with parameters 1 — pi, . . . , 1 — pK-
We will consider the two extreme cases where the traffic intensities at the various stations
are distinct, and where they are all equal; our approach can easily be extended to any
intermediate case.

Without further loss of generality, assume that the stations are numbered so that
P\ < P2 < ■ ■ ■ < pK < ^- If we define the z-transform of the steady state total WIP A^ as



Pj;{z) = E[z% then

pT(. _ nf=.(i-P.)

n;=i(l - zp])
A partial fractions expansion gives P(N = n) = HJLi ctjp^, where

a, = -^'-r: -. ; .

Ue^j{pj-Pe)
Hence, the cumulative distribution function of N is

P{N 0) > 0, and let M{s) = \ogE{e^^') be their
common logarithmic moment generating function. Then Chernoff's bound states thai

-logF(Xi + ... + X„>0) z)< inf f ^~^ 1 e-"^ (7)

ae(0,-lnp) yi - pt°- )

for any z > Kp/{1 — p). This bound, used together with Proposition 1, gives

z*< inf (a-Mnf-i^^W + a-Mnf^H, (8)

-ae{o,-inp)[ \\ - pe" ) \ h )]

so that z* is upper-bounded by a linear function of K.

We can tighten the bound in (8) by optimizing over a 6 (0, - Inp). Straight torw.ird
minimization of the right side of (8) is difficult because it is not convex in a. Howcwr. ihc

9



value of a thai minimizes the bound in (7) is

2

(9)



a = in



Since a* is a function of the unknown base stock level z, we use the following iterative
procedure to find the optimal value of a to employ in (8). Start with an initial value
do e (0,-lnp) and substitute it into the right side of (8) to obtain an initial base stock
level zq. Then use (9) to get an updated value a\, and so on. In all 120 cases, we used
Oo = — lnp/2, and the value of a did not change after a\. If we use this procedure to
determine a in (8), then the large deviation approximation implies that this bound is tight
as /C — oo.

Although a closed form solution for z' is not available in general, both (2) and (4)
are easy to solve numerically, and the remainder of this section is devoted to a numericaJ
investigation. The primary objective is to explore how the optimal base stock level z' varies
as K , the number of stations, increases. To this end, we compute the optimal base stock level
for 120 balanced Jackson networks, using five different values of p, 12 different network sizes
and two backorder-to-holding cost ratios, ^ = 3 and ^ = 10. These results are reported in
Table 1 and plotted in Figures 1 and 2. As expected, z* grows considerably as the utilization
approaches unity. However, the most striking feature of the results is that the optimal base
stock level grows almost Unearly with the number of stations, as suggested by (8).

NumericaJ calculations of the upper bound for z' in (8) show that this bound is not
very tight, even for K as large as 40. Hence, we also consider the base stock level that
combines the slope of the Chernoff bound in (8) with the exact result for A" = 1 in (5):



In p






l+a-Mn(-^ ^\{K-\). (10)



1 - pe"

To compute the value of a in (10), we employ the iterative procedure described earlier, but
with (10) replacing (8). The resulting base stock levels are displayed in Table 2 £Lnd, as can

10



z*


250 ,













200 .




^y^




n no










150 .


.


^^




r\ w^














^^"^^




. =0.8






100 .




^S"^^^^




(1 7






50 .



_^^ 3^^^ 1-*"'






A C












' "T 1








c


) 5 10

Number of Stations


15 20







Figure 1: Optimal base stock level z* for r = 3.




Figure 2: Optimal base stock level z* for | = 10.



11



^ = 3













K.


Xum


ber of Stations








p


1


2


3


4


5


6


7 8 9


10


15


20


0.90


13


25


36


47


57


67


78 88 98


108


158


207


0.85


8


16


23


29


36


43


49 56 62


68


100


131


0.80


6


11


16


21


26


30


35 40 44


49


71


93


0.70


3


7


10


12


15


18


21 23 26


29


42


54


0.50


1


3


4


6


7


8


9 10 12


13


18


24



10













K,


Number of Stations








p


1


2


3


4


5


6 7 8 9


10


15


20


0.90


22


37


50


63


75


87 98 110 121


132


186


239


0.85


14


24


32


40


48


55 63 70 77


84


118


151


0.80


10


17


23


29


34


39 45 50 55


60


84


108


0.70


6


10


14


17


20


24 27 30 33


36


50


64


0.50


3


5


6


8


9


11 12 14 15


16


23


29



Table 1: Optimal base stock level for a baJanced network.

be seen in Figures 3 and 4, are very close to the optimal base stock levels. In fact, the
percentage cost increase under the base stock level in (10) relative to the optimal cost was
calculated for all 120 scenarios, and this quantity ranged from 0.0% to 2.8%, and averaged
0.6%. Notice that, as the large deviation principle suggests, the approximation improves
with larger values of |.

A second objective of the numerical study is to investigate the value of the cost \mder
the optimal base stock policy. Since only the relative costs axe relevant, we set the W'lF^
holding cost c = 1, and let the FG holding cost h = 2. The values of C{z') for all 120 cases
are listed in Table 3 and graphed in Figures 5 and 6. Notice that the cost at the optimal
base stock level grows slightly less than linearly in the number of stations. Although the
numerical results are not reported here, we also found that the cost function is rather Hat
near the optimal base stock level, suggesting that the base stock policy is relatively robust
to estimation errors in the system parameters.



12



Base 250
Stock

' - *'200 .

150 .

100 -

50 .

.



^•'p =0.90




^






Approx.






5 10 15 20
Number of Stations





Figure 3: Optimal vs. approximate base stock level for ^ = 3.



Base 250
Stock

•^-'1 200 .

150 .


r


^ p = 0.90






— — —• — - Approx.


^^^


^^ p = 0.85




100 .




^^^ p = 0.80
_^_^,^p =0.70




50 ■




p-0.50







5 10 15
Number of Stations


20





Figure 4: Optimal vs. approximate base stock level for ^ = 10.



13



! = 3













f


1

Online LibraryRodrigo RubioProduct-form make-to-stock queueing networks → online text (page 1 of 2)