A DYNAMIC PROGRAMMING ALGORITHM

FOR THE BUFFER ALLOCATION PROBLEM

IN HOMOGENEOUS ASYMPTOTICALLY
RELIABLE SERIAL PRODUCTION LINES
A. C. DIAMANTIDIS AND C. T. PAPADOPOULOS

Received 9 February 2004 and in revised form 5 April 2004

In this study, the buer allocation problem (BAP) in homogeneous, asymptotically reli-
able serial production lines is considered. A known aggregation method, given by Lim,
Meerkov, and Top (1990), for the performance evaluation (i.e., estimation of through-
put) of this type of production lines when the buer allocation is known, is used as an
evaluative method in conjunction with a newly developed dynamic programming (DP)
algorithm for the BAP. The proposed algorithm is applied to production lines where the
number of machines is varying from four up to a hundred machines. The proposed algo-
rithm is fast because it reduces the volume of computations by rejecting allocations that
do not lead to maximization of the lines throughput. Numerical results are also given for
large production lines.

1. Introduction and literature review

The analysis of production or flow lines and, more generally, of manufacturing systems
has been the object of numerous studies. Usually, production lines are modeled as serial
queuing networks and analyzed either analytically as Markovian models or via approxi-
mate decomposition methods and simulation.
The literature on the modeling of production lines is vast and a large amount of re-
search over the years has been devoted to this area. One of the first most complete analyses
of such systems was published in 1962 by Sevastyanov [20]. The large amount of research
allows us to review only the most directly relevant studies here.
For a systematic classification of the relevant works on the stochastic modeling of pro-
duction lines, the interested reader is referred to the books by Buzacott and Shanthikumar
[3], Papadopoulos et al. [17], Gershwin [7], Altiok [2], and Helber [10], and the review
papers by Dallery and Gershwin [5] and Papadopoulos and Heavey [16], among others.
Hillier and Boling [11] and Heavey et al. [9], analyzed serial production lines using
Markovian models, whereas Gershwin [6] and Dallery et al. [4] utilized decomposition
approaches to evaluate the performance of the same type of production lines. The former
method is practically applicable only to short lines due to the curse of the dimensionality

Copyright 2004 Hindawi Publishing Corporation

Mathematical Problems in Engineering 2004:3 (2004) 209223
2000 Mathematics Subject Classification: 78M50, 90B30, 90C39, 49L20
URL: http://dx.doi.org/10.1155/S1024123X04402014
210 A DP algorithm for the buer allocation problem

problem arising in the Markovian models. The latter method can be applied to large
production lines at the expense of the accuracy of the numerical results. Altiok [2], among
others, studied the phase-type distributions and their use to approximate any general
distribution of service or interarrival times in the stochastic modeling of production lines.
Meerkov and his colleagues have developed performability, a quite interesting theory
and method of analysis of production lines. Lim et al. [14] presented an asymptotic anal-
ysis technique for a model of a serial production line, gave estimates of its accuracy, and
formulated a convergence theorem for their solution algorithm.
One of the most interesting questions that designers face in a serial production line
is the buer allocation problem (BAP), that is, how much buer storage to allow and
where to place it within the line. This is an important question because buers can have a
great impact on the eciency of the production line. Buers compensate for the blocking
and the starving of the lines stations. However, buer storage is expensive both due to
its direct cost and due to the increase of the work-in-process (WIP) inventories. In [17],
both evaluative and generative (optimization) models are given for modeling the various
types of manufacturing systems.
The BAP has been solved via various techniques such as simulated annealing [21, 22],
genetic algorithms [15], cross entropy search method [1], gradient techniques [8], heuris-
tics [18], and other search methods (tabu search, among others).
One of the optimization methods for solving the BAP is the dynamic programming
(DP) method. Several authors have employed the DP method for solving the BAP (see
Jafari and Shanthikumar [12], Kubat and Sumita [13], and Yamashita and Altiok [23],
among others). However, this method was employed in the case of a production line with
synchronous transfer as defined in [17], among others, where the steady-state through-
put can be approximated in a closed recursive form. Another classification of the research
work relevant to the BAP is based on whether the lines under study are balanced or un-
balanced. A line is called balanced (or unbalanced) if the mean processing times at each
station are equal (or unequal). Powell [19] provided a literature review according to this
scheme.
In this paper, a DP algorithm for the BAP is developed. This algorithm makes use of an
aggregation procedure to approximate various performance measures of the production
line developed by Lim et al. [14].
The remainder of this paper is structured as follows. Section 2 presents the problem
and the model. Section 3 presents the proposed DP algorithm with an application exam-
ple. Section 4 gives numerical results for several production lines, both short and large,
and Section 5 concludes the paper and proposes some areas for further research. Finally,
the appendix gives the aggregation method for the approximation of throughput for a
given buer allocation, as taken by Lim et al. [14].

2. The model and the problem definition

