Online Library → Rodrigo Rubio → Product-form make-to-stock queueing networks → online text (page 1 of 2)

Font size

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

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 2

Online Library → Rodrigo Rubio → Product-form make-to-stock queueing networks → online text (page 1 of 2)