Curry G.L., Feldman R.M. Manufacturing Systems Modeling and Analysis

Подождите немного. Документ загружается.

References 123

Set p

(0,0,0)

= 0.0842, and determine the next ten probabilities; that is, p

(1,p,0)

and

then one set of three probabilities for each of the three equation-set forms similar to

Eqs. (4.8)–(4.10).

4.11. Develop the system equations for the steady-state probabilities for a single

operator servicing three machines. What type of difﬁculties will have to be over-

come to solve this system of equations for n → ∞, where n denotes the number of

machines for which the operator is responsible.

4.12. Consider an inﬁnite capacity 3-machine 2-operator service system where an

operator is required to setup a job on a machine before processing can begin. De-

velop the node-arc diagram for 5 or less jobs in the s ystem. That is, develop the

diagram explicitly for 0 to 5 jobs in the system with the understanding that the com-

plete diagram would contain an inﬁnite number of nodes. All processes, (arrivals,

setups and processing) are assumed to be exponentially distributed with mean rates

, and

, r espectively.

4.13. Consider an M/M/2/2 system with exponential breakdowns (rate

) and re-

pairs (rate

). The machines are identical and when one machine breaks down with

the other machine empty, the job being processed is left on the broken machine

while it is being repaired. Develop the state diagram for this system.

4.14. Consider an M/M/2/2 system with exponential breakdowns (rate

) and re-

pairs (rate

). The machines are identical and when one machine breaks down with

the other machine empty, the job being processed is moved from the broken ma-

chine to the operating machine instantaneously. Develop the state diagram for this

system.

References

1. Feldman, R.M., Deuermeyer, B.L., and Valdez-Flores, C. (1993). Utilization of the Method of

Linear Matrix Equations to Solve a Quasi-Birth-Death Problem, J. Applied Probability, 30:639–

649.

2. Hopp, W.J., and Spearman M.L. (2000). Factory Physics: Foundations of Manufacturing Man-

agement, second edn. IRWIN, Chicago

Chapter 5

Multiple-Stage Single-Product Factory Models

The mechanics for developing both exact and approximate single workstation mod-

els were developed in Chap. 3. Linking several workstations together is a necessary

step towards more realistic factory models. In this chapter, the single workstation

models are linked together to form more realistic factory models. The approach

taken is to use general G/G/1 and G/G/c system approximations of Properties

3.3 and 3.5 as the building blocks for multiple workstation systems. To properly

connect a series of workstations, the departure process of jobs from each worksta-

tion must be characterized. Speciﬁcally, the mean of inter-departure times and their

squared coefﬁcient of variation must be computed for a workstation. These param-

eters then describe the arrival process for the downstream workstation. For general

system conﬁgurations, there are two basic mechanisms that must be explored: (1)

the merging of several input streams into a workstation, and (2) the separation or par-

titioning of a workstation output stream into several different streams for different

target workstations. This chapter starts with workstations in series and progresses

to more complex general network conﬁgurations. Single product models are studied

in detail in this chapter and in Chap. 6 the methodology is generalized for multiple

product systems.

5.1 Approximating the Departure Process from a Workstation

In the study of single workstation models in Chap. 3, the workstation’s impact on the

output ﬂow of jobs from the workstation was not considered. This information was

not needed to study the performance of a single workstation, but when the output

from one workstation becomes the input to the next workstation, this information is

critical to system analysis. One of the main concerns of this chapter is the impact

that the workstation service and queueing processes have on trafﬁc ﬂow characteris-

tics. That is, we will study how the workstation transforms the inter-arrival process

characteristics into output-stream characteristics. Consider ﬁrst the mean ﬂow rate

for a system in steady state. In the long run, the same number of units must depart

G.L. Curry, R.M. Feldman, Manufacturing Systems Modeling and Analysis, 2nd ed., 125

DOI 10.1007/978-3-642-16618-1 5,

 Springer-Verlag Berlin Heidelberg 2011

126 5 Multiple-Stage Single-Product Factory Models

the workstation as enter the workstation. Otherwise, there would be a buildup (or

depletion) of jobs in the workstation and the queue would grow inﬁnitely (or units

would need to be created out of nothing) as time extends to inﬁnity. It may be that

