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

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

7.4 Modeling the Workstation Following a Batch Server 213

7.4 Modeling the Workstation Following a Batch Server

Since the unbatching process after a batch-service workstation does not produce

a renewal process (i.e., a stream of inter-departure times that are independent and

identically distributed), it is prudent to model the recipient workstation as having a

batch arrival process. This approach captures the true behavior of the arrival stream

including the inter-dependence between arrivals, whereas the i.i.d. SCV approxima-

tion does not. The analysis of the workstation depends on whether the jobs leaving

the batch processor are sent directly to the next workstation or if a probabilistic

branch follows the batch server.

7.4.1 A Serial System Topology

To illustrate the difﬁculties inherent in modeling the workstation following a batch

service operation, reconsider Example 7.3 and assume that the workstation of that

example feeds into a workstation that processes jobs one-at-a-time. This down-

stream workstation has a service process described by an exponential distribution

with a mean of 3 minutes. The workstation of Example 7.3 is feeding batches of

size 5 to our workstation at a mean rate of 3 batches per hour with an SCV of batch

inter-arrival times of 0.75 and an SCV of 7.75 of individuals. The workstation uti-

lization factor is u = 5 ×3 ×0.05 = 0.75. Then using the standard approximation

for individuals, the system cycle time for this workstation is

CT =

7.75 + 1

0.75

1 −0.75

×0.05 + 0.05 = 0.706 hr . (7.14)

Simulating this situation yielded a cycle time estimate of 0.496 hours based on

just over 135,000 simulated services. The resultant inter-arrival stream characteris-

tics were measured as E[T

(I)] = 0 .333, with C

(B)] = 0.753. The workstation

utilization factor was measured to be 0.749. This data was from a simulation run

length of 10,000 hours with a statistics reset after 1,000 hours. So even though the

ﬁrst two moments of the inter-arrival time distribution were very accurate, the cycle

time approximation was off by 42%. Why? The answer is in the arrival stream’s

characteristics. The ﬁrst two moments of the inter-arrival time distribution does not

capture the grouping behavior observed in the batch arrival process. For example, it

is quite possible to have an arrival stream sequence of batches of size 2 with exactly

the same mean and SCV; thus, it is clear that the ﬁrst two moments alone cannot

adequately describe an arrival process of individuals that arise from batches.

To properly take the arrival stream’s characteristics into account, the next work-

station after the batch server workstation should be modeled as a batch arrival sta-

tion, using the modeling approach detailed in Sect. 7.1 dealing with batch moves,

speciﬁcally, Property 7.2 should be used. This approach treats the system as a batch

arrival and batch server system for the queue time estimate and then adds the in-

214 7 Models of Various Forms of Batching

dividual unit’s service time plus the extra waiting time due to each unit waiting its

turn for processing within the batch.

The cycle time given by Eq. (7.14) can be re-calculated using Property 7.2 as

follows:

CT =

5 ×0.75 + 1

0.75

1 −0.75

×0.05 +

5 + 1

×0.05 = 0.506 hr .

This result differs by 2% from the simulated value. Thus, the batch modeling ap-

proach is much closer to the observed cycle time since this model has inherent in it

the behavior of items arriving for service from the batch server workstation.

7.4.2 Branching Following a Batch Server

From previous discussion (Sect. 7.4.1), we know that the proper method of modeling

a workstation following a batch service process is to treat the output process as a

batch move. Thus, units coming out of the batch server move to the next workstation

in a fashion identical to the batch move model (Sect. 7.1). The question arises as to

the appropriate modeling method if the departures from the batch server follow a

probabilistic branch that separates individual items and distributes them to different

workstations.

Consider for illustration purposes a batch server (Workstation 1) with a batch

size of 4. Let p be the probability that an individual item from a batch goes next

to Workstation 2 and let q = 1 − p be the probability that an individual job goes

to Workstation 3. Consider further a batch that is just exiting the batch server and

the batch is immediately broken into individual items that are randomly branched to

either Workstation 2 or Workstation 3, with random variables N

and N

denoting

the number of jobs sent to the two workstations. Thus, N

∈{0, 1,2,3, 4} and N

4 −N

. If Workstation 2 receives 1 job then Workstation 3 receives 3 jobs from

this batch. In other words, the workstations receiving output from a batch service

operation followed by a probabilistic split see random sized batches. Figure 7.2

