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

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

8.1 Closed Queueing Networks for Single Products 243

returned to Workstation 1 and 90% are sent to Workstation 3. From Workstation 3,

10% are defective and are again sent back to Workstation 1 and 90% are good and

shipped to the customer. A control will be placed on this factory so that there will

always be exactly 25 jobs in the system. To implement this policy, a job will be

started whenever a ﬁnished job is shipped to a customer. In such a situation, jobs

are actually ﬂowing into the system and out of the system, but mathematically, it is

equivalent to the closed system shown in Fig. 8.1. The throughput rate of this system

is the ﬂow rate of jobs along the upper path (the path indicating a 9/10 probability

branch) leaving Workstation 3 and returning to Workstation 1. 

The mathematical analysis of a closed queueing network starts with solving for

the ﬂows between workstations. It is assumed throughout the chapter that there are

n workstations. A slight problem exists for closed-queueing networks in that there

is no longer a unique set of ﬂow rates that describe the system. This is not surprising

if one considers that the ﬂow rates are dependent on the number of jobs allowed in

the system, w

max

. To illustrate this point, again consider Fig. 8.1. The arrival rates

to each workstation must satisfy the following

= 0.1

= 0.9

It is now easy to verify that the solution

(

)=(1,1,0.9)

satisﬁes the ﬂow requirements of Fig. 8.1. But it is also true that

(

)=(2,2,1.8)

also satisﬁes the ﬂow requirements. In fact, any multiple of the vector (1,1,0.9)

would satisfy the above equation f or the three rates, so obviously a unique set of

ﬂow rates cannot be found. But what can be found are the relative ﬂow rates, call

these the vector (r

), that give the rates with respect to each other. For the

above example, these rates are (1, 1, 0.9), based on the ﬂow for either of the ﬁrst two

workstations. These relative rates are (1/0.9, 1/0.9, 1) if they are computed relative

to the ﬂow of the third workstation.

Before developing a method to obtain the relative ﬂow rates, consider the difﬁ-

culty in attempting to perform the standard ﬂow rate analysis (see Sect. 5.4.1). In

general, a solution to the following system of equations is required

= P

where

is the vector of unknown internal ﬂow rates,

is the vector of known rates

of arrivals from an external source, and P is the routing matrix giving the branch-

ing probabilities. Since there are no external inﬂows for closed queueing networks

244 8 WIP Limiting Control Strategies

(namely,

= 0), the system can be rewritten as

(I −P

)

= 0 ,

where I is an identity matrix (see Property 5.7).

Now if the inverse of (I −P

) exists, the ﬂow can only be zero (

= 0).By

the illustration above, the ﬂow rates are not zero, so one can conclude that (I −

)

−1

does not exist. In fact this is always true for a closed queueing network,

i.e., the matrix (I −P

) is nonsingular. Therefore, a dependent system of equations

results when the external ﬂows are zero. For this situation, any one of the equations

can be dropped from the system. (Technically, this is an eigenvector problem for

a positive matrix whose row sums all add to one. The maximum eigenvalue is one

and the solution i s, therefore, unique up to a multiplicative constant. As long as no

workstation or group of workstations is isolated from the other workstations, there

will be exactly one redundant equation.) That is, any one of the relative ﬂow rate

factors r

can be set to some positive constant and then the other ﬂow rate factors

can be obtained relative to this value. For example using Fig. 8.1,letr

= 1 and

then solution is (r

)=(1 , 1,0.9);letr

= 1 and the relative ﬂow rates are

)=(1 /0.9,1/0.9,1).

With this dependency, the question arises as to the proper methodology for ob-

taining these relative ﬂow rates. The above approach is used, where one of the r

is set to a constant. Without loss of generality, r

will always be set to 1 and, thus,

it is no longer necessary to include the unknown r

in the system of equations. To

illustrate, notice that routing matrix for Fig. 8.1 is

P =

⎡

⎣

010

0.100.9

100

⎤

⎦

Now, after eliminating the ﬁrst equation and setting the ﬁrst variable equal to 1, the

system of equations becomes

= 1







100

00.90



⎛

⎝

⎞

⎠

which can be written as

= 1











0.90





This system becomes

8.1 Closed Queueing Networks for Single Products 245

= 1









−



0.90



−1