units are destroyed, but we would account for those units as departing “scrapped”

units. Or, it may be that an assembly operation occurs so that the number of units

appears to change; however, we would consider the assembled unit as two units so

that the net ﬂow of material in is always equal to the net ﬂow out. Applying this

conservation of ﬂow concept, the mean output rate from a workstation must equal

the mean input rate to that workstation.

The inter-arrival and inter-departure times

random variables are denoted as T

and T

, where the subscripts a and d represent

arrivals and departures, respectively, for the workstation. Thus, the conservation of

ﬂow concept leads to the following property.

Property 5.1. The mean arrival rate of jobs to a workstation operating under

steady-state conditions equals the mean departure rate of jobs; that is

E[ T

]=E[T

] .

For exponential systems, namely M/M/c systems with c ≥ 1, the output process

is probabilistically identical to the input process; namely, the inter-departure times

are exponentially distributed so that C

= C

= 1. For non-exponential sys-

tems, obtaining the value of C

is a little more involved. Assume for the moment

that the workstation is extremely busy, then the distribution of the time between

departures would essentially be the service time distribution and so C

would be

expected to be very close in value to C

. At the other extreme, when the system

is very lightly loaded, the inter-departure times should be an arrival time minus the

service time for the last job plus the service time for the arriving job. Thus, the inter-

departure time distribution should be similar to the inter-arrival time distribution so

that C

should be very similar to C

. In fact, for an M/G/1 system (remember that

= 1forM/G/1 systems), Buzacott and Shanthikumar [3] show this is exact;

namely,

(M/G/1)=1 −u

+ u

, (5.1)

where u is utilization. They also develop for the G/G/1 system a lower bound on

(G/G/1) ≥(1 −u)



1 + uC



+ u

A general relationship for a G/G/1 system for the squared coefﬁcient of variation

was developed by Marshall [4]as

= C

+ 2u

−2u (1 −u)CT

/E[T

] , (5.2)

The conservation of ﬂow concept applied to networks is the same as the rate balance concept

used to derive the steady-state probabilities as discussed in Sections 3.1 and 3.2.

5.1 Approximating the Departure Process from a Workstation 127

which has the workstation queue time as an inﬂuencing variable. Using the previ-

ously developed approximation CT

=((C

)/2)uE[T

]/(1 −u) (Property 3.3)

and substituting it into Marshall’s formula, the result is the ﬁrst equation in the fol-

lowing property taken from Whitt [6].

Property 5.2. The squared coefﬁcient of variation of the inter-departure times

for a single server workstation can be approximated by

(G/G/1) ≈



1 −u



+ u

and for multiple server workstations by

(G/G/c) ≈



1 −u



+ u

√

c −1

√

where u = E[T

]/(cE[T

]).

The single-server approximation is a weighed sum of the two limiting conditions C

and C

. Note also that it is what one might conjecture as a generalization of (5.1)

since for the M/G/1 case C

= 1.

The two approximations given in Property 5.2 will sufﬁce for use in our gen-

eral queueing network approximation system development. There will be situations,

such as a batch server (Chap. 7), where a properly detailed model of the process

will produce better results than relying directly on these formulas. The reason for

improvements in the batching cases is due more to the lack of the independence as-

sumption between processing times for jobs served in batches than it has to do with

the inappropriateness of the C

approximations themselves.

Example 5.1. For a single server workstation, the inter-arrival distribution param-

eters are E[T

]=20 min and C

= 1/2. The service time distribution parameters

are E[T

]=15 min and C

= 1/3. Then

= 3/hr and

= 4/hr. Thus, the system

utilization factor u =

= 3/4. Using Property 5.2, the approximate value for the

squared coefﬁcient of variation of the inter-departure times is given by



1 −











= 0.40625 .

Note that this approximation result does not depend on the distributions of the inter-

arrivals or the inter-departures, only there ﬁrst two moments. 

• Suggestion: Do Problems 5.1 and 5.2.

128 5 Multiple-Stage Single-Product Factory Models