illustrates this idea with items being represented by small circles stacked on one

another to indicate that they arrived at the same time.

A speciﬁc batch (of size 4) split between the two workstations can take any of the

conﬁgurations shown i n Table 7.2. So in essence, each workstation sees a binomial

distribution of random batch sizes (refer to p. 14), in this example ranging from 1

to 4. Note that a zero batch size means that no arrival occurs for at least one more

batch service.

The modeling approach is again to treat the arrival pattern as batches but now

of random sizes, N ∈{1,2,···,k}. However, because the workstation accepting the

batches does not “see” batches of size zero, the distribution of batches sizes must be

a conditional binomial distribution given that the random variable is not zero. Thus,

the probability density function for the random batch size N is

7.4 Modeling the Workstation Following a Batch Server 215

Batch Server

Single Unit Servers

Fig. 7.2 Illustration of a batch service followed by individual (random) branching to subsequent

workstations, where stacked jobs denote batches with a size equal to the number of stacked items

Table 7.2 Distribution of batch sizes to the workstations

Probability WS 2 WS 3 Probability





o ooo









oo oo









ooo o









oooo









oooo





Pr{N = n} = p





k−n

(1 −q

)

for n = 1, ··· ,k , (7.15)

where k is the ﬁxed processing batch size and q = 1 −p. The mean and SCV for this

conditional binomial distribution are not too difﬁcult to determine and are given by

E[N]=

1 −q

and (7.16)

[N]=



1 −kq

k−1

+(k −1)q



. (7.17)

As with ﬁxed batch sizes, the cycle time model is separated into the cycle time in

the queue for batches (working their way up to the server) and the average service

delay for individuals within the batch. The service delay consists of the item’s ser-

vice time T

plus the service time of all items in the batch that are processed before

this speciﬁc individual. These times need to be averaged over all possible positions

for items within the batch. These two components are addressed individually.

216 7 Models of Various Forms of Batching

7.4.2.1 Cycle Time in the Queue for Random Sized Batches

A queued batch can be viewed as seeing batches ahead of it being served as a whole

even though the service mechanism operates on individual items taken from a batch.

The expected delay time is computed for a batch to move up in the ﬁrst-come-ﬁrst-

serve queue until it (any of its items) becomes the batch being served. (This is the

same model form used for the Batch Move Model of Sect. 7.1). The service time

for each batch is a random sum of i.i.d. random variables which was described

in Sect. 1.6.2. Thus, the measures for the batch service time are obtained through

Property 1.9 and are given as

E[T

(B)] = E[N]E[T

(I)] and

(B)] = C

[N]+

(I)]

E[ N]

, (7.18)

where N is the random variable denoting the batch size (Eq. 7.15).

The arrival rate of individual items at the workstation following a batch service

with branching probability p is a function of the arrival rate of individuals into

the batch service workstation. For notational clariﬁcation denote the batch server

workstation as #1 and the recipient workstation as #2. Let

(I) be the arrival rate of

individuals i nto the batch workstation and let

(I) be the arrival rate of individuals

into #2 after the branch. Then the relationship between these rates is

(I)=p

(I) . (7.19)

However, the batch arrival rate is not quite as straight forward because of the pos-

sibility that a batch is of size zero. Assume that #1 operates on batches of size k,

then the probability that a batch of size zero is “sent” to #2 is q

where q = 1 − p.

Therefore, the probability that a batch of size greater than zero departs from #1 is

1 −q

so that the batch arrival rate to #2 is given by

(B)=



1 −q



(I)

, (7.20)

and the expected batch size is given by Eq. (7.16).

The squared coefﬁcient of variation of the inter-arrival time into #2 is related

to the squared coefﬁcient of variation of the inter-departure time for #1. Since the

departures are in terms of batches, the batch inter-arrival time’s squared coefﬁcient

of variation into #2 is

(2)] = (1 −q

(1)] + q

, (7.21)

where the subscript B is used to indicate that the C

is for batches. Recall that the

factor q

is the probability that no units from the batch are directed to #2.

Using the standard Kingman approximation, the cycle time in the queue, CT

,for

the batches is given as

7.4 Modeling the Workstation Following a Batch Server 217

(2)=



(2)] +C

(B)]



1 −u



E[T

(B)] (7.22)



(2)] +C

[N]+C