yielding (r

)=(1,1,0.9).

This same logic can be extended to a general closed network resulting in the

following general property.

Property 8.1. Let P denote the routing matrix associated with a closed queue-

ing network containing n workstations, and let Q denote the submatrix

formed from P by deleting the ﬁrst row and ﬁrst column; that is, q

i, j

i+1, j+1

for i, j = 1,··· ,n −1. Then the vector of relative arrival rates to

each workstation, r, is given by r

= 1 and

⎛

⎜

⎝

⎞

⎟

⎠



I −Q



−1

⎛

⎜

⎝

1,2

1,n

⎞

⎟

⎠

Notice that I is an identity matrix of dimension n −1 ×n −1 and the column vector

on the right-hand side of the equation is the ﬁrst row of the routing matrix minus the

ﬁrst element.

• Suggestion: Do Problems 8.1 and 8.2.

8.1.1 Analysis with Exponential Processing Times

In this section, a system of equations for determining the mean cycle time and the

expected WIP in each workstation is developed under the assumption that all pro-

cessing times are exponentially distributed. The approach used when all worksta-

tions have only one server and there is only one product within the factory serves as

the building block for the more complicated cases; therefore we discuss the simplest

case ﬁrst and then extend those models to the other cases.

8.1.1.1 Single-Server Systems

The methodology used to determine mean cycle times within a closed network is

called a mean value analysis. In the initial models of queueing systems, the approach

was to obtain the probability distribution for the number of jobs within the system,

and then from the number of jobs, the various measures were obtained. We now

246 8 WIP Limiting Control Strategies

bypass the probabilities and determine the mean values directly. The results for the

exponential cases are exact.

In order to use the same notation as in t he previous chapters, the letter w will be

used to denote the number of jobs within a system. Thus, we continue to use n for

the total number of workstations and k as the workstation index. In later sections,

i will denote the type and m will be the total number of types within the factory;

however, for this section, m = 1 so we will not need to specify the job type. The

idea behind the mean value analysis is that the mean values for a network with w

jobs can be easily derived from a network with w −1 jobs; therefore, we will need

to reference the various mean values by the number of jobs within the network. For

example, CT

(w) will denote the mean cycle time at node k under the assumption

that the closed network (factory) contains w jobs.

The ﬁrst key relationship that is needed is the actual arrival rate into each work-

station. From Property 8.1, we know the relative arrival rates. In other words, if

(w) is the actual arrival rate to Workstation k when there are w jobs within the

network, then

(w)=x(w)r

, (8.1)

where x(w) is some (unknown) value dependent on the number of jobs in the system.

By Little’s Law this leads to

WIP

(w)=x(w)r

(w) .

Because the total WIPmust equal w, we s um over all workstations and solve for the

unknown “arrival rate” constant

x(w)=

∑

(w)

which when combined with Eq. (8.1) leads to the following property.

Property 8.2. Consider a closed network with n workstations containing

w jobs with the relative arrival rates to the workstations given by the n-

dimensioned vector r determined from Property 8.1. The arrival rate to Work-

station k is

(w)=

∑

j=1

(w)

The time spent within a workstation by a job equals the service time for that job

plus the time all jobs in front of that job must spend on the server. The key concept

that makes the mean value analysis possible was shown by Reiser and Lavenberg

[11]; that is, the average number of jobs in front of an arriving job for a factory

containing w jobs equals that workstation’s WIPfor a factory containing w −1 jobs.

Thus, the following relationship holds for Workstation k:

8.1 Closed Queueing Networks for Single Products 247

(w)=E[T

(k)] + E[T

(k)]WIP

(w −1) . (8.2)

Notice that some care needs to be taken in interpreting the parameters correctly.

Because the mean service time at a workstation does not depend on the number of

jobs within the network, t he parameter k within the expression E[T

(k)] refers to the

workstation number. However, the parameter for the cycle time and WIP refer to the

total number of jobs within the network. The ﬁrst term in Eq. (8.2) is the time for

processing the arriving job itself and the second term represents the processing time

for all jobs within the workstation, including the job in service, at the arrival time.

Using Little’s Law and Property 8.2,theWIP

(w −1) term in the above equa-

tion can be replaced by CT

(w −1) leading to the following Mean Value Analysis

Algorithm.