Fig. 5.1 A serial factory

structure with three worksta-

tions

5.2 Serial Systems Decomposition

The system under consideration in this section is a pure serial system with external

inﬂow into the ﬁrst workstation only and no branching. The departures from each

workstation are the inﬂows into the next workstation as illustrated in Fig. 5.1.This

system is treated as a series of G/G/c/∞ queues with speciﬁed service parameters

(E[T

(i)], C

(i), c

) for each workstation i, numbered from 1 to n. Because of the se-

rial nature of the system, the arrival stream for workstation i is the departure stream

from workstation i−1; thus, C

(i)=C

(i−1) for i = 2,··· ,n. In addition, the initial

workstation inter-arrival time distribution parameters E[T

(1)] and C

(1) (arriving

job characteristics) are assumed known. (In general, the characteristics of arriving

jobs from external sources are always assumed to be known.)

If we were limited to exponential processes, the system as a whole could be (the-

oretically) modeled using the state-diagram approach of Chap. 2; however, the dia-

gram approach becomes intractable even for small networks because of dimension-

ality problems of the state space. Another relatively easy approach is possible for

inﬁnite capacity exponential systems due to the fact that output for any M/M /c/∞

system is a Poisson process (see Burke [2]) with the same parameters as the input

process but statistically independent of the input process. Therefore, the approach

to modeling the network composed of M/M/c systems is to model each individual

node as if it were independent of all other nodes using as input to each node the

same arrival process as to the ﬁrst node.

Example 5.2. Patients arrive to the emergency room according to Poisson process

(i.e., with exponential inter-arrival times) with a mean rate of 4 per hour. When they

arrive, there is a single clerk who takes their information. This process takes an

exponentially distributed length of time with an average of 4 minutes per patient.

There is a triage nurse who next sees the patient. The nurse takes an exponentially

distributed length of time averaging 10 minutes per patient. Finally one of two doc-

tors sees the patient and each doctor takes an exponentially distributed amount of

time with each patient averaging 24 minutes with the doctor. We would like to know

the average number of patients within the facility at any one time and the average

time that a patient spends in the emergency room.

The emergency room system is composed of an M/M/1 system feeding a •/M/1

system feeding a •/M/2 system. Because of the above mentioned property that

M/M/c systems have exponential inter-departure times, the second and third nodes

are an M/M/1 and M/M/2 system, respectively, with an arrival r ate of 4 per hour

(Property 5.1). Furthermore, since each of the three nodes is an inﬁnite capacity

exponential system, the system can be analyzed as three independent single node

systems. The ﬁrst node has a utilization factor of u

= 4/15 (note that 4 minutes

5.2 Serial Systems Decomposition 129

per patient is 15 patients per hour) and thus the average number of patients in

the ﬁrst node is WIP(1)=4/11 (use Eq. 3.11). The second node has a utiliza-

tion factor of u

= 2/3 yielding WIP(2)=2 (again use Eq. 3.11). For the third

node, we ﬁrst ﬁnd the time spent waiting for the doctor. This is given by Prop-

erty 3.4 and yields CT

(3)=42.67 min since u

= 0.8. Adding the doctor’s time

to the wait time (Eq. 3.21) yields the time spent in third node as CT (3)=1.11

hr. Applying Little’s Law (Property 2.1) gives the average number of patients at

the node as WIP( 3)=4.44. Thus, the total number in the emergency room is

WIP

= 4/11 + 2 + 4.44 = 6.8. Applying Little’s Law one more time, yields the av-

erage value for the total time a patient spends in the emergency room as CT

= 1.7

hr. 

Although the analysis approach used in Example 5.2 is exact only under the as-

sumptions of inﬁnite capacity nodes and exponential distributions for inter-arrivals

and processing times, it provides the motivation for approximation schemes when

these assumptions do not hold. The analysis approach for general systems is based

on the concept that a system’s performance can be adequately approximated by sep-

arating the system into individual workstations. The performance characteristics of

the individual workstations are computed separately and then these results recom-

bined for the total system behavior. This decomposition approach is fundamental to

the approximation of general network conﬁgurations. The reasons that this decom-