The main assumptions of our model are the same as those made by Lim et al. [14], as
follows.
(1) A serial production line (see Figure 2.1) consists of M machines Mi , i = 1,...,M,
and M 1 buers Bi of finite capacity at least one (this assumption is dictated by
 A. C. Diamantidis and C. T. Papadopoulos 211

M1 B1 M2 B2 M3 MM 1 BM 1 MM

Figure 2.1. A production line with M machines and M 1 buers.

(A.1), as otherwise function Q(a,N) is not defined). Assuming that each buer
stores at least 1 unit and N is the total buer capacity that can be allocated, it is
obvious that for a production line consisting of M machines and M 1 buers,
the maximum buer capacity that each buer can store is up to N M + 2 units.
(2) An inexhaustive supply of workpieces is available upstream machine M1 , and an
unlimited storage area is present downstream machine MM . Thus the first ma-
chine is never starved and the last machine is never blocked.
(3) All machines have equal and constant service times. Time is scaled so that this
machine cycle takes one time unit. Thus processing times are assumed to be de-
terministic and identical for all machines and are taken as the time unit.
(4) Machine Mi , being not blocked and not starved, takes part in production during
any time slot with probability i and fails to do so with probability 1 i (pro-
duction lines in which machines have this property are called homogeneous by
Lim et al. [14], that is, a homogeneous line is characterized by machines with one
parameter only, i , instead of the two parameters pi and ri usually used in the
literature, where pi and ri denote, respectively, the failure rate and the repair rate
of machine Mi ). It is assumed that blocked and/or starved machines do not fail.
(5) It is assumed that the production lines under consideration are homogeneous,
asymptotically reliable, that is, i = 1 i , where 0 <
1 and i , i = 1,...,M,
is independent of . The i s are known as the loss parameters, as defined by Lim
et al. [14].

Following the lines of Lim et al. [14], denote by Li the cumulative losses in the ith op-
eration (jobs/h) and by AXi the actual throughput, then i = 1 Li /AXi , and since i =
1 i , where 0 <
1, it is obvious that Li
AXi . Thus the loss parameter i refers to
the fraction of the cumulative losses in the ith operation divided by the actual throughput
of machine Mi .
Major decisions in designing production lines involve the workload allocation and the
BAPs with respect to an objective function such as profit maximization or throughput
maximization for a given total buer capacity. In this study, the latter has been chosen to
deal with; namely, our objective is to find the optimal buer allocation for a given total
buer capacity in order to maximize the average production rate of the production line.
The above problem may be expressed mathematically as follows.

1
Find the optimal vector B = (N1 ,...,NM 1 ) that maximizes {XM } given that M j =1 N j
= N, where XM is the mean production rate (throughput) of a production line consisting
of M machines and M 1 buers. N is the total buer capacity and Ni is the capacity of
buer i, i = 1,...,M 1.
212 A DP algorithm for the buer allocation problem

3. The dynamic programming algorithm

Before expressing the DP algorithm mathematically, we introduce the following symbols.
Zi is the buer capacity that the DP algorithm allocates to buer i and to all buers
upstream buer i. Therefore Zi = N1 + + Ni, for all i 2. It is obvious that Z1 = N1
and that ZM 1 = N1 + + NM 1 = N.
f f
j (N j 1 ) is the value of the aggregated loss parameter j , defined in the appendix,
when buer space N j 1 is allocated to buer j 1, where N j 1 = 1,2,...,N M + 2, j =
f
2,...,M. Equation (A.14) in the appendix indicates that parameter j 1 (N j 1 ) is used in
f f
order to calculate parameter j . From the various values of parameter j 1 , that one
with the maximum value is selected.
f
f1 (Z1 ) is the set of feasible values of parameter 2 (N1 ), N1 = 1,...,N M + 2, that are
used to calculate f2 (Z2 ).
The DP algorithm consists of four steps which are summarized below.
f
Step 1. Calculate the forward pass loss parameters i (Ni1 ), i = 2,...,M, Ni1 = 1,...,
N M + 2, by using expression (A.9) of Lim et al. [14].
Step 2. The fundamental recursion equation. Execute the following recursive equations:

   f    
fj Zj = min j+1 N j + f j 1 Z j 1 ,
feasible values
N j , f j 1 (Z j 1 )

j = 2,...,M 1, N j = 1,...,N M + 2, (3.1)

Z j = j,...,N M + j + 1, ZM 1 = N,
Z j 1 = Z j N j .

Step 3. Termination of the algorithm. The algorithm terminates when the value of
fM 1 (ZM 1 ) is calculated.
Step 4. Determination of the optimal buer allocation. The optimal buer allocation is
given by vector (T1 ,T2 ,...,TM 1 ), with its elements obtained as follows.

(1) Allocate TM 1 units of buer space to buer BM 1 , where TM 1 is the value for
which fM 1 (N) is obtained.
(2) Allocate TM 2 units of buer space to buer BM 2 , where TM 2 is the value for
which fM 2 (N TM 1 ) is obtained.
(3) Allocate TM 3 units of buer space to buer BM 3 , where TM 3 is the value for
which fM 3 (N TM 1 TM 2 ) is obtained, and so forth.
(4) Allocate T2 and T1 units of buer capacity to buers B2 and B1 , respectively, where
T2 and T1 are the values for which f2 (N (TM 1 + TM 2 + + T3 )) is obtained.

3.1. Application of the algorithm: an example. In this section, an application of the