(I)]/E[N]



1 −u



E[N]E[T

(I)] ,

where the utilization factor is computed by u

(I)E[T

(I)].

• Suggestion: Do Problem 7.13.

7.4.2.2 Average Service Delay Times for Random Sized Batches

Once a batch has worked its way through the batch queue and ﬁnally has command

of the server, the server will be busy for the speciﬁc number of service times equal

to the number of items in the batch. The delay time associated with individual items

within the batch varies since processed items leave the workstation immediately

upon completion of their turn i n the server. Thus, an average delay is computed by

taking into account the delay associated with each position, with respect to the order

that items are served, within the batch. This average delay has two components,

the service time of the individual and the average delay waiting for other items

positioned ahead of that individual unit in the batch.

We follow the same logic here that was used in Sect. 7.1.3. The random vari-

able D represents the total delay experienced by all jobs within a batch; thus from

Eq. (7.5), it follows that

E[D|N = n]=

n(n −1)

E[ T

(I)] ,

where the random variable N is the size of the batch. Since E[E[D|N]] = E[D] (see

Property 1.8), the service time delay, st, is obtained as follows

st =

E[D]

E[N]

+ E[T

(I)] =

E[ N(N −1)]

2E[N]

E[T

(I)] + E[T

(I)] (7.23)

E[N(N + 1)]

2E[N]

E[T

(I)] =

E[N

] −E[N]

+ E[N]

2E[N]

E[ T

(I)]



E[N]+1

V [N]

2E[N]



E[ T

(I)] =



1 + E[N]+E[N]C

[N]



E[T

(I)] .

Notice that for deterministic batches, Eq. (7.23) is identical to Eq. (7.6).

218 7 Models of Various Forms of Batching

7.4.2.3 Cycle Time in the Workstation for Random Sized Batches

The cycle time in a workstation that directly follows a batch server and receives

only a proportion of the individual items can be obtained by combining the two

major pieces of the previous two sections yielding the following property.

Property 7.8. Consider a workstation that processes items one-at-a-time with

a mean and SCV of the (individual) processing time given by E[T

] and C

Jobs arrive to the workstation in batches of random size denoted by N. The

times between batch arrivals have a mean and SCV of E[T

(B)] and C

]

yielding a mean batch arrival rate of

(B)=1/E[T

(B)]. The mean system

cycle time per item at the workstation is approximated by



E[ N]C

]+E[N]C

[N]+C



1 −u



E[ T

]



1 + E[N]+E[N]C

[N]



E[ T

]

where the utilization factor is u = E[N]

(B)E[T

Example 7.4. Consider a workstation that processes 5 units simultaneously (k = 5).

Let the departure rate from this batch workstation be 3 batches per hour with a

squared coefﬁcient of variation of the inter-departure times of 0.75. After the batch

leaves the workstation, it is broken into individual units and each item has a 25%

chance of being sent to the second workstation. The second workstation processes

items one-at-a-time according to an exponential distribution with mean of 12 min-

utes. We would like to analyze the second workstation.

The probability of #2 not receiving any units from a particular batch that ﬁnished

processing at #1 is 0.75

= 0.2373. Thus, the arrival rate of of batches (of any size)

to #2 is

(B)=3(1 −0.2373)=2.288 per hour (see Eq. 7.20), or equivalently,

E[T

(B)] = 0.437 hours. Note that the arriving batch can be of any size from 1 to

5 units depending on the probabilistic results from individual unit branching. The

mean and SCV for the batch size (Eqs. 7.16 and 7.17)areE[N]=1.639 and C

[N]=

0.220. The mean batch size (1.639) together with the batch arrival rate (2.288/hr)

and the mean service time (0.2 hr) results in a utilization factor of u = 0.75.

The arrival rate of individual units is the average batch size (1.639) times the

batch arrival rate (2.288/hr) yielding 3.75/hr which is also equal to the branch prob-

ability (0.25) times the individual departure rate from the ﬁrst workstation. The

SCV of the inter-arrival times of batches is determined from the departure process

according to Eq. (7.21):

]=(1 −0.2373)0.75 + 0.2373 = 0.809.

7.4 Modeling the Workstation Following a Batch Server 219

Property 7.8 can now be used to determine the average time spent within the

workstation for an arbitrary job:

CT =



1.639 ×0.809 + 1.639 ×0.220 + 1