position approach is only an approximation are two-fold: ﬁrst, Property 5.2 is an

approximation and second, the successive inter-departure times are not independent

except for the M/M/c/∞ case.

The decomposition approach is predicated on being able to establish the indi-

vidual workstation parameters needed for using Property 3.3 or 3.6. The required

data are the parameter set (E[T

(i)], C

(i), c

, E[T

(i)], C

(i)) for each workstation

i. The ﬁrst three parameters are speciﬁed data for the workstation. The last two pa-

rameters in the s et are for the job arrival stream into the workstation. These two

inter-arrival distribution parameters need to be estimated from the departure ﬂows

from the upstream workstations and, of course, the network structure. For serial

systems, the outﬂow from one workstation is the direct inﬂow into the next, so this

particular serial network topology allows for a sequential computation of these un-

known parameters. Starting with the known inﬂow data into the ﬁrst workstation,

all the necessary data are available and the ﬁrst workstation’s performance charac-

teristics (from Properties 3.3 or 3.6) and the departure stream characteristics (from

Properties 5.2) can be computed. The second workstation arrival stream character-

istics are made equal to the ﬁrst workstation’s departure stream. Thus for the second

workstation, the performance information and the departure stream parameters are

obtained. This becomes the needed information for the third workstation, and so

on. (It is now, hopefully, apparent how the topology of the network impacts the

analysis. For a general system structure, the topology is more complex and these

data must be computed simultaneously leading to the development of a system of

equations as seen in Section 5.4 that must be solved to obtain the inter-arrival distri-

bution parameters.) As always, the arrival stream and service characteristics deﬁne

the workstation utilization as u

= E[T

(i)]/(c

E[T

(i)]).

130 5 Multiple-Stage Single-Product Factory Models

The departure stream characteristics for each workstation consists of the mean

inter-arrival time and the squared coefﬁcient of variation of these times. For a se-

rial system in steady state, the workstation mean inﬂow rates must be identical for

all workstations. (The assumptions of no losses, no reworks, and one external in-

ﬂow point are critical to this simpliﬁed method for computing these inﬂow rates.)

Thus, E[T

(i)] = E[ T

(1)] for all workstations i = 2,··· ,n. There remains only the

task of computing the C

(i) term for each workstation i and the serial structure of

the network allows for these computations to be carried out sequentially. A recur-

sive algorithm can be easily developed for the factory based on the following two

properties.

Property 5.3. The mean cycle time and departure process for an inﬁnite ca-

pacity single-server workstation within a factory that has a pure serial system

topology are given by

CT(i) ≈



(i −1)+C

(i)



1 −u



E[T

(i)] + E[T

(i)] and

(i) ≈



1 −u



(i −1)+u

(i) ,

where i is the sequence number of the workstation and C

(0) is the squared

coefﬁcient of variation of the arrival stream to the ﬁrst workstation. (The only

arrivals are to the ﬁrst workstation.)

Property 5.4. The mean cycle time and departure process for an inﬁnite ca-

pacity workstation with c servers within a factory that has a pure serial system

topology are given by

CT(i) ≈



(i −1)+C

(i)





√

+2−1

(1 −u

)



E[ T

(i)] + E[T

(i)] and

(i) ≈ 1 +



1 −u



(i −1) −1



+ u



(i) −1



√

where i is the sequence number of the workstation and C

(0) is the squared

coefﬁcient of variation of the arrival stream to the ﬁrst workstation. (The only

arrivals are to the ﬁrst workstation.)

Once the cycle times for the individual workstations have been obtained, the

overall system performance measures can be determined. The cycle time in the to-

tal system can be computed for serial systems by merely summing the individual

workstation times since every job visits each workstation exactly once during its

processing. This is not a general computation scheme and is, therefore, forgone in

5.2 Serial Systems Decomposition 131

favor of a method that is valid for all network topologies. The more general approach

is to use Little’s Law to compute the mean number of jobs, WIP

(i), in each work-

station, sum the workstation means together to obtain the total factory mean number

of jobs, WIP

, and then obtain the system mean cycle time through the application

of Little’s Law again; thus