algorithm is given for a production line with 4 machines and loss parameters 1 = 3.4,
2 = 2.1, 3 = 4.3, and 4 = 1.1, respectively. The total buer capacity that is to be allo-
cated is 10 units.
 A. C. Diamantidis and C. T. Papadopoulos 213
f
Table 3.1. Terms j (N j 1 ), j = 2,3,4, calculated as described in Step 1.

Buer 1 Buer 2 Buer 3

f f f
N1 2 (N1 ) N2 3 (N2 ) N3 4 (N3 )
1 5.5 1 9.8 1 10.9
2 4.2021 2 7.3874 2 9.9114
3 3.8008 3 6.5986 3 9.8135
4 3.6215 4 6.2158 4 9.8021
5 3.5285 5 5.9952 5 9.8013
6 3.4765 6 5.8553 6 9.80045
7 3.4463 7 5.76104 7 9.800442
8 3.4283 8 5.6948 8 9.800440

f
Step 1. In this step, we calculate the forward pass loss parameters i (Ni1 ), i = 2,...,4,
Ni1 = 1,...,8. These parameters are presented in Table 3.1 and will be used throughout
the algorithm.
Step 2. In DP, computations are carried out in stages by breaking down the problem into
subproblems. Each subproblem is then considered separately with the objective of reduc-
ing the volume of computations. However, since the subproblems are interdependent, a
procedure must be devised to link the computations in a manner that guarantees that a
feasible solution for each stage is also feasible for the entire problem.

j = 2, Z2 = 2,...,9. (3.2)

For Z2 = 2 = N1 + N2 , the only feasible values of N1 and N2 are {N1 = 1 and N2 = 1}. As
f
f1 (Z1 ), the value of parameter 2 (1) is used and
   f f 
f2 Z2 = 2 = min 3 (1) + 2 (1) = min{9.8 + 5.5} = 15.3 (3.3)

corresponding to T1 = 1 and T2 = 1.
For Z2 = 3 = N1 + N2 , the feasible values of N1 and N2 are {N1 = 1 and N2 = 2} or
f f
{N1 = 2 and N2 = 1}. As f1 (Z1 ), the values of parameters 2 (1), 2 (2) are used and

   f f f f 
f2 Z2 = 3 = min 3 (1) + 2 (2),3 (2) + 2 (1)
= min{9.8 + 4.2021,7.3874 + 5.5} (3.4)
= min{14.0021,12.8874} = 12.8874

corresponding to T1 = N1 = 1 and T2 = N2 = 2.
For Z2 = 4 = N1 + N2 , the feasible values of N1 and N2 are {N1 = 1 and N2 = 3}, {N1 =
f f
2 and N2 = 2}, or {N1 = 3 and N2 = 1}. As f1 (Z1 ), the values of parameters 2 (1), 2 (2),
f
2 (3) are used and
214 A DP algorithm for the buer allocation problem
   f f f f f f 
f2 Z2 = 4 = min 3 (1) + 2 (3),3 (2) + 2 (2),3 (3) + 2 (1)
= min{9.8 + 3.8008,7.3874 + 4.2021,6.5986 + 5.5} (3.5)
= min{13.6008,11.5895,12.0986, } = 11.5895

corresponding to T1 = N1 = 2 and T2 = N2 = 2.
For Z2 = 5 = N1 + N2 , the feasible values of N1 and N2 are {N1 = 1 and N2 = 4}, {N1 =
2 and N2 = 3}, {N1 = 3 and N2 = 2}, or {N1 = 4 and N2 = 1}. As f1 (Z1 ), the values of
f f f f
parameters 2 (1), 2 (2), 2 (3), 2 (4) are used and
   f f f f f f f f 
f2 Z2 = 5 = min 3 (1) + 2 (4),3 (2) + 2 (3),3 (3) + 2 (2),3 (4) + 2 (1)
= min{9.8 + 3.6215,7.3874 + 3.8008,6.5986 + 4.2021,6.2158 + 5.5} (3.6)
= min{13.4215,11.1882,10.8007,11.7158} = 10.8007

corresponding to T1 = N1 = 2 and T2 = N2 = 3.
For Z2 = 6 = N1 + N2 , the feasible values of N1 and N2 are {N1 = 1 and N2 = 5}, {N1 =
2 and N2 = 4}, {N1 = 3 and N2 = 3}, {N1 = 4 and N2 = 2}, or {N1 = 5 and N2 = 1}.
f f f f f
As f1 (Z1 ), the values of parameters 2 (1), 2 (2), 2 (3), 2 (4), 2 (5) are used and

   f f f f f f
f2 Z2 = 6 = min 3 (1) + 2 (5),3 (2) + 2 (4),3 (3) + 2 (3),
f f f f 
3 (4) + 2 (2),3 (5) + 2 (1)
= min{9.8 + 3.5285,7.3874 + 3.6215,3.8008 + 6.5986,
(3.7)
6.2158 + 4.2021,5.9952 + 5.5}
= min{13.3285,11.0089,10.3994,10.4179,11.4952}
= 10.3994