0.25

1 −0.25



0.2



1 + 1.639 + 1.639 ×0.220



0.2 = 1.106 hr .

The approximations agree quite well with simulated results for this system. Ta-

ble 7.3 contrasts several of these computations with the measured results from a

simulation study. The simulation study consists of the 20 replications of individual

simulations 10,000 hours in length, with a statistical reset at 1,000 hours. Each repli-

cation results in 20,600 to 20,700 processed batches (or more than 400,000 batches).



Table 7.3 Comparison of analytical approximation and simulation results for Example 7.4

E[T

(B)] C

] E[T

(B)] C

(B)] CT

Analytical Mean 0.437 0.809 0.300 0.830 0.806 1.106

Simulated Mean 0.437 0.813 0.301 0.835 0.805 1.106

Simulated Std.Dev. 0.003 0.011 0.002 0.009 0.044 0.045

The conclusion is that this model is the appropriate method for modeling t he

downstream server from a batch workstation with individual unit branching to the

next workstation. This approach is considerably better than using an i.i.d. coefﬁ-

cient of variation formula to compute the individual inter-arrival time parameters

and then applying a model for individual cycle times. The down side of this ap-

proach is that it is harder to incorporate into a network model because of the more

complex connections between workstations and if the workstation has multiple in-

ﬂows the blending of the streams becomes considerably more complicated.

• Suggestion: Do Problems 7.7 and 7.8.

7.4.2.4 Arrival SCV of Individuals after a Random Branch

If it is necessary to compute the squared coefﬁcient of variation of the arrival stream

of individuals coming from a batch service process, then the best one can do is

an i.i.d. approximation for the SCV. This treatment considers all the individuals

as independent arrivals and merely computes the associated SCV of the individual

inter-arrival times.

To effect this computation, we repeat Eq. (7.21) from Sect. 7.4.2.1 that gives t he

relationship between departing batches from one workstation to arriving batches to

the next workstation:

220 7 Models of Various Forms of Batching

(2)] = (1 −q

(1)] + q

where p is the branching probability with q = 1 − p. Equation (7.13) gives the con-

version from a batch to individual jobs, so by taking a weighted average of the

squared coefﬁcients of variation, we have

(2)] = E[N]C

(2)] + E[N] −1 ,

where N is the random variable of the resulting batch size after the probabilis-

tic branching with distribution given by Eq. (7.15). Using the mean value from

Eq. (7.16), the SCV of the inter-arrival times of individually arriving jobs is cal-

culated as

(2)] =



(1 −q

(1)] + q

+ 1



1 −q

−1 , (7.24)

where k is the batch size of the departing batches from the ﬁrst workstation before

branching occurs.

Note that a better approximation occurs if a single unit processing workstation

that follows a batch server is modeled using the Batch Move Model that resulted in

Property 7.8. Equation 7.24 is given f or the situation where it is difﬁcult t o model

the next workstation with the batch move approach and/or there are several sources

of inﬂow into this workstation that must be combined.

Example 7.5. To illustrate obtaining the inter-arrival time SCV for individuals ran-

domly branched to a workstation from a batch service workstation, consider that

the batch workstation has an SCV for inter-departure times of batches given as

(1)] = 0.8, and let the branching probability be 1/2 for individual units from

batches of size 4. Then q

= 0.5

= 0.0625 and

(2)] =

4(1/2)[0.9375(0.8)+0.0625 + 1]

0.9375

−1 = 2.8667.

This agrees quite well with the simulated result of 2.87. 

7.4.2.5 Departures from the Workstation Following Batch Service

The mean and squared coefﬁcient of variation of an arrival process sometimes does

not adequately capture the arrival stream’s characteristics from an accurate model-

ing prospective. This is particularly true for batch arrival streams. The batch process

cycle time is relatively easy to characterize but the output process from the batch ser-

vice workstation cannot be adequately characterized with only the mean and SCV

parameters. The batch arrival phenomenon to a single unit service workstation re-

quires a separate model (the Batch Move Model of Sect. 7.1), and the random batch

size extension given in Property 7.8. Individual units depart these workstations and

merge with other inﬂow streams to subsequent workstations. So the question of an

adequate model for approximating the outﬂow or departure stream of individuals

7.4 Modeling the Workstation Following a Batch Server 221

needs to be addressed. Curry and Deuermeyer [3] show that a simple extension

