300 9 Serial Limited Buffer Models
9.3.2 The Backward Pass
Each iteration of the algorithm involves a forward pass and then a backward pass.
The forward pass updates the arrival-machine distribution parameters and the back-
ward pass updates the service-machine distribution parameters. The difficulty with
analyzing the service-machine is that after it is finished processing, the next sub-
system may have no space for it so that the service-machine becomes blocked. This
effectively increases the job delay time of the job controlling the machine. The way
this is handled in the decomposition procedure, where the connection between ad-
jacent workstations is not available, is to increase the job processing times. Thus,
in the backwards pass, the probability that an arriving job finds a full s ubsystem is
needed because the time that it takes to unblock service-machine is dependent on
the phase of the downstream machine. In addition, the probability that the arriving
job finds the service-machine in a specific phase is also needed. Therefore, in the
following discussion, we will let p
(i,F)
a,k
denote the probability that an arrival to Sub-
system k (k < n) finds the subsystem full and its service-machine in Phase i.Aswe
begin the backwards pass, we start with the final subsystem (i.e., Subsystem n) and
its service-machine is always exponential so it has no phases; hence, p
F
a,n
will be
used to denote that an arrival to the final subsystem finds the subsystem full.
9.3.2.1 Backward Pass for Subsystem 3
The service-machine for the final subsystem needs no updating since it is never
blocked; however, the probability that an arrival to the final subsystem finds the
subsystem full must be calculated so that the service-machine for the penultimate
subsystem can be updated. To obtain this probability, the steady-state probabilities
for the subsystem must be determined. The data that are needed for determining
the generator matrix for the steady-state probabilities are the arrival-machine pa-
rameters (namely,
α
3
, p
3
, and
β
3
from p. 298) and the mean processing rate for the
service-machine (namely, 1/
t
3
). The state space for Subsystem 3 is very similar to
Subsystem 2 (see p. 296) except there are two additional states since the kanban
limit for Subsystem 3 is 4 jobs whereas the capacity for Subsystem 2 was 3 jobs.
The generator matrix is also very similar (see p. 296) except it will have two more
rows and columns. Once the generator matrix is constructed, the probabilities can
be obtained from Property 9.3 to yield the results in Table 9.3.
Table 9.3 Probabilities for Subsystem 3 — first backward pass
Phase of Number of Jobs in System
Arrival-Machine01234
1 0.2869 0.2246 0.1578 0.1110 0.0787
2 0.0407 0.0180 0.0125 0.0082 0.0045
b 0.0571