corresponding to T1 = N1 = 3 and T2 = N2 = 3.
For Z2 = 7 = N1 + N2 , the feasible values of N1 and N2 are {N1 = 1 and N2 = 6},
{N1 = 2 and N2 = 5}, {N1 = 3 and N2 = 4}, {N1 = 4 and N2 = 3}, {N1 = 5 and N2 = 2},
f f f f
or {N1 = 6 and N2 = 1}. As f1 (Z1 ), the values of parameters 2 (1), 2 (2), 2 (3), 2 (4),
f f
2 (5), 2 (6) are used and
   f f f f f f
f2 Z2 = 7 = min 3 (1) + 2 (6),3 (2) + 2 (5),3 (3) + 2 (4),
f f f f f f 
3 (4) + 2 (3),3 (5) + 2 (2),3 (6) + 2 (1)
= min{9.8 + 3.4765,7.3874 + 3.5285,6.5986 + 3.6215,
(3.8)
6.2158 + 3.8008,5.9952 + 4.2021,5.8553 + 5.5}
= min{13.2765,10.9159,10.2201,10.0166,10.1973,11.3553}
= 10.0166

corresponding to T1 = N1 = 3 and T2 = N2 = 4.
 A. C. Diamantidis and C. T. Papadopoulos 215

For Z2 = 8 = N1 + N2 , the feasible values of N1 and N2 are {N1 = 1 and N2 = 7}, {N1 =
2 and N2 = 6}, {N1 = 3 and N2 = 5}, {N1 = 4 and N2 = 4}, {N1 = 5 and N2 = 3}, {N1 =
f f
6 and N2 = 2}, or {N1 = 7 and N2 = 1}. As f1 (Z1 ), the values of parameters 2 (1), 2 (2),
f f f f f
2 (3), 2 (4), 2 (5), 2 (6), 2 (7) are used and
   f f f f f f f f
f2 Z2 = 8 = min 3 (1) + 2 (7),3 (2) + 2 (6),3 (3) + 2 (5),3 (4) + 2 (4),
f f f f f f 
3 (5) + 2 (3),3 (6) + 2 (2),3 (7) + 2 (1)
= min{9.8 + 3.4463,7.3874 + 3.4765,3.65986 + 5.285,6.2158 + 3.6215,
(3.9)
5.9952 + 3.8008,5.8553 + 4.2021,5.76104 + 5.5}
= min{13.2463,10.8639,10.1271,9.8373,9.796,10.0574,11.26104}
= 9.796

corresponding to T1 = N1 = 3 and T2 = N2 = 5.
For Z2 = 9 = N1 + N2 , the feasible values for N1 and N2 are {N1 = 1 and N2 = 8}, {N1 =
2 and N2 = 7}, {N1 = 3 and N2 = 6}, {N1 = 4 and N2 = 5} {N1 = 5 and N2 = 4}, {N1 =
6 and N2 = 3}, {N1 = 7 and N2 = 2}, or {N1 = 8 and N2 = 1}. As f1 (Z1 ), the values of
f f f f f f f f
parameters 2 (1), 2 (2), 2 (3), 2 (4), 2 (5), 2 (6), 2 (7), 2 (8) are used.
Therefore
   f f f f f f f f
f2 Z2 = 9 = min 3 (1) + 2 (8),3 (2) + 2 (7),3 (3) + 2 (6),3 (4) + 2 (5),
f f f f f f f f 
3 (5) + 2 (4),3 (6) + 2 (3),3 (7) + 2 (2),3 (8) + 2 (1)
= min{9.8 + 3.4283,7.3874 + 3.4463,6.5986 + 3.4765,6.2158 + 3.5285,
5.9952 + 3.6215,5.8553 + 3.8008,5.76104 + 4.2021,5.6948 + 5.5}
= min{13.2283,10.8337,10.0751,9.7443,9.6167,9.6561,9.96314,11.1948}
= 9.6167
(3.10)

corresponding to T1 = N1 = 4 and T2 = N2 = 5;

i = 3, Z3 = 10. (3.11)

For N3 = 1,...,N M + 2 = 1,...,8, it is straightforward that the feasible values of f2 (Z2 )

and N3 are (N3 = 1 and f2 (Z2 = 9)), (N3 = 2 and f2 (Z2 = 8)), (N3 = 3 and f2 (Z2 = 7)),
(N3 = 4 and f2 (Z2 = 6)), (N3 = 5 and f2 (Z2 = 5)), (N3 = 6 and f2 (Z2 = 4)),
(N3 = 7 and f2 (Z2 = 3)), or (N3 = 8 and f2 (Z2 = 2)).
Therefore
   f   f   f  
f3 Z3 = 10 = min 4 (1) + f2 Z2 = 9 ,4 (2) + f2 Z2 = 8 ,4 (3) + f2 Z2 = 7 ,
f   f   f  
4 (4) + f2 Z2 = 6 ,4 (5) + f2 Z2 = 5 ,4 (6) + f2 Z2 = 4 ,
f   f  
4 (7) + f2 Z2 = 3 ,4 (8) + f2 Z2 = 2
216 A DP algorithm for the buer allocation problem

= min{10.9 + 9.6167,9.9114 + 9.796,10.0166 + 9.8135,

10.3994 + 9.8021,10.8007 + 9.8013,11.5895 + 9.80045,
12.8874 + 9.800442,15.3 + 9.800440}
= 19.7074
(3.12)

