Curry G.L., Feldman R.M. Manufacturing Systems Modeling and Analysis
Подождите немного. Документ загружается.
9.3 Example of a Kanban Serial System 303
machine to Subsystem 2 is in Phase 1 (and not blocked) equals 0.7906 and the proba-
bility that the arrival-machine is in Phase 2 (and not blocked) is 0.0362. In addition,
the probability that an arrival enters the subsystem from Phase 1 of the arrival-
machine is 91.22% (namely, 1 − p
2
), and enters f rom Phase 2 is 8.78% (namely,
p
2
); thus, the probability that an arrival to Subsystem 2 will find the subsystem full
with the service-machine in Phase 1 is given by
p
(1,F)
a,2
= 0.9122 ×
0.1800
0.7906
+ 0.0878 ×
0.0054
0.0362
= 0.2208 ,
and the probability that an arrival to Subsystem 2 will find the subsystem full with
the service-machine in Phase 2 is given by
p
(2,F)
a,2
= 0.9122 ×
0.0031
0.7906
+ 0.0878 ×
0.0001
0.0362
= 0.0038 .
Finally, the throughput rate is the arrival rate times the probability that the system
is not blocked, or
th(2)=0.6959 ×(1 −0.1687 −0.0044)=0.5754/hr .
Summary: The backwards pass for penultimate subsystem (namely, Subsys-
tem (n −1)) always uses the MGE
2
distribution for the service-machine process;
thus, the mean and variance of service times can be given as
E[T
s
(n −1)] = t
n−1
+ p
F
a,n
t
n
and (9.13)
Var[T
s
(n −1)] = t
2
n−1
+ p
F
a,n
t
2
max
2 − p
F
a,n
,
where
t
n
denotes the mean service time of the final workstation and t
n−1
denotes the
mean service time of the penultimate workstation.
With the mean and SCV for the service-machine process determined, Eq. (9.1)
or (9.2) is used to obtain the parameters for the approximating GE
2
which are de-
noted by (
μ
n−1
,q
n−1
,
γ
n−1
). This distribution is combined with the GE
2
distribution
determined in the forward pass that is used for the arrival process. The parameters
for the arrival process were denoted by (
α
n−1
, p
n−1
,
β
n−1
). Thus, we have the data
needed to establish the steady-state probabilities of Subsystem (n −1). The form of
the generator matrix is similar to Fig. 9.7 with the steady-state probabilities coming
from Property 9.3. These probabilities are denoted by v
i
where i is a three-tuple. The
probability that an entry will find the system blocked while the service-machine is
in the first phase is
p
(1,F)
a,n−1
=(1 − p
n−1
)
v
(1,1,max)
v
(1,0,0)
+
∑
max
i=1
[v
(1,1,i)
+ v
(1,2,i)
]
(9.14)
+ p
n−1
v
(2,1,max)
v
(2,0,0)
+
∑
max
i=1
[v
(2,1,i)
+ v
(2,2,i)
]
,
304 9 Serial Limited Buffer Models
where p
n−1
is the parameter from the GE
2
distribution for the arrival-machine of the
penultimate subsystem. Similarly, the probability that an entry will find the system
blocked while the service-machine is in the second phase is
p
(2,F)
a,n−1
=(1 − p
n−1
)
v
(1,2,max)
v
(1,0,0)
+
∑
max
i=1
[v
(1,1,i)
+ v
(1,2,i)
]
(9.15)
+ p
n−1
v
(2,2,max)
v
(2,0,0)
+
∑
max
i=1
[v
(2,1,i)
+ v
(2,2,i)
]
.
(Notice that the phase index in the superscript of the blocking probabilities (Eqs. 9.14
and 9.15) refers to the phase of the service-machine; whereas, the index in the su-
perscript of the starving probabilities (Eqs. 9.7 and 9.8) refers to the phase of the
arrival-machine.)
From this point on, any subsystem except for the first and last subsystems will
have the full state space involving three tuples. Thus, the mean throughput rate, for
k = 2,··· ,n −1 is given by
th(k)=
1 −v
(b,1,max)
−v
(b,2,max)
E[T
a
(k)]
. (9.16)
9.3.2.3 Backward Pass for Subsystem 1
Note that there are three possibilities when a job has finished on the service-
machine: (1) the service-machine is not blocked (this has a probability of 77.54%),
in which case the service time will be exponential, (2) the service-machine is
blocked and the service-machine of Subsystem 2 is in Phase 1 (this has a proba-
bility 22.08%), in which case the service time for the next job will experience a
delay of according to a GE
2
distribution, and (3) the service-machine is blocked and
the service-machine of Subsystem 2 is in Phase 2 (this has a probability 0.38%), in
which case the service time for the next job will experience a delay of an additional
exponential time associated with the second phase of the GE
2
distribution. Thus, the
processing time distribution for the service-machine for Subsystem 1 is an MGE
3
process with generator matrix G
G =
⎡
⎣
−
μ
2
q
2
μ
2
(1 −q
2
)
μ
2
0 −
γ
2
γ
2
00 −1/t
1
⎤
⎦
=
⎡
⎣
−0.7524 0.0256 0.7268
0 −1.4792 1.4792
00−0.75
⎤
⎦
and with initial probabilities
α
α
α
=(0.2207,0.0038,0.7755). Notice that the first two
initial probabilities are p
(1,F)
a,2
and p
(2,F)
a,2
.ThisMGE
3
process has a mean time of
1.6344 hr and an SCV = 0.9325 (Property 9.2). Thus, the following parameter set
(
μ
1
,q
1
,
γ
1
)=(0.6562,0.1350,1.2238)
9.3 Example of a Kanban Serial System 305
will be used for the GE
2
distribution that approximates the service-machine of Sub-
system 1. Recall that for the first subsystem, the arrival-machine is never starved so
that its processing time distribution is exponential with mean 1 hr. We do not need to
determine the blocking probabilities, but an estimate for the throughput is needed;
therefore, we will calculate the steady-state probabilities.
The state space for this system will be slightly different from those we have had
so far an is given as
{(00),(11),(21),(12),(22),(13),(23),(14),(24),(1b),(2b)}.
The difference between this state space and the state space on Page 296 (other than
the larger buffer capacity) is that the first element of the ordered pair refers to the
phase of the service-machine instead of the arrival-machine; thus, there is only one
empty state and two blocked states instead of two empty states and one blocked
state.
To construct the generator matrix for the subsystem, it is best to look for a pattern
among 2 ×2 submatrices, except that the first row and column will be different. The
first few elements of the matrix are as follows and we leave it to the reader to finish
its construction:
Q =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
−1/
t
0
1/t
0
000···
(1 −q
1
)
μ
−(
μ
1
+ 1/t
0
) q
1
μ
1/t
0
0
γ
1
0 −(
γ
1
+ 1/t
0
) 01/t
0
0 (1 −q
1
)
μ
0 −(
μ
1
+ 1/t
0
) q
1
μ
0
γ
1
00−(
γ
1
+ 1/t
0
) ···
.
.
.
.
.
.
.
.
.
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
From Property 9.3, the steady-state probabilities for the subsystem can be found
as given in Table 9.5.
Table 9.5 Probabilities for Subsystem 1 — first backwards pass
Phase of Number of Jobs in System
Service-Machine 0 1 2 3 4 b
0 0.0329
1 0.0534 0.0882 0.1464 0.2432 0.3706
2 0.0021 0.0045 0.0078 0.0132 0.0376
These probabilities yield a mean throughput of
th(1)=1 ×(1 −0.3706 −0.0376)=0.5918/hr .
The throughput estimates for the three subsystems after this first iteration are have
been calculated to be 0.5918/hr, 0.5754/hr, and 0.5603/hr. (These are all from the
backward pass since they are the more recent estimates than the forward pass.) The
306 9 Serial Limited Buffer Models
algorithm is finished when all three throughputs are the same and do not change
with the iteration.
Summary: The update to the service-machine for Subsystem k involves forming
the MGE
3
distribution from the parameters determined during the backward pass of
Subsystem k + 1. The generator will have the form
G =
⎡
⎣
−
μ
k+1
q
k+1
μ
k+1
(1 −q
k+1
)
μ
k+1
0 −
γ
k+1
γ
k+1
00 −1/t
k
⎤
⎦
,
and with the initial probability vector given by
α
α
α
=
p
(1,F)
a,k+1
, p
(2,F)
a,k+1
,1 −p
(1,F)
a,k+1
− p
(2,F)
a,k+1
.
Again, it is possible to obtain closed form expressions of the application of Prop-
erty 9.2 to this generator. Thus, the mean and variance for the service-machine pro-
cessing time for Subsystem k are
E[T
s
(k)] = t
k
+
p
(1,F)
a,k+1
μ
k+1
+
π
γ
k+1
(9.17)
Var[T
a
(k)] = t
2
k
+
p
(1,F)
a,k+1
(2 −p
(1,F)
a,k+1
)
μ
2
k+1
+
π
(2 −
π
)
γ
2
k+1
+
2p
(1,F)
a,k+1
(q
k+1
−
π
)
μ
k+1
γ
k+1
,
where
π
= p
(1,F)
a,k+1
×q
k+1
+ p
(2,F)
a,k+1
. With the mean and SCV for the arrival process
determined, Eq. (9.1)or(9.2) is used to obtain the parameters for the approximat-
ing GE
2
which are denoted by (
μ
k
,q
k
,
γ
k
). Using this distribution together with the
exponential-arrival process with mean time
t
0
, the steady-state probabilities can be
obtained using a generator similar to the generator on Page 305.
The mean throughput rate is given by
th(1)=
1 −v
(1,b)
−v
(2,b)
t
0
. (9.18)
This completes one iteration of the algorithm. The iterations should be continued
until the throughput estimates do not change from one iteration to the next.
9.3 Example of a Kanban Serial System 307
9.3.3 The Remaining Iterations
Some of the procedures used in the first forward passes were different simply be-
cause the subsystems had not been analyzed before. In the following subsections we
indicate the adjustments that will have to be made for the remaining iterations.
9.3.3.1 The Remaining Forward Passes for Subsystem 1
The steady-state probabilities for Subsystem 1 were obtained on the previous back-
ward pass and the arrival-machine needs no updating since it can never be starved.
Because the service-machine is no longer exponential, the probability of a depart-
ing job leaving the system empty must be conditioned on the phase of the service-
machine from which the job departs; otherwise the probability would be the time-
averaged probability instead of a departure point probability. This is similar to the
logic used for Eq. (9.11) except the conditioning is on the service-machine instead
of the arrival-machine. Thus, the probability that a departure will leave the subsys-
tem empty is given as
p
0
d,1
=(1 −q
1
)
v
(1,1)
v
(b,1)
+
∑
max
i=1
v
(1,i)
(9.19)
+ q
1
v
(2,1)
v
(b,2)
+
∑
max
i=1
v
(2,i)
,
where q
1
is the parameter from the GE
2
distribution for the service-machine of
the Subsystem 1 and v
(b,i)
is the steady-state probability that the arrival is blocked
and the s ervice-machine is in Phase i. These quantities were determined during the
backward pass for the first subsystem.
9.3.3.2 The Remaining Forward Passes for Subsystem 2
The determination of the mean and variance for the inter-arrival times is the same
as the first forward pass; namely, use Eq. (9.6) and then determine new values for
(
α
2
, p
2
,
β
2
) based on the mean and SCV of the inter-arrival times. The generator
matrix is formed according to Fig. 9.8 (i.e., the state space is made up of three-
tuples) using the service-machine parameters saved from the previous backward
pass, and then Property 9.3 is used to obtain the steady-state probabilities.
Because the service-machine is no longer exponential, the probability of a depart-
ing job leaving the system empty must be conditioned on the phase of the service-
machine from which the job departs as was done for the first subsystem. Here a joint
probability is needed for the phase of the arrival-machine. Thus, the probability that
a departure will leave Subsystem k empty while the arrival-machine in Phase 1 is
308 9 Serial Limited Buffer Models
p
(1,0)
d,k
=(1 −q
k
)
v
(1,1,1)
v
(b,1,max)
+
∑
max
i=1
[v
(1,1,i)
+ v
(2,1,i)
]
(9.20)
+ q
k
v
(1,2,1)
v
(b,2,max)
+
∑
max
i=1
[v
(1,2,i)
+ v
(2,2,i)
]
,
where q
k
is the parameter from the GE
2
distribution for the service-machine of
Subsystem k with k = 2, ··· ,n −1. The probability that a departure will leave Sub-
system k empty with the arrival-machine in Phase 2 is
p
(2,0)
d,k
=(1 −q
k
)
v
(2,1,1)
v
(b,1,max)
+
∑
max
i=1
[v
(1,1,i)
+ v
(2,1,i)
]
(9.21)
+ q
k
v
(2,2,1)
v
(b,2,max)
+
∑
max
i=1
[v
(1,2,i)
+ v
(2,2,i)
]
.
9.3.3.3 The Remaining Forward and Backward Passes
The forward pass for the final subsystem and all the backward passes remain the
same as during the first iteration. Recall that one iteration includes both the forward
and backward passes. Once the throughputs converge, the decomposition algorithm
is finished.
9.3.4 Convergence and Factory Performance Measures
The changing values of throughput by iteration are shown in Table 9.6 and it is
seen that five iterations are sufficient for convergence. The throughput values in the
Table 9.6 Throughput results from the first five iterations
Subsystem 1 Subsystem 2 Subsystem 3
Iteration 1 0.5916/hr 0.5754/hr 0.5602/hr
Iteration 2 0.5831/hr 0.5820/hr 0.5798/hr
Iteration 3 0.5824/hr 0.5823/hr 0.5821/hr
Iteration 4 0.5823/hr 0.5823/hr 0.5823/hr
Iteration 5 0.5823/hr 0.5823/hr 0.5823/hr
table are from the backwards pass. The values calculated from t he forward pass are
ignored.
The performance measures for each workstation and the system as a whole are
computed from the throughput rate and the steady-state probabilities for each sub-
system as representative of the associated workstation. Notice that the throughputs
are the same for each subsystem ( 0.5823/hr for our example) if convergence has
taken place, but of course, the steady-state probabilities are different. To illustrate,
9.3 Example of a Kanban Serial System 309
consider Table 9.7 that shows the steady-state probabilities for Subsystem 1 as deter-
mined by the final backwards pass. The l ast row of the table gives the probabilities
Table 9.7 Probabilities for Subsystem 1 — fifth backwards pass
Phase of Number of Jobs in System
Service-Machine 0 1 2 3 4 b
0 0.0303
1 0.0501 0.0846 0.1434 0.2434 0.3745
2 0.0023 0.0048 0.0086 0.0148 0.0432
Sum 0.0303 0.0524 0.0894 0.1520 0.6759 —
for the number of jobs in the subsystem. Notice that the probability of 4 jobs in the
subsystem is the sum for the last two columns since the system contains 4 jobs when
it is blocked. Thus the average number of jobs in the system is
WIP(1)=1 ×0.0524 + 2 ×0.0894 + 3 ×0.1520 + 4 ×0.6759 = 3.391 ,
and the cycle time (from Little’s Law) is
CT(1)=
WIP(1)
th(1)
=
3.391
0.5823
= 5.823 hr .
The system WIP
s
is the sum of individual the WIP’s for each workstation (sub-
system) and equals 7.215 jobs, and the cycle-time estimate is 7.215/0.5823 =
12.391 hr. The system and individual workstation results from the analytical pro-
cedure are compared with those from a simulation model. The simulation run was
long enough so that the half-width of the confidence limits for each estimate was
approximately 1% of the estimate or smaller. The simulation and analytical com-
parisons are given in Table 9.8. Both the mean throughput and cycle time errors are
less that 1% and the error in the WIP estimates is less than 2%; thus, the results of
the algorithm yield very acceptable results.
Table 9.8 Comparison of the analytical and simulation results
Analytical Simulation
th W IP CT th W IP CT
System 0.5823/hr 6.798 11.674 hr 0.588/hr 6.892 11.717 hr
Workstation 1 0.5823/hr 3.391 5.823 hr 0.588/hr 3.447 5.861 hr
Workstation 2 0.5823/hr 1.784 3.063 hr 0.588/hr 1.807 3.072 hr
Workstation 3 0.5823/hr 1.623 2.787 hr 0.588/hr 1.638 2.785 hr
The results of our analysis indicate that the WIP in each workstation is signifi-
cantly below the kanban limits set for system control. One reason for this is that the
job preparation time to initiate each job to the factory is on the same order as the
process times. This is established so that the computations would result in numbers
310 9 Serial Limited Buffer Models
that could easily be checked. It is often the case that the rate at which Machine 0
operates would be significantly greater than the workstation processing rates.
9.3.5 Generalizations
Serial flow networks only were considered in this presentation. General feed-
forward flow networks, that is acyclic flow only with no feedback branching, were
studied by Lee and Pollock [10], and general networks that also allow backward
branching were studied by Jun and Perros [9]. This latter problem class encounters
the phenomenon called dead-locking and these systems are difficult even to simu-
late (see Deuermeyer et al. [5] and Venkatesh et al. [16]).
•
Suggestion: Do Problems 9.6–9.8.
9.4 Setting Kanban Limits
A significant problem associated with the implementation of a WIP limiting con-
trol strategy for factory operations is the setting of the kanban or WIP limits. This
problem has been studied in the literature for special cases [2, 7, 8, 14] and Chap. 7
of the book by Papadopoulos, Heavey and Browne [12] discusses the results and
characterizations of the structural properties found in the literature to that date. A
recent analysis by Spinellis, Papadopoulos and Smith [15] uses simulated annealing
as the optimization tool to find the buffer settings for long production lines. Heuris-
tic methods (such as simulated annealing, tabu search and genetic algorithms (see
[3]) are particularly suited to the optimization of this type of problem due to the
combinatorial and stochastic nature of the problem. These methods are called meta-
heuristics. According to Glover and Laguna [6]: “A meta-heuristic refers to a master
strategy that guides and modifies other heuristics to produce solutions beyond that
normally generated in a quest for local optimality.”
The problem is to find the individual buffer capacities (workstation WIP limits)
that maximize the throughput for a given total allocation of buffer units for a se-
rial system of workstations. The maximum throughput for a system without a total
buffer-units limit is obtained by infinite queues allowed at each machine in the se-
rial configuration. To make the problem realistic, the objective has been taken to
find the optimal allocation of a fixed number of buffer units. By allocation is meant
the number of buffer units to assign to each of the machines (workstations). So by
fixing the total number of units available, the allocation of these units to the various
machines so as to maximize the system throughput is a well-defined problem. Then
the question of how many total units to allow can be answered based on a secondary
criterion such as an upper limit on the mean cycle time or reaching a minimum
throughput level.
9.4 Setting Kanban Limits 311
In this section, a scheme is developed for obtaining very good, if not optimal,
buffer level configurations. Researchers such as Altiok and Stidham [2] conjecture
that the response function (throughput) is smooth and convex in nature. The exam-
ple problem discussed below demonstrates that this function is not actually convex
for all cases. Thus, the solution methodology must deal with local maxima that
are not the global maximum. The general search strategy is to use a neighborhood
search procedure for finding local maxima in conjunction with a restart procedure
designed to explore the solution space beyond these local maxima. The underly-
ing throughput evaluation methodology is the decomposition approach (mean-value
response generator) discussed in this chapter. The approach developed herein can
be viewed as a particular application of tabu search, but apparently the complex
meta-heuristic structure commonly used for non-convex combinatorial problems
is not needed. For example, the approach in [15] of using simulated annealing is
much more complex than appears necessary for the buffer allocation problem. Their
heuristic methodology, however, allows for the simultaneous optimization of buffer
allocations and machine processing rates. This combined optimization is a much
more difficult problem that requires this more powerful approach.
9.4.1 Allocating a Fixed Number of Buffer Units
For a given number of buffer space units, the problem is to find the best allocation of
these units across the workstations so as to maximize the system throughput. Since
this total must remain constant, it seems reasonable to use an exchange algorithm
where a single unit is taken from one workstation and assigned to another. Then the
throughput for this new configuration is evaluated. The basic step of the algorithm
is to evaluate all single units exchanges (both positive and negative) for each pair
of workstations (this is called a cycle). A cycle results in n(n −1) evaluations for a
n workstation problem. The best configuration for all these exchanges is stored as
the current best (incumbent solution) and the process repeated. If the best exchange
value is not better than the incumbent solution, then the process has reached a local
maximum. In this way a local search is performed with the best configuration being
used as the base point for further explorations (cycles). For concave functions this
local search procedure converges to the global maximum.
Once a local maximum has been obtained, the pair-wise exchange of a single unit
of buffer space between two workstations cannot find a better point and each addi-
tional cycle will terminate again with this same solution. To allow the exploration
to continue, a restart procedure is initiated once a local maximum has been identi-
fied. The restart procedure implemented herein is to start the unit-exchange process
from the local maximum with this configuration’s throughput value set to zero (an
incumbent value of zero). This allows the unit-exchange process to find the second
best point in the neighborhood as the solution obtained during the cycle since the
starting point (configuration) cannot be generated by this exchange procedure. The
neighborhood search (cycle procedure) continues from this solution. This one-unit
312 9 Serial Limited Buffer Models
offset from the local maximum allows the neighborhood search procedure to ex-
plore a slightly different region than it could reach from the local maximum point.
If the local concave nature of this local maximum is not too broad, the next cycle
has a chance of finding a better solution and continuing the search at a higher level
than was obtained via the local maximum. If the solution obtained by the restart
procedure is the same local maximum, then the search process is terminated with
that point as its maximal configuration. The algorithm in pseudo-code is given be-
low. In this pseudo-code, BP is the base policy and BP
is the one-unit offset per-
mutation policy obtained by routine P ermutat ion(±1, BP), maxthr u is the current
best throughput value, and maxpolicy is the associated policy. The routine “evalu-
ate BP
” solves the decomposition and obtains the system performance throughput
value thru(BP
). The algorithm is started with a buffer allocation BP whose sum
determines the total number of units to be allocated.
Algorithm
start: BP ←{b
1
,b
2
,··· ,b
n
}
maxthru ← 0
maxpolicy ← BP
f ound ← 0
holdthru ← 0
cycle: BP ← maxpolicy
Repeat
BP
← Permutat ion(±1, BP)
evaluate BP
If thru(BP
) > maxthru Then
maxthru ← thru(BP
)
maxpolicy ← BP
EndIf
Until BP
= /0
If maxthru > holdthru Then
holdthru ← maxthru
GoTo cycle
EndIf
local: f ound ← f ound + 1
If f ound = 1 Then
maxthru ← 0
GoTo cycle
EndIf
Stop: Print maxthru, maxpolicy
Since there is no closed-form relationship that describes the throughput rate as a
function of the buffer configuration, it cannot be determined analytically whether or
not this throughput function is concave. Most of the optimization approaches used
in the literature for the buffer allocation problem will only isolate local maxima. The