Property 8.3. Consider a closed network with n workstations containing

max

jobs. Each workstation has a single exponential server and the rela-

tive arrival rates to the workstations are given by the n-dimensioned vector r

determined from Property 8.1. The following algorithm can be used to obtain

the workstation mean cycle times.

1. Set CT

(1)=E[T

(k)] for k = 1,··· ,n and set w = 2.

2. Determine CT

(w) for k = 1, ··· ,nby

(w)=E[T

(k)] + E[T

(k)]

(w −1) r

(w −1)

∑

j =1

(w −1)

3. If w = w

max

, determine arrival rates from Property 8.2 and stop; otherwise,

increment w by 1 and return to Step 2.

Example 8.2. Consider the network given in Fig. 8.1. Let the mean processing times

at the three workstations be 12 minutes, 30 minutes, and 30 minutes, respectively.

In addition, 9/10 of the jobs leaving Workstation 3 are considered good and will be

shipped to customers while 1/10 of the jobs are scrapped. Management has decided

that the CONWIP level will be set to 5 jobs. The ﬁrst step of the mean value analysis

is to determine the relative arrival rates. As you recall, just before the statement of

Property 8.1, we showed that

= 1/hr , r

= 0.9/hr .

The steps of the algorithm yield Table 8.1 for the cycle time values at the various

WIP levels, where all values are in hours. Once the cycle time values are obtained,

the other standard workstation characteristics can be derived from Property 8.2 and

Little’s Law yielding Table 8.2.

Notice that each utilization factors is less than 1; this will always be the case

because the service rate serves as the upper limit to the throughput for each work-

station, and the utilization factor equals the arrival rate (throughput rate) times the

248 8 WIP Limiting Control Strategies

Table 8.1 Mean cycle time results (in hours) for Example 8.2

Iteration CT

(w) CT

(w)

∑

(w)

w = 1 0.200 0.500 0.500 1.150

w = 2 0.235 0.717 0.696 1.578

w = 3 0.260 0.955 0.897 2.021

w = 4 0.277 1.208 1.099 2.475

w = 5 0.290 1.477 1.299 2.936

Table 8.2 Workstation characteristics for Example 8.2 at a CONWIP level of 5

Measure Workstation 1 Workstation 2 Workstation 3

(5) 0.290 hr 1.477 hr 1.299 hr

(5) 1.703/hr 1.703/hr 1.533/hr

WIP

(5) 0.493 2.515 1.992

(5) 0.341 0.852 0.767

service time. More generally, the utilization factor is the arrival rate times the mean

service time divided by the number of machines at the workstation; that is,

(w)=

(w)E[T

(k)]/c

where c

is the number of machines at Workstation k. Since 90% of the output from

Workstation 3 is considered good, the throughput rate of this factory is 90% of the

throughput rate of Workstation 3; thus, the mean number of jobs shipped from this

factory is

= 0.9 ×1.533 = 1.38/hr .

Since the WIP level is always 5 for this example, the system mean cycle time is

given by

max

1.38

= 3.62 hr .



• Suggestion: Do Problems 8.3, 8.4, 8.5 (a,b,c), 8.6 (a,b), and 8.7 (a,b).

8.1.1.2 Multi-Server Systems

The algorithm for the multi-server case will require evaluation of the marginal prob-

abilities associated with each workstation and is called a Marginal Distribution

Analysis. (The probabilities are marginal in that they refer to the number of jobs

within a speciﬁc workstation and not the joint probability of the number of jobs in

different workstations at the same time.) As long as the processing times at each

workstation are exponential, the analysis will yield the correct mean values. It is

very similar to the Mean Value Analysis in that the cycle time calculations for a net-

work with a CONWIP level set to w individual jobs depends on the values calculated

for a network with a CONWIP level of w −1 j obs; however, the major difference

8.1 Closed Queueing Networks for Single Products 249

is that the marginal probabilities must be calculated ﬁrst. These probabilities when

there are w jobs within the network will be denoted by p

( j; w) for j = 0,··· , w

where the subscript k refers to the workstation number. Then the cycle time for w

jobs in the network will be expressed in terms of the marginal probabilities for a

network with w −1 jobs.

If Workstation k has c

servers and each server has a mean service time of