corresponding to T3 = N3 = 2 and f2 (Z2 = 8).

Step 3. The algorithm terminates as f3 (Z3 ) has been calculated.
Step 4. From the previous calculations, notice that f2 (Z2 = N T3 = 10 2 = 8) was
obtained for T1 = 3 and T2 = 5.
Therefore the optimal buer allocation is given by the vector (T1 ,T2 ,T3 ) = (3,5,2).

4. Numerical results
In this section, numerical results are presented showing buer allocations obtained using
the proposed DP algorithm for four, five, six stations, and large production lines with
up to a hundred stations (the latter are given in Section 4.1). For the short lines, by the
enumeration method, all possible buer allocations of a given total buer capacity were
tested and the optimal buer allocation, namely, that one giving the maximum through-
put, was obtained. The DP algorithm was implemented in PASCAL and in a very slow old
PC486 system. Tables 4.1, 4.2, and 4.3 present the buer allocations, for given total buer
capacities, obtained by the DP algorithm for short lines with four, five, and six stations,
respectively.
Comment. We have applied enumeration for all total buer capacities given in Table 4.1,
that is, for 4 to 10 units of total buer capacities. Comparing the results from the enumer-
ation method with those obtained by the DP algorithm, we have found that in all cases
the results were identical. Also notice that the run time is very small and lies between 0.04
and 0.19 seconds even in a slow old PC486 system. In Tables 4.2 and 4.3, for the cases
where the results from the enumeration method dier from those obtained by the pro-
posed algorithm, a percentage error has been introduced. The error has been calculated
using the following formula:
 
XM,enum XM,DP 
Error = 100%, (4.1)
XM,enum

where XM,enum and XM,DP denote the throughput of the buer configuration obtained by
enumeration and the proposed DP algorithm, respectively.

4.1. Numerical results for large production lines. In this section, numerical results are
presented, showing buer allocations obtained using the proposed DP algorithm in pro-
duction lines with many stations M, 10 M 100. Tables 4.4, 4.5, 4.6, and 4.7 present
the buer allocations obtained by the DP algorithm for given total buer capacities, for
large production lines with ten, fifty, eighty, and one hundred stations, respectively.
 A. C. Diamantidis and C. T. Papadopoulos 217
Table 4.1. Application of the DP algorithm in a four-station production line with 1 = 3.4, 2 = 2.1,
3 = 4.3, and 4 = 1.1.

N Buer 1 Buer 2 Buer 3 X4 ( = 0.01) Run time

10 3 5 2 0.9522 0.19 s
9 3 4 2 0.9510 0.17 s
8 3 3 2 0.9487 0.11 s
7 2 3 2 0.9452 0.09 s
6 2 2 2 0.9396 0.08 s
5 2 2 1 0.9328 0.06 s
4 1 2 1 0.9182 0.04 s

Table 4.2. Application of the DP algorithm in a five-station production line with 1 = 3.4, 2 = 2.1,
3 = 4.3, 4 = 1.1, and 5 = 5.5.

N B1 B2 B3 B4 X5,enum X5,DP Error Run time

10 2 3 2 3 0.9359 0.9358 0.0106% 0.09 s
9 2 2 2 3 0.9321 0.9320 0.0107% 0.08 s
8 2 2 1 3 0.9269 0.9201 0.7278% 0.06 s
7 2 2 1 2 0.9164 0.9114 0.5370% 0.05 s
6 1 2 1 2 0.9009 0.9001 0.0872% 0.05 s

Table 4.3. Application of the DP algorithm in a six-station production line with 1 = 3.4, 2 = 2.1,
3 = 4.3, 4 = 1.1, 5 = 2.4, and 6 = 3.7.

N B1 B2 B3 B4 B5 X6,enum X6,DP Error Run time

10 2 2 2 2 2 0.9338 0.9338 0% 1.89 s
9 2 2 1 2 2 0.9237 0.9217 0.212% 0.91 s
8 1 2 1 2 2 0.9139 0.9096 0.471% 0.73 s
7 1 2 1 1 2 0.8969 0.8907 0.686% 0.49 s
6 1 1 1 1 2 0.8715 0.8589 1.441% 0.30 s

Table 4.4. Application of the DP algorithm in a ten-station production line with M = 10, N = 20. The
production rate for this specific buer allocation is 0.9382.

1 2 3 4 5 6 7 8 9 10
3.4 2.1 4.3 1.1 2.4 3.7 1.5 2.3 2.6 1.4

B1 B2 B3 B4 B5 B6 B7 B8 B9 Time
2 3 2 2 3 2 2 2 2 0.3 s
218 A DP algorithm for the buer allocation problem
Table 4.5. Application of the DP algorithm in a fifty-station production line with M = 50, N = 90.
The production rate for this specific buer allocation is 0.8651.

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10
2 2 1 2 2 1 2 2 1 2
B11 B12 B13 B14 B15 B16 B17 B18 B19 B20
2 2 2 2 2 2 1 2 2 2
B21 B22 B23 B24 B25 B26 B27 B28 B29 B30
2 2 2 2 2 2 2 2 2 2
B31 B32 B33 B34 B35 B36 B37 B38 B39 B40
2 2 2 2 2 2 2 1 2 2
B41 B42 B43 B44 B45 B46 B47 B48 B49 Time
2 2 2 2 2 2 1 2 1 27 s