WIP

∑

i=1

WIP

(i)=

∑

i=1

CT(i)

E[ T

(i)]

and (5.3)

= E[T

(1)] ×WIP

. (5.4)

Equation (5.3) is independent of the job ﬂow sequence and, hence, valid for any

network topology. Notice that for the mean throughput rate, the reciprocal of the

mean inter-arrival times is used since all arrivals will eventually pass through the

workstation. Equation (5.4) is not very general because it assumes that all arrivals

to the factory enter through the ﬁrst workstation. In later sections, this may not be

true.

Example 5.3. Consider a three-workstation factory with serial ﬂow as depicted in

Fig. 5.1. Each workstation has a single machine with the service time distribution

parameters as listed in Table 5.1. The inter-arrival time distribution for jobs to the

Table 5.1 Service time characteristics for Example 5.3

Workstation iE[T

(i)] C

(i)

112min2.0

29min0.7

3 13.2 min 1.0

factory has a mean of 15 minutes or a mean rate of 4 jobs per hour, and a squared

coefﬁcient of variation of 0.75. The system mean work-in-process, cycle time, and

throughput are desired.

Since arrivals to the system occur at the ﬁrst workstation, E[T

(1)] = 15 min

yielding a utilization factor of u

= E[T

(1)]/E[T

(1)] = 0.8. Using the network

decomposition principle together with Property 5.3 yields the following for the ﬁrst

workstation:

CT(1)=



(1)+C

(1)



1 −u



E[T

(1)] + E[T

(1)]



0.75 + 2.0



0.8

0.2

(12 min)+12 min

= 78 min = 1.3hr

(1)=



1 −u



(1)+u

(1)



1 −0.8



0.75 + 0.8

(2.0)=1.55 , and

132 5 Multiple-Stage Single-Product Factory Models

WIP(1)=CT (1) ×

E[ T

(1)]

1.3hr

0.25 hr

= 5.2 .

The last equation comes from the application of Little’s Law, and since no jobs are

lost, the throughput rate is th = 1/E[T

(1)]. Notice that care must always be taken

to make sure that the time units are consistent when applying Little’s Law. Because

this is a pure serial network, the arrival rate and throughput rate will be the same for

each workstation; thus, the utilization factors for the other two workstations are u

E[T

(2)]/E[T

(1)] = 0.6 and u

= E[T

(3)]/E[T

(1)] = 0.88. Applying Property 5.3

and Little’s Law to the second and third workstations yield

CT(2)=



1.55 + 0.7



0.6

0.4

(0.15 hr)+0.15 hr = 0.403 hr

(2)=



1 −0.6



1.55 + 0.6

(0.7)=1.244

WIP(2)=CT (2)/E[T

(1)] = 1.613 and

CT(3)=



1.244 + 1.0



0.88

0.12

(0.22 hr)+0.22 hr = 2.030 hr

(3)=



1 −0.88



1.244 + 0.88

(1.0)=1.055

WIP

(3)=CT (3)/E[T

(1)] = 8.121 .

Finally, the total factory performance characteristics for this serial system are

WIP

= 5.200 + 1.613 + 8.121 = 14.933 jobs

E[ T

(1)]

= 4/hr

WIP

= 3.733 hr .

As a comparison, a simulation model was developed for this serial factory struc-

ture using Excel. (The appendix of this chapter presents the use of Excel for sim-

ulating networks for single-server workstations.) The gamma distribution was used

for the random inter-arrival times and service times with the appropriate means and

squared coefﬁcients of variations. Five replicates of the model were obtained with

each replication being a simulation of 32,000 customers through the system. Table

5.2 displays the analytical approximation results with those obtained from the simu-

lation. The analytical approximations are given ﬁrst followed across the row by the

simulation estimates with the half-width of the 95% conﬁdence interval also shown

for the simulation. (The estimate for the squared coefﬁcients of variation were ob-

tained by estimating the variance and dividing by the square of the mean estimate;

thus, it is a biased statistic. The conﬁdence interval is based on Eq. (3.25)soitis

technically not correct for ratios; however, it does give some idea of the variability

of the estimator.)