E[T

(k)], then the rate of service for the workstation with j jobs within it is equal to

min{j,c

}/E[T

(k)]. The key to obtaining an expression for the marginal probabili-

ties is to observe that the rate of arrival into Workstation k containing j jobs with a

total network population ﬁxed at w jobs equals

(w) p

( j −1; w −1) and the rate

of leaving that node is min{j,c

( j; w)/E[T

(k)] (see [2, p. 373]). Equating these

two probabilities using a similar approach to the rate balancing method of Sect. 3.2

yields an iterative expression for the probabilities and cycle times. The resulting

Marginal Distribution Analysis Algorithm of the following property is similar to

the algorithm contained in Buzacott and Shanthikumar [2, pp. 373–374].

Property 8.4. Consider a closed network with n workstations containing

max

jobs. Workstation k has c

servers with exponential processing time hav-

ing a mean of E[T

(k)]. The relative arrival rates to the workstations are given

by the n-dimensioned vector r determined from Property 8.1. The following

algorithm can be used to obtain the workstation mean cycle times.

1. Set p

(0;0)=1 for k = 1,··· ,n, and set w = 1.

2. Determine CT

(w) for k = 1, ··· ,nby

(w)=E[T

(k)]

w−1

∑

j=0

j + 1

min{j + 1, c

}

( j;w −1) .

3. Deﬁne the workstation arrival rates, for k = 1,··· ,n, by

(w)=

∑

i=1

(w)

If w = w

max

, s top; otherwise, proceed to the next step.

4. Determine p

( j; w) for k = 1,··· ,n and j = 1, ··· ,wby

( j; w)=

(w)E[T

(k)]

min{j, c

}

( j −1; w −1) .

5. Set p

(0;w)=1−

∑

j=1

( j; w) for k = 1,··· ,n.

6. Increment w by 1 and return to Step 2.

Since the mean cycle time of a workstation does not require the marginal prob-

abilities of other workstations, the two algorithms can be used together. In other

250 8 WIP Limiting Control Strategies

words, if some workstations have only one server, the easier algorithm of Prop-

erty 8.3 can be used for those workstations while the algorithm of Property 8.4 is

used for those workstations with multi-servers.

Example 8.3. We shall increase the capacity of the factory used in Example 8.2

(from Fig. 8.1) by adding two machines to Workstation 2 and adding one machine

to Workstation 3; thus, we have c

= 1, c

= 3, and c

= 2. All other characteris-

tics will stay the same. Although Workstation 1 has only one server, we shall used

the Marginal Distribution Analysis Algorithm to demonstrate is equivalence to the

Mean Value Analysis Algorithm. Both algorithms give the same value for w = 1

since the mean cycle time must equal the mean service time if only one job is in the

network; thus,

(1)=0.2hr, CT

(1)=0.5hr, CT

(1)=0.5hr.

Recall that r =(1, 1,0.9) so that

∑

k=1

(1)=1.15 and thus the arrival rates to

the stations are

(1)=0.8696/hr,

(1)=0.7826/hr .

The main extra work necessitated by the multiple servers is the calculation of the

marginal probabilities. From Step 4 of the algorithm, we have

(1;1)=0.1739/hr, p

(1;1)=0.4348/hr, p

(1;1)=0.3913/hr ,

andfromStep5,wehave

(0;1)=0.8261/hr, p

(0;1)=0.5652/hr, p

(0;1)=0.6087/hr .

The next iteration begins with w = 2. The calculations for cycle time yield

(2)=0.2348 hr, CT

(2)=0.5hr, CT

(2)=0.5hr.

Notice that with two jobs being maintained in the system, the cycle time in the sec-

ond and third workstations is the same as when the CONWIP level was set to one.

Because there are at most two jobs in system, there cannot be a queue at Worksta-

tions 2 and 3 due to the number of servers at these workstations. Using the same

logic, we would expect the mean cycle time at the second station to remain a 0.5 hr

with a CONWIP level of 3 since there are three separate processors at the second

workstation.

The sum after the second iteration is

∑

k=1

(2)=1.1848 so that the arrival

rates to the stations are

(2)=1.6881/hr,

(2)=1.5193/hr .

Each time the number of jobs within the factory increases, the number of calcula-

tions for the marginal probabilities also increase. The probability calculations are

shown in Table 8.3.

8.1 Closed Queueing Networks for Single Products 251

Table 8.3 Marginal probabilities for w = 2inExample8.3

Workstation 1 Workstation 2 Workstation 3

(1;2) 0.2789 0.4771 0.4624

(2;2) 0.0587 0.1835 0.1486

(0;2) 0.6624 0.3394 0.3890

The next iteration begins with w = 3. The calculations for cycle time yield

(3)=0.2793 hr, CT

(3)=0.5hr, CT

(3)=0.5372 hr .

The sum is

∑

k=1

(3)=1.2627 so that the arrival rates to the stations are

(3)=2.3758/hr,

(3)=2.1382/hr .

Notice that the numerical value for CT

(3) is the same whether the algorithm of

Property 8.4 or 8.3 is used, as long as the values for CT

(3) and CT

(3) come from

Property 8.4. However, it does serve to check for numerical carelessness, so we will

continue calculating the probabilities associated with Workstation 1. The probability

calculations are shown in Table 8.4.

Table 8.4 Marginal probabilities for w = 3inExample8.3

Workstation 1 Workstation 2 Workstation 3

(1;3) 0.3147 0.4032 0.4159

(2;3) 0.1325 0.2834 0.2472

(3;3) 0.0279 0.0727 0.0794

(0;3) 0.5248 0.2407 0.2575

The next iteration begins with w = 4. The calculations for cycle time yield

(4)=0.3327 hr, CT

(4)=0.5121 hr, CT

(4)=0.6015 hr .

The sum is

∑

k=1

(4)=1.3862 so that the arrival rates to the stations are

(4)=2.8856/hr,

(4)=2.5971/hr .

The ﬁnal probability calculations are shown in Table 8.5.

Table 8.5 Marginal probabilities for w = 4inExample8.3

Workstation 1 Workstation 2 Workstation 3

(1;4) 0.3029 0.3474 0.3344

(2;4) 0.1816 0.2909 0.2700

(3;4) 0.0765 0.1363 0.1605

(4;4) 0.0161 0.0349 0.0516

(0;4) 0.4229 0.1905 0.1835

252 8 WIP Limiting Control Strategies

Since our factory has a CONWIP level set at w

max

= 5, the ﬁnal iteration involves

only the ﬁrst three steps of the algorithm. Then after the ﬁnal cycle times and arrival

rates are calculated, Little’s Law can be used to obtain the workstation average WIP

levels. These ﬁnal results are contained in Table 8.6.

Table 8.6 Workstation characteristics for Example 8.3

Workstation 1 Workstation 2 Workstation 3

(5) 0.392 hr 0.534 hr 0.686 hr

(5) 3.238/hr 3.238/hr 2.914/hr

WIP

(5) 1.269 1.730 2.000

(5) 0.648 0.540 0.729

The rate at which jobs can be shipped out of this system is

= 0.9 ×2.914 = 2.62/hr ;

thus, the extra machines produced an increase of almost 90% in output. Notice also

for both Example 8.2 and 8.3, the workstation WIP values sum to the CONWIP

level, which is another convenient check on the numerical accuracy of data entries.

At the CONWIP level of 5, the mean cycle time through for the manufacturing

process is

2.62

= 1.91 hr .



• Suggestion: Do Problems 8.6 (c), 8.7 (c), 8.8, and 8.9.

8.1.2 Analysis with General Processing Times

The Mean Value Analysis Algorithm (Property 8.3) is based on the fact that when

a job arrives to a workstation within a closed network containing w total jobs, the

average number of jobs ahead of the arriving j ob will equal the average WIP of

that workstation for a closed network containing w −1 jobs. This fact is based on

the exponential assumption, so that for networks containing workstations that have

non-exponential processing times, an iterative method like t he Mean Value Analysis

Algorithm is no longer exact. Another aspect of the move from exponential service

times to general distributions for service is that we need to consider the remaining

processing time for the job in service at the point in time when an arrival occurs. Pre-

viously the remaining service time was not considered because of lack of memory

of the exponential distribution (see the discussion around Eq. 1.16).

As an approximation, we shall continue to assume that an arriving job sees the

number of jobs ahead of it based on a network with one less job. Another impor-

tant assumption that is possible with exponential processing times is its memoryless