Table 4.6. Application of the algorithm in an eighty-station production line with M = 80, N = 200.
The run time is 6 minutes and 0.44 second in a PC486. The production rate for this specific
buer allocation is 0.8810.

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10
6 8 2 3 4 3 3 3 2 3
B11 B12 B13 B14 B15 B16 B17 B18 B19 B20
3 3 2 2 3 2 2 2 2 3
B21 B22 B23 B24 B25 B26 B27 B28 B29 B30
3 3 3 3 3 3 2 3 3 3
B31 B32 B33 B34 B35 B36 B37 B38 B39 B40
3 2 2 3 3 3 3 2 2 2
B41 B42 B43 B44 B45 B46 B47 B48 B49 B50
2 2 2 2 2 2 2 2 2 2
B51 B52 B53 B54 B55 B56 B57 B58 B59 B60
2 2 3 3 3 2 2 2 2 2
B61 B62 B63 B64 B65 B66 B67 B68 B69 B70
2 3 2 2 2 2 3 3 3 2
B71 B72 B73 B74 B75 B76 B77 B78 B79
2 3 2 3 3 2 2 2 3

Unfortunately, we cannot compare these results with those obtained from enumera-
tion because it is impossible to use enumeration in large production lines (because of the
huge number of states that should be examined).
 A. C. Diamantidis and C. T. Papadopoulos 219
Table 4.7. Application of the DP algorithm in a hundred-station production line with M = 100, N =
400. The run time is 24 minutes and 6.81 seconds in a PC486. The production rate for this specific
buer allocation is 0.9112.

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10
9 14 5 7 8 5 5 5 4 6
B11 B12 B13 B14 B15 B16 B17 B18 B19 B20
6 6 4 4 4 4 3 4 4 4
B21 B22 B23 B24 B25 B26 B27 B28 B29 B30
5 5 5 5 5 4 4 4 4 4
B31 B32 B33 B34 B35 B36 B37 B38 B39 B40
4 4 4 5 5 4 5 3 4 4
B41 B42 B43 B44 B45 B46 B47 B48 B49 B50
4 4 3 3 3 4 3 4 3 4
B51 B52 B53 B54 B55 B56 B57 B58 B59 B60
3 3 4 4 4 3 3 3 4 4
B61 B62 B63 B64 B65 B66 B67 B68 B69 B70
3 4 4 3 4 4 4 4 4 4
B71 B72 B73 B74 B75 B76 B77 B78 B79 B80
4 4 3 4 4 4 3 3 4 4
B81 B82 B83 B84 B85 B86 B87 B88 B89 B90
4 3 3 3 3 3 3 3 4 3
B91 B92 B93 B94 B95 B96 B97 B98 B99
3 4 3 4 3 3 3 3 3

5. Conclusions and further research

In this study, we present a dynamic programming algorithm that solves the buer alloca-
tion problem (BAP) of N units of total buer capacity in a homogeneous asymptotically
reliable serial production line consisting of M machines and M 1 buers. The main
conclusions are as follows.
(1) The proposed dynamic programming algorithm for short (with M < 10 stations)
production lines found, in almost all cases, the optimal solution for the BAP. In
the cases where the algorithm did not give the optimal solution, it gave a near-
optimal solution.
(2) The algorithm is quite fast and in all cases where we applied it, we did not en-
counter any bugs and the algorithm always converged to a solution. The run time
in all cases was quite small.
(3) The DP algorithm can be applied in large production lines to eectively (rapidly
and accurately) find a near-optimal solution to the BAP. Even in large systems,
the proposed algorithm worked quite eectively.
220 A DP algorithm for the buer allocation problem

A further investigation to improve the accuracy of the proposed algorithm might in-
clude the eect the backward pass search might have on the accuracy of the numerical
results. However, an application of this backward pass to a few short lines showed no
further improvement in the optimal buer allocation. Another point that needs further
investigation in order to improve the accuracy of the proposed algorithm might be the
appropriate use of the values of the loss parameters, i . In our numerical results, we used
values analogous to those used by Lim et al. [14] for short lines.
An extension of the work presented in this paper would be the study of a production
line where the general topology would be quite dierent from the topology of the model
considered in this study. That is, a production line which consists of identical machines in
parallel order at each workstation. Another optimization problem, apart from the buer
allocation, would be the server allocation as well as the workload allocation problem or,
even better, the simultaneous optimization of the parameters of these design problems
taken in various combinations.

Appendix
Throughput approximation of homogeneous asymptotically reliable production lines
for a given buer allocation (taken from Lim et al. [14])
The method for the performance evaluation of a homogeneous asymptotically reliable
serial production line presented here is introduced and explicitly analyzed in [14].
Define the function
1a
Q(a,N) = , a R+ , N [1, ]. (A.1)
1 aN

Two-machine lines. A two-machine, one-buer production line in steady state is equiva-

lent to a single aggregated machine characterized by



aggregation = 1 2 + 1 Q 2 ,N . (A.2)
1

Thus, the loss parameter of the equivalent aggregated machine is


2
aggregation = 2 + 1 Q ,N , (A.3)
1