to Property 7.3 yields a relatively accurate approximation for a workstation down-

stream from a batch processor that has probabilistic branches.

Property 7.9. Consider a workstation with batch arrivals that processes items

one-at-a-time. Using the same notation as in Property 7.8, the squared coef-

ﬁcient of variation of the inter-departures of individuals from the workstation

is approximated by

(I)=(1 −u

)E[N]C

]+(E[N] −1)(1 −u)

+ u

Example 7.6. We return to Example 7.4 and determine the characteristics of the de-

parture process from the second workstation (i.e., the workstation that was accepting

25% of the items departing from the batch processor). The batch size characteristics

were computed to be E[N]=1.639 and C

[N]=0.220 and the batch arrival rate was

determined to be

(B)=2.288/hr. Therefore the individual arrival rate and thus the

departure rate of items from the workstation is 1.639×2.288 = 3.75/hr which yields

E[ T

(I)] = 16 min .

We also have from Example 7.4 that the SCV for the batch arrival process to the

workstation was 0.8093; therefore the SCV of the inter-departure times of individual

items from the workstation is

(I)=1.639(1 −0.75

)0.8093 +(1.639−1)(0.25)

+ 0.75

(1)=1.183 .



In a simulation study of the departures from this random batch arrival system

with individual service, a set of 13 simulations with random batch sizes resulting

from a service batch of size 5, a 25% change of individuals being routed to the

workstation being studied and, C

(B) and C

(I) both ranged over 3/4, 1, and 3/2.

Each of these simulations consisted of 100,000 simulated hours. The average abso-

lute error between the theoretical estimate and the simulation estimate for C

(I) for

these 13 studies was 1.80% with a maximum error of 3.03%. Although this study

also was not over the whole range of values for utilization, and inter-arrival and ser-

vice time SCV’s, it does indicate that the i.i.d. approximation given in Property 7.9

for the SCV of departures is a viable approach for modeling purposes.

• Suggestion: Do Problem 7.11(a).

222 7 Models of Various Forms of Batching

7.5 Batch Network Examples

Modeling the ﬂow of jobs within a factory in which batching occurs can compli-

cate the methodology considerably. To help in incorporating batches within your

models, we devote this ﬁnal section to the analysis of two different factories with

batching. The ﬁrst example includes all three major batch types and without any

feedback paths. The second example includes a more complex branching structure

that has reentrant ﬂows. The main concept that is demonstrated with these examples

is that the formulas from the various properties cannot be blindly applied — they

often must be adjusted slightly to ﬁt different situations. However, the bottom line

is that systems with batching can be reasonably well analyzed if the various models

discussed in this chapter are used wisely.

7.5.1 Batch Network Example 1

Consider Fig. 7.3 that has three workstations each of which operates using a differ-

ent form of the batch service models studied in this chapter. The ﬁrst workstation is

a setup-batch processing workstation, the second workstation uses oven-batch pro-

cessing, and the third workstation is a single unit server with batch arrivals (the

batch move model). Inﬂow into the system is in terms of individual units with a

Poisson arrival rate with a mean of 5 units per hour. These individuals are imme-

diately batched into groups of k = 3 and transported into the ﬁrst workstation. The

batch forming time in this analysis will be added to the cycle time for Workstation

1. The data for each particular workstation is given as it is needed in the solution

process.

Note in Fig. 7.3 that once batches are formed, they remain batches until they ei-

ther exit the system following processing at Workstation 2 or they make it to Work-

station 3. The jobs are large and require a forklift for transportation between work-

stations, thus all probabilistic branches are made on batches and not individual jobs.

Speciﬁcally, 2/3 of the batches leaving Workstation 1 are routed to Workstation 2

and 1/3 go to Workstation 3. From Workstation 2, 1/4 of the batches are ﬁnished

(leave the system) and the remaining 3/4 are routed to Workstation 3. At Worksta-

tion 3, t he items are then separated once the batch enters service and, subsequently,

they leave as individuals. The goal of this analysis is to obtain the expected cycle

time and throughput rate for the system as a whole.

Workstation 1 Including Batch Forming Time

The arrival rate of individuals to the ﬁrst workstation is according to a Poisson pro-

cess with a mean rate of 5 per hour. The average batch forming time, BT ,tobe

associated with each individual item is determined by the equation