where 1 and 2 are the loss parameters of the first and second machines, respectively. It
has been proved that the mean production rate X2 of a two-machine, one-buer produc-
tion line is given by


 
X2 = 1 2 + 1 Q 2 ,N + O 2
1

 (A.4)
1  2
= 1 1 + 2 Q ,N +O .
2
 A. C. Diamantidis and C. T. Papadopoulos 221

It is straightforward that


1
aggregation = 1 + 2 Q ,N . (A.5)
2

Equations (A.3) and (A.5) show that




aggregation = 1 + 2 Q 1 ,N = 2 + 1 Q 2 ,N . (A.6)
2 1

The above process can be generalized for the case of a homogeneous asymptotically reli-
able serial production line consisting of M machines and M 1 buers. Firstly, the first
two machines M1 and M2 are combined into an aggregated machine with the loss param-
eter 2 f defined by (A.3), that is,


f 2
2 = 2 + 1 Q ,N1 . (A.7)
1

The superscript f indicates that during the aggregation, we move forward (from ma-
chine M1 to machine MM ). The aggregated machine, characterized by 2 f , is now com-
bined with the third machine defined by the loss parameter 3 . The new aggregated ma-
chine is characterized by the loss parameter
 
f f 3
3 = 3 + 2 Q f ,N2 . (A.8)
2

At the ith step of this multistage aggregation process, one may obtain
 
f f i
i = i + i1 Q f ,Ni1 , (A.9)
i1

and at the final step,

 
f f M
M = M + M 1 Q f ,NM 1 . (A.10)
M 1

The estimate of the throughput obtained as a result of this aggregation is

 
f f M
XM = 1 M + M 1 Q f ,NM 1 . (A.11)
M 1

Because there is no proof that XM f is close to the real throughput of a production line
with M machines and M 1 buers, another set of iterations, this time directed backward
instead of forward, should be supplemented. This scheme is called backward aggregation
222 A DP algorithm for the buer allocation problem

and aggregates the line moving from the last machine MM to the first machine M1 . Thus
 f 
M 1
bM 1 = M 1 + M Q ,NM 1 ,
M
 f 
M 2
bM 2 = M 2 + bM 1 Q ,NM 2 , (A.12)
bM 1
 f 
j
bj = j + bj+1 Q ,N j ,
bj+1

and, at the final step,

 
1
b1 = 1 + b2 Q ,N1 . (A.13)
b2

By repeating the process and constructing a new forward aggregation based on this back-
ward aggregation, and so on, the following iterative algorithm is obtained:
 
f f bi (s)
i (s + 1) = i + i1 (s + 1)Q f ,Ni1 , i = 2,...,M,
i1 (s + 1)
 f 
j (s + 1) (A.14)
bj (s + 1) = j + bj+1 (s + 1)Q ,N j , j = 1,...,M 1,
bj+1 (s + 1)
f
s = 0,1,..., bi (0) = i , 1 (s) = 1 , bM (s) = M , s.

Procedure (A.14) generates the following two sequences of throughput estimates:

f f
XM (s) = 1 M (s),
(A.15)
b
XM (s) = 1 b1 (s).

References
[1] G. Allon, T. Raviv, and R. Y. Rubinstein, Application of the cross entropy method for buer allo-
cation problem in simulation based environment, Proceedings of the Third Aegean Interna-
tional Conference on Design and Analysis of Manufacturing Systems (Tinos Island, Greece),
2001, pp. 269278.
[2] T. Altiok, Performance Analysis of Manufacturing Systems, Springer-Verlag, New York, 1997.
[3] J. A. Buzacott and J. G. Shanthikumar, Stochastic Models of Manufacturing Systems, Prentice
Hall, New Jersey, 1993.
[4] Y. Dallery, R. David, and X. Xie, An ecient algorithm for analysis of transfer lines with unreliable
machines and finite buers, IIE Trans. 20 (1988), no. 3, 280283.
[5] Y. Dallery and S. B. Gershwin, Manufacturing flow line systems: a review of models and analytical
results, Queueing Syst. Theory Appl. 12 (1992), no. 1-2, 394.
[6] S. B. Gershwin, An ecient decomposition method for the approximate evaluation of tandem
queues with finite storage space and blocking, Oper. Res. 35 (1987), no. 2, 291305.
[7] , Manufacturing Systems Engineering, Prentice Hall, New Jersey, 1994.
 A. C. Diamantidis and C. T. Papadopoulos 223

[8] S. B. Gershwin and J. E. Schor, Ecient algorithms for buer space allocation, Ann. Oper. Res.
93 (2000), 117144.
[9] C. Heavey, H. T. Papadopoulos, and J. Browne, The throughput rate of multistation unreliable
production lines, Eur. J. Oper. Res. 68 (1993), no. 1, 6989.
[10] S. Helber, Performance Analysis of Flow Lines with Non-Linear Flow of Material, Lecture Notes
in Economics and Mathematical Systems, vol. 473, Springer-Verlag, Berlin, 1999.
[11] F. S. Hillier and R. W. Boling, Finite queues in series, with exponential or Erlang service timesa
numerical approach, Oper. Res. 15 (1967), 286303.
[12] M. A. Jafari and J. G. Shanthikumar, Determination of optimal buer storage capacities and
optimal allocation in multistage automatic transfer lines, IIE Trans. 21 (1989), no. 2, 130
135.
[13] P. Kubat and U. Sumita, Buers and backup machines in automatic transfer lines, Int. J. Prod.
Res. 23 (1985), no. 6, 12591270.
[14] J.-T. Lim, S. M. Meerkov, and F. Top, Homogeneous, asymptotically reliable serial production
lines: theory and a case study, IEEE Trans. Automat. Control 35 (1990), no. 5, 524534.
[15] C. T. Papadopoulos and T. I. Karagiannis, A genetic algorithm approach for the buer allocation
problem in unreliable production lines, International Journal of Operations and Quantitative
Management 7 (2001), no. 1, 2335.
[16] H. T. Papadopoulos and C. Heavey, Queueing theory in manufacturing systems analysis and
design: a classification of models for production and transfer lines, Eur. J. Oper. Res. 92 (1996),
no. 1, 127.
[17] H. T. Papadopoulos, C. Heavey, and J. Browne, Queueing Theory in Manufacturing Systems
Analysis and Design, Chapman & Hall, London, 1993.
[18] H. T. Papadopoulos and M. I. Vidalis, A heuristic algorithm for the buer allocation in unreliable
unbalanced production lines, Computers & Industrial Engineering 41 (2001), no. 3, 261277.
[19] S. G. Powell, Buer allocation in unbalanced three-station serial lines, Int. J. Prod. Res. 32 (1994),
no. 9, 22012217.
[20] B. A. Sevastyanov, Influence of storage bin capacity on the average standstill time of a production
line, Theory Probab. Appl. 7 (1962), 429438.
[21] D. D. Spinellis and C. T. Papadopoulos, A simulated annealing approach for buer allocation in
reliable production lines, Ann. Oper. Res. 93 (2000), 373384.
[22] D. D. Spinellis, C. T. Papadopoulos, and J. MacGregor Smith, Large production line optimization
using simulated annealing, Int. J. Prod. Res. 38 (2000), no. 3, 509541.
[23] H. Yamashita and T. Altiok, Buer capacity allocation for a desired throughput in production
lines, Proceedings of the Samos International Workshop on Performance Evaluation and
Optimization of Production Lines (Samos Island, Greece), 1997, pp. 124.

A. C. Diamantidis: Department of Product and Systems Design Engineering, University of the

Aegean, Hermoupolis, Syros 84100, Greece
E-mail address: adiama@syros.aegean.gr

C. T. Papadopoulos: Department of Product and Systems Design Engineering, University of the

Aegean, Hermoupolis, Syros 84100, Greece
E-mail address: hpap@aegean.gr
 Mathematical Problems in Engineering

Special Issue on
Modeling Experimental Nonlinear Dynamics and
Chaotic Scenarios

Call for Papers

Thinking about nonlinearity in engineering areas, up to the Guest Editors
70s, was focused on intentionally built nonlinear parts in
Jos Roberto Castilho Piqueira, Telecommunication and
order to improve the operational characteristics of a device
Control Engineering Department, Polytechnic School, The
or system. Keying, saturation, hysteretic phenomena, and
University of So Paulo, 05508-970 So Paulo, Brazil;
dead zones were added to existing devices increasing their
piqueira@lac.usp.br
behavior diversity and precision. In this context, an intrinsic
nonlinearity was treated just as a linear approximation, Elbert E. Neher Macau, Laboratrio Associado de
around equilibrium points. Matemtica Aplicada e Computao (LAC), Instituto
Inspired on the rediscovering of the richness of nonlinear Nacional de Pesquisas Espaciais (INPE), So Jos dos
and chaotic phenomena, engineers started using analytical Campos, 12227-010 So Paulo, Brazil ; elbert@lac.inpe.br
tools from Qualitative Theory of Dierential Equations,
Celso Grebogi, Center for Applied Dynamics Research,
allowing more precise analysis and synthesis, in order to
Kings College, University of Aberdeen, Aberdeen AB24
produce new vital products and services. Bifurcation theory,
3UE, UK; grebogi@abdn.ac.uk
dynamical systems and chaos started to be part of the
mandatory set of tools for design engineers.
This proposed special edition of the Mathematical Prob-
lems in Engineering aims to provide a picture of the impor-
tance of the bifurcation theory, relating it with nonlinear
and chaotic dynamics for natural and engineered systems.
Ideas of how this dynamics can be captured through precisely
tailored real and numerical experiments and understanding
by the combination of specific tools that associate dynamical
system theory and geometric tools in a very clever, sophis-
ticated, and at the same time simple and unique analytical
environment are the subject of this issue, allowing new
methods to design high-precision devices and equipment.
Authors should follow the Mathematical Problems in
Engineering manuscript format described at http://www
.hindawi.com/journals/mpe/. Prospective authors should
submit an electronic copy of their complete manuscript
through the journal Manuscript Tracking System at http://
mts.hindawi.com/ according to the following timetable:

Manuscript Due December 1, 2008

First Round of Reviews March 1, 2009
Publication Date June 1, 2009

Hindawi Publishing Corporation

http://www.hindawi.com