# Heuristics for the Buffer Allocation Problem with Collision Probability Using Computer Simulation

Authors: Eishi Chiba
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The standard manufacturing system for Flat Panel Displays (FPDs) consists of a number of pieces of equipment in series. Each piece of equipment usually has a number of buffers to prevent collision between glass substrates. However, in reality, very few of these buffers seem to be used. This means that redundant buffers exist. In order to reduce cost and space necessary for manufacturing, the number of buffers should be minimized with consideration of possible collisions. In this paper, we focus on an in-line system in which each piece of equipment can have any number of buffers. In this in-line system, we present a computer simulation method for the computation of the probability of a collision occurring. Based on this method, we try to find a buffer allocation that achieves the smallest total number of buffers under an arbitrarily specified collision probability. We also implement our proposed method and present some computational results.


---

## Body

## 1. Introduction

Reflecting the increasing demand for Flat Panel Displays (FPDs) such as LCDs and plasma display panels, more effective methods for their manufacture are required. Production rate is continually improving with technological advances such as the rapid enlargement of glass substrates and the miniaturization of patterns. Accordingly, production lines have to be modified to accommodate such advances, and new optimization problems to be solved continue to arise. One introduction in the production line of FPDs is an advanced system calledCrystal Flow [1]. It targets a higher level of line control in next-generation production processes as well as in existing lines.The main flow of the FPD process is shown in Figure1 [2]. Each piece of processing equipment in Figure 1 has a specialized role, such as cleaning, coating, proximity exposing, developing, etching, and resist stripping, and those pieces of equipment are connected in-line. Each piece of equipment usually has a number of buffers. Most production lines adopt a simple strategy to feed glass substrate into the first piece of equipment at a constant interarrival time, this being called thetact time. This strategy is simple and enables us to estimate the number of products that can be manufactured in a given time.Figure 1
FPD process flow.Due to solution foaming, chemicals, heat treating, and so forth, the processing time at each piece of equipment is uncertain and may vary according to the conditions at that time. If a sheet of substrate is sent to a piece of equipment that is still processing a previously sent sheet of substrate, that newly sent sheet can wait at a buffer in front of the piece of equipment. However, if, at that time, all buffers in front of the piece of equipment are occupied by previously sent sheets, there will be no buffer for the newly sent sheet to wait in. This phenomenon is called acollision between substrates. Collisions should be avoided whenever possible because glass substrate is expensive and fragile. Moreover, stopping the active system in the middle of production due to a collision could result in a significant increase in cost.In the field of scheduling theory, a collision-like phenomenon is called ablocking in the flow shop model and is studied as an important factor to determine line efficiency. If the processing time is deterministic, many study results on blocking exist (see extensive survey in [3]). If the processing time is stochastic, study results are somewhat limited in comparison with their deterministic counterparts. For example, see [4, 5], where the purpose is to minimize the expected makespan. On the other hand, in queueing theory, depending on the rule for processing blockings (blocked calls cleared, blocked calls delayed, etc.), previous work mainly focused on performance measures in the steady state. In fact, we can find a lot of research on this in the field of queuing theory, for example, in [6–8].In this paper, given the number of jobs to be processed in the prescribed tact time span, we focus on the measure recently presented in [9], which is the probability that there will be at least one collision, called the collision probability. In a comparatively new manufacturing system such as one manufacturing FPDs, the evaluation item (i.e., collision probability) is the new focus of observation.The probability density function (pdf) of actual processing time is often represented by a bell-like curve such as in Figure2(e). The pdf of normal distribution is also bell-shaped, but it has a weakness in that the pdf takes positive values in the negative domain, which is not true in the pdf of actual processing time. Therefore, in this paper, we assume that the processing time follows an Erlang distribution.Figure 2
The pdf of the Erlang distribution: (a)k
=
1, λ
=
1 (exponential distribution); (b) k
=
2, λ
=
2; (c) k
=
5, λ
=
5; (d) k
=
10, λ
=
10; (e) k
=
30, λ
=
30.The pdf of Erlang distribution is defined as follows:(1)
f
x
;
k
,
λ
=
λ
k
x
k
-
1
e
-
λ
x
k
-
1
!
for
x
≥
0
,where two parameters λ and k are a positive real number and a positive integer, respectively. Its expectation and variance are given by k
/
λ and k
/
λ
2, respectively. Therefore, under Erlang distribution, we can set the expectation and the variance independently of each other by setting parameters λ and k appropriately. In Figure 2, five different probability density functions are plotted, where expectations of all cases are the same (i.e., one), but their variances decrease through cases (a)–(e) in Figure 2. Some of these pdfs are bell-shaped, and the pdf of Erlang distribution takes a value of zero for x
<
0. Thus, Erlang distribution is flexible enough to represent actual processing times.For the in-line machines model without buffers, studies on collision probability have been conducted. The evaluation item (i.e., collision probability) in the in-line machines model was first presented in [9]. It was shown in [9] that the collision probability can be approximately expressed by a multiple integration, assuming that the processing time of each piece of equipment follows general distribution. If the processing time follows Erlang distribution, a closed form formula of the approximate collision probability is derived without using any multiple integration [10]. A computer simulation method for computing the collision probability was also presented in [9]. This method can compute the probability for the processing time of general distribution. Note that those results obtained in [9, 10] do not consider buffers; that is, the number of buffers is assumed to be zero. In contrast, the in-line machine model in this paper considers buffers.In a real FPD production line, in order to avoid collision between substrates, a number of buffers are placed in front of each piece of equipment. However, in reality, very few buffers seem to be used, and a large amount of money and space is wasted due to those that are not used. In designing an actual line, the number of buffers is often decided in advance from past experience. To the best of the authors’ knowledge, no theoretical literature exists on the appropriate number of buffers to be used. Therefore, our research focuses on finding an optimal value for the number of buffers.In this paper, we generalize the in-line machines model in [9, 10] to accommodate buffers. We present a computer simulation method for computing the collision probability in the model, in which each piece of equipment has an arbitrary number of buffers. This method is efficient as it computes in linear time whether a collision occurs or not at each piece of equipment. Next, we parameterize the collision probability and try to find a buffer allocation that achieves the smallest total number of buffers under an arbitrarily specified collision probability. The optimization problem is henceforth referred to asthe buffer allocation problem with collision probability. Next, we present heuristics for this problem, characterized in that it computes a locally optimal solution. Finally, we implement the heuristics and confirm its performance from computational experimentation.The remainder of this paper is organized as follows. In Section2, we describe a formal model for the production line of FPDs. Then we formulate our problem as an optimization problem. In Section 3, we consider how to derive start and finish times of each job at each piece of equipment, with each piece of equipment having an infinite number of buffers. In Section 4, we present a computer simulation method to evaluate the exact collision probability. In Section 5, based on the simulation method, we present heuristics to minimize the total number of buffers. In Section 6, we give some computational results and confirm that the heuristics computes good solutions in realistic computation time. Finally, Section 7 concludes this paper.


## 2. Model and Problem Formulation

We describe a formal model for the production line of FPDs. The following notations are used:(i)
M
1
,
M
2
,
…
,
M
m: m different pieces of equipment in series. Each piece of equipment performs a dedicated role.
(ii)
J
1
,
J
2
,
…
,
J
n: n jobs to be processed.
(iii)
T
i
(
j
)
(
>
0
): processing time of job J
i at M
j.
(iv)
t
t
a
c
t
(
>
0
): tact time, that is, the time difference between the start time instants of J
i and J
i
+
1 for all 1
≤
i
≤
n
-
1 at the entrance to the line.
(v)
b
j
(
∈
Z
+
): the number of buffers in front of M
j, where Z
+ denotes the nonnegative integer set.The in-line machines model is illustrated in Figure3. With the same time interval, t
t
a
c
t, jobs are fed one by one into the line at the entrance. Each job is first processed on piece of equipment M
1. It is then automatically transported to the next piece of equipment M
2 after it has been finished on M
1. It is assumed, for simplicity, that the transportation time between pieces of equipment is nil. As soon as M
2 receives the job, it starts processing. In this manner, each job is processed on consecutive pieces of equipment in the order M
1
,
M
2
,
…
,
M
m and then sent to the exit. Moreover, we assume that the processing time T
i
(
j
) at M
j is a random variable that follows Erlang distribution with parameters λ
j and k
j, and all T
i
(
j
) (1
≤
i
≤
n, 1
≤
j
≤
m) are independent of each other.Figure 3
In-line machines model with buffers, whereb
1
=
2, b
2
=
3, and b
m
=
1.When a jobJ
i arrives at a piece of M
j, the system dynamics is as follows. If M
j is idle, it starts processing for J
i. Otherwise, if an empty buffer exists in front of M
j, then J
i waits at the buffer. When waiting, the queue discipline follows First-In-First-Out (FIFO), where all jobs are processed in the same order as they arrive in the queue. Since the number of buffers in front of M
j is b
j, the length of the queue can be, at most, b
j. In Figure 3, b
1
=
2, b
2
=
3, and b
m
=
1. When all buffers in front of M
j are occupied (i.e., the length of the queue in front of M
j is b
j), if J
i arrives at M
j, then a collision occurs. Thecollision probability is the probability that there will be at least one collision.The sequence of the number of buffers in front of each piece of equipment, that is,(
b
1
,
b
2
,
…
,
b
m
), is called abuffer allocation. It is calledfeasible if the collision probability is less than or equal to a given value α. Then our problem, that is,buffer allocation problem with collision probability (BAP-CP), is stated as follows. Given the number of jobs n, the number of pieces of equipment m, the tact time t
t
a
c
t, the parameters of the Erlang distribution for each piece of equipment, and α
(
0
≤
α
≤
1
) (specifying the collision probability), minimize the objective function B
=
∑
j
=
1
m
‍
b
j (i.e., total number of buffers) over the set of all feasible buffer allocations. Anoptimal buffer allocation is a feasible buffer allocation that achieves the smallest objective value.


## 3. Scheduling When the Number of Buffers Is Infinite

We consider a schedule under the assumption that the number of buffers in front of each piece of equipment is infinite. The schedule is a mappingJ
i
↦
(
s
t
i
(
j
)
,
f
t
i
(
j
)
:
1
≤
j
≤
m
), where the variables s
t
i
(
j
) and f
t
i
(
j
) are defined as follows:(i)
s
t
i
(
j
): time instant when job J
i is started on M
j,
(ii)
f
t
i
(
j
): time instant when job J
i is finished on M
j.Suppose that processing timeT
i
(
j
) is equal to t
i
(
j
) for 1
≤
i
≤
n, 1
≤
j
≤
m. Then, using processing times t
i
(
j
), we can compute a schedule as follows. J
i is started on M
j after the completion of two events, these being (i) J
i is finished on M
j
-
1 and (ii) J
i
-
1 is finished on M
j. After J
i is started on M
j, it is finished in t
i
(
j
) unit times. Moreover, we can consider that each J
i is finished on M
0 at the time instant (
i
-
1
)
t
t
a
c
t since each job is fed into the line at the entrance with t
t
a
c
t interval. Therefore, the following recursive expressions hold:(2)
s
t
i
j
=
max
⁡
f
t
i
j
-
1
,
f
t
i
-
1
j
1
≤
i
≤
n
,
1
≤
j
≤
m
,
f
t
i
j
=
0
i
=
0
,
1
≤
j
≤
m
,
i
-
1
t
tact
1
≤
i
≤
n
,
j
=
0
,
s
t
i
j
+
t
i
j
1
≤
i
≤
n
,
1
≤
j
≤
m
.From (2), the time complexity for computing the schedule is O
(
m
n
), as filling each entry requires O
(
1
) time. The obtained schedule is used to compute the collision probability in the next section.


## 4. Computing the Collision Probability

The number of buffers should be minimized in order to reduce the cost and space needed for manufacturing. However, the larger the decrease in the number of buffers is, the more the collision probability increases. A trade-off between them exists. When considering this trade-off, it is important to evaluate the collision probability under a given buffer allocation. Using the schedule obtained in the previous section, we present a simulation method to evaluate the exact collision probability.Definition 1.
A waiting sequence in front ofM
j is a subsequence of jobs (
J
p
,
J
p
+
1
,
…
,
J
q
) for some 2
≤
p
≤
q
≤
n such that(3)
f
t
k
j
-
1
<
f
t
p
-
1
j
,for all k
=
p
,
p
+
1
,
…
,
q. A waiting sequence (
J
p
,
J
p
+
1
,
…
,
J
q
) in front of M
j is called maximal if adding any job (J
p
-
1 or J
q
+
1) would destroy that property. A maximal waiting sequence (
J
p
,
J
p
+
1
,
…
,
J
q
) in front of M
j, such that its length (i.e., q
-
p
+
1) is the largest over all maximal waiting sequences in front of M
j, is called maximum.Thef
t
k
(
j
-
1
)
<
f
t
p
-
1
(
j
) in Definition 1 means that M
j is still processing J
p
-
1 when each J
k (k
=
p
,
…
,
q) arrives at M
j from M
j
-
1. Therefore, all jobs in the waiting sequence will wait at the buffers in front of M
j. However, a collision occurs if the length of the waiting sequence is larger than the number of buffers b
j. In other words, when the length of the maximum waiting sequence in front of M
j is lower than or equal to b
j, no collision will occur in front of M
j.Using the example shown in Figure4, we consider an efficient method to compute whether a collision at M
j occurs or not. In Figure 4, each f
t
i
(
j
-
1
) and f
t
i
(
j
)
(
i
=
1,2
,
…
,
n
) is given. When M
j is processing J
i, a waiting sequence in front of M
j can be computed as follows. Starting from k
=
i, k is incremented by one for each successive k. If the condition f
t
k
(
j
-
1
)
<
f
t
i
(
j
) is true, the waiting sequence in front of M
j is (
J
i
+
1
,
…
,
J
k
). Therefore, if the length of the sequence (i.e., k
-
i) is larger than b
j, then a collision occurs; otherwise, k is incremented by one. On the other hand, if the condition f
t
k
(
j
-
1
)
<
f
t
i
(
j
) is false, J
i is finished on M
j before J
k arrives at M
j. Therefore, when M
j is processing the next job J
i
+
1 (i is incremented by one), we compute a waiting sequence in front of M
j. Note that, throughout this computation, the values of k and i are never decreased, and either k or i is incremented by one after the evaluation of the condition. Therefore, we can compute whether a collision at M
j occurs or not in at most 2
n evaluations of the condition. In Figure 4, the waiting sequence (
J
3
,
J
4
,
J
5
,
J
6
,
J
7
) is maximum. Therefore, the value of b
j needs to be at least five to avoid a collision.Figure 4
An example of the schedule atM
j
-
1 and M
j when n
=
8. The broken lines correspond to evaluations of the condition f
t
k
(
j
-
1
)
<
f
t
i
(
j
).From the above discussion, Pseudocode1 computes whether a collision at M
j occurs or not. The computation time is O
(
n
).Pseudocode 1
Function COLLISION_CHECK(
M
j
)
Input:   f
t
i
(
j
-
1
), f
t
i
(
j
)  (
1
≤
i
≤
n
) obtained from (2)
the number of jobsn, and the number of buffers b
j.
Question: Does at least one collision occur at M
j?
(1)  i
:
=
1
;
k
:
=
1;
(2)  while (i
≤
n && k
≤
n)
(3)   if (f
t
k
(
j
-
1
)
<
f
t
i
(
j
))
(4)    if (b
j
<
k
-
i) return  j;// Collision occurs at M
j.
(5)    else  k
:
=
k
+
1;
(6)     else  i
:
=
i
+
1;
(7)
(8)  return 0;// Collision does not occur at M
j.Using COLLISION_CHECK(
M
j
), we can compute the collision probability in the in-line machines model as follows.Algorithm 2 (SIMULATE).
Input. The input is the number of jobs n, the number of pieces of equipment m, the number of buffers b
j for all 1
≤
j
≤
m, the tact time t
t
a
c
t, the parameters of the Erlang distribution for each piece of equipment, and a positive integer c (specifying the number of iterations, which is related to the accuracy for the collision probability).Output. The output is the collision probability.Step 1.
l
o
o
p
≔
1.Step 2.
Generate processing timest
i
(
j
)
(
1
≤
i
≤
n
,
1
≤
j
≤
m
) randomly from the Erlang distribution.Step 3.
Compute the schedule of each job using (2).Step 4.
Evaluate whether a collision occurs at anyM
j by calling COLLISION_CHECK(
M
j
) for each j
=
1
,
…
,
m. Let l
o
o
p
≔
l
o
o
p
+
1. If l
o
o
p
≤
c, return to Step 2; otherwise go to Step 5.Step 5.
Output the collision probability (the number of collisions evaluated in Step 4)/
c.For Steps 2, 3, and 4 in SIMULATE, the computation time isO
(
m
n
). Since Steps 2, 3, and 4 are repeated c times, the computation time of SIMULATE is O
(
c
m
n
).


## 5. Heuristics for BAP-CP

In this section, we present heuristics for BAP-CP. The heuristics is composed of three stages. Stage1 computes a buffer allocation (
b
1
¯
,
b
2
¯
,
…
,
b
m
¯
) such that the collision probability is almost exactly zero from simulation. Therefore, the buffer allocation corresponds to an approximate upper bound on the optimal buffer allocation (
b
1
∗
,
b
2
∗
,
…
,
b
m
∗
). In other words, b
j
∗
≤
b
j
¯ is assumed for each j.Stage 1.
Compute the buffer allocation(
b
1
¯
,
b
2
¯
,
…
,
b
m
¯
).Step 1.
l
o
o
p
≔
1, b
j
¯
≔
0 for each j
=
1
,
…
,
m.Step 2.
Generate processing timest
i
(
j
)
(
1
≤
i
≤
n
,
1
≤
j
≤
m
) randomly from the Erlang distribution.Step 3.
Compute the schedule of each job using (2).Step 4.
Compute the length of the maximum waiting sequence in front of each piece of equipment. For eachM
j, if the length of the maximum waiting sequence is greater than b
j
¯, update the value of b
j
¯ to this length. Let l
o
o
p
≔
l
o
o
p
+
1. If l
o
o
p
≤
c
′, return to Step 2.Stage1 is similar to SIMULATE. At Step 4 in Stage 1, the length of the maximum waiting sequence in front of M
j can be computed in a way similar to COLLISION_CHECK(
M
j
). Specifically, Steps 4 and 5 in COLLISION_CHECK(
M
j
) are rewritten as follows. When the condition f
t
k
(
j
-
1
)
<
f
t
i
(
j
) is true, the length of the waiting sequence is k
-
i. Therefore, the maximum value of k
-
i throughout the while loop corresponds to the length of the maximum waiting sequence in front of M
j. Thus, the length can be computed in linear time. At Step 4 in Stage 1, the c
′ is a positive integer constant for the computation of the buffer allocation (
b
1
¯
,
b
2
¯
,
…
,
b
m
¯
). The value of c
′ is related to the accuracy for the buffer allocation (
b
1
¯
,
b
2
¯
,
…
,
b
m
¯
).Stage2 computes a feasible buffer allocation (
b
1
,
b
2
,
…
,
b
m
) for BAP-CP. From Stage 1, the upper bound b
j
¯ on the number of buffers b
j for each j is obtained. Therefore, we search for the value of b
j for each j between 0 and b
j
¯, inclusive. For this, two variables l
e
f
t
j and r
i
g
h
t
j for each j are used, these being lower and upper bounds on b
j, respectively.Stage 2.
Compute the feasible buffer allocation(
b
1
,
b
2
,
…
,
b
m
).Step 1.
l
e
f
t
j
≔
0, r
i
g
h
t
j
≔
b
j
¯ for each j
=
1
,
…
,
m.Step 2.
b
j
≔
0 for each j
=
1
,
…
,
m.Step 3.
With the current buffer allocation(
b
1
,
b
2
,
…
,
b
m
), compute the collision probability α
′ by using SIMULATE. Throughout SIMULATE, record the index k of M
k at which the most collisions occur.Step 4.
Ifα
<
α
′ holds for the given collision probability α, then l
e
f
t
k
≔
b
k, b
k
≔
(
l
e
f
t
k
+
r
i
g
h
t
k
)
/
2, and return to Step 3.In Stage2, starting from b
j
=
0 for each j, the value of each b
j is increased until the current buffer allocation is feasible. When increasing the value of each b
j, we take a greedy approach. This means that the value of b
k is increased for M
k, the machine at which the most collisions occur. For the computation, the return value of COLLISION_CHECK(
M
j
) corresponds to the index of the piece of equipment at which a collision occurs. Note that the value of each b
j does not decrease throughout Stage 2. This may result in an excessive number of buffers for each M
j. To remedy this, we apply Stage 3.Stage3 computes an appropriate value of each b
k using the binary search method.Stage 3.
Improve the buffer allocation(
b
1
,
b
2
,
…
,
b
m
) computed in Stage 2.Step 1.
k
≔
1.Step 2.
r
i
g
h
t
k
≔
b
k.Step 3.
b
k
≔
(
l
e
f
t
k
+
r
i
g
h
t
k
)
/
2.Step 4.
With the current buffer allocation(
b
1
,
b
2
,
…
,
b
m
), compute the collision probability α
′ by using SIMULATE.Step 5.
Ifα
<
α
′, then l
e
f
t
k
≔
b
k
+
1; otherwise r
i
g
h
t
k
≔
b
k
-
1.Step 6.
Ifl
e
f
t
k
≤
r
i
g
h
t
k, return to Step 3; otherwise b
k
≔
l
e
f
t
k.Step 7.
k
≔
k
+
1. If k
≤
m, return to Step 2.The binary search for the value ofb
k corresponds to Steps 2–6. The binary search is based on the property that the collision probability decreases monotonically with the value of b
k. After performing Stage 3, the obtained buffer allocation (
b
1
,
b
2
,
…
,
b
m
) is clearly feasible, and subtracting any value from any b
k would destroy the feasibility. Therefore, the obtained buffer allocation is locally optimal.We analyze the time complexity of the heuristics. In Stage1, the computation time is O
(
m
n
) for Steps 2, 3, and 4. Since Steps 2, 3, and 4 in Stage 1 are repeated c
′ times, the computation time of Stage 1 is O
(
c
′
m
n
). Next, the computation related to Step 3 in Stage 2 obviously dominates the total computation time for Stage 2. The total number of iterations of Step 3 is O
(
log
⁡
b
1
¯
+
log
⁡
b
2
¯
+
⋯
+
log
⁡
b
m
¯
)
=
O
(
m
m
a
x
1
≤
j
≤
m
log
⁡
b
j
¯
). Since Step 3 costs O
(
c
m
n
), the total computation time of Stage 2 is O
(
c
m
2
n
m
a
x
1
≤
j
≤
m
log
⁡
b
j
¯
). Finally, the analysis for Stage 3 is the same as that of Stage 2. Therefore, the computation time of the heuristics is O
(
c
′
m
n
+
c
m
2
n
m
a
x
1
≤
j
≤
m
log
⁡
b
j
¯
).


## 6. Computational Experiment

The heuristics is implemented on a PC (CPU: Intel Core i7 4 GHz, RAM: 32 GByte, OS: Windows 8.1 Professional). Throughout all simulations, we use Mersenne Twister [11] as the pseudorandom generator, and the number of iterations is set to c
=
c
′
=
10
,
000.First, we survey the relationship betweenα (specifying the collision probability) and the total number of buffers B. For this, the number of jobs is set to n
=
100, the number of pieces of equipment is set to m
=
8, and the parameters of the Erlang distributions are set so that the expectation and variance of the processing time on each piece of equipment become equal to 1 and 0.01, respectively (i.e., k
=
100, λ
=
100 in (1)). The results obtained by the heuristics are shown in Figure 5. Figure 5 shows a tendency that the value of B decreases with an increasing value of α, clearly exhibiting the trade-off between α and B. Note that, although the value of B decreases sharply over small values of α, the value of B decreases by very small amounts when the value of α exceeds a certain threshold. Moreover, each buffer allocation shows a tendency that the values of b
j for pieces of equipment found earlier in the production line, such as M
1 and M
2, are a little larger than those for other pieces of equipment.Figure 5
The relationship betweenα and B when t
t
a
c
t
=
1.00,1.02,1.04, and 1.06. Each marker corresponds to the result obtained by the heuristics.Figure5 shows the results when t
t
a
c
t
=
1.00, 1.02, 1.04, and 1.06. We can confirm that the relationship between α and B is almost the same for each tact time, and the value of B decreases with an increasing value of t
t
a
c
t when the value of α is fixed. The CPU time necessary for computing each marker in Figure 5 is at most 90 seconds.Next, we survey the relationship between the tact timet
t
a
c
t and the total number of buffers B when α
=
0. In a real FPD production line, collisions should be avoided whenever possible. For this, the parameter α corresponding to the collision probability is set to zero. The value of n is set to 100 and 1,000. The other parameters are the same as the settings in the first computational experiment (i.e., m
=
8, k
=
100, and λ
=
100). The results obtained by the heuristics are shown in Figure 6. Figure 6(a) shows a tendency that the value of B decreases with an increasing value of t
t
a
c
t.Figure 6
(a) The relationship betweent
t
a
c
t and B when α
=
0. (b) The relationship between t
t
a
c
t and the average makespan when α
=
0. Each marker corresponds to the result obtained by the heuristics.
(a)
(b)We discuss a “good” value for tact time using Figure6. Note that the value of B decreases by very small amounts when the value of t
t
a
c
t exceeds a certain threshold t
t
a
c
t
u
p
p
e
r. In Figure 6(a), the value of t
t
a
c
t
u
p
p
e
r is about 1.2 and does not seem to depend on the value of n. The value of B should be minimized in order to reduce cost and space necessary for manufacturing. Moreover, the value of t
t
a
c
t should be minimized in order to minimize the makespan. Therefore, any value of t
t
a
c
t which is lower than or equal to the threshold t
t
a
c
t
u
p
p
e
r can be considered an effective value from the standpoint of the minimization of the value of t
t
a
c
t under small values of B.The average makespan corresponding to each marker in Figure6(a) is shown in Figure 6(b). Note that the makespan is f
t
n
(
m
), which is computed from (2). The average makespan increases with an increasing value of t
t
a
c
t when the value of t
t
a
c
t is larger than a certain threshold t
t
a
c
t
l
o
w
e
r. It can be considered that the threshold t
t
a
c
t
l
o
w
e
r is equal to the largest value of the average processing times for all pieces of equipment. In Figure 6(b), the threshold t
t
a
c
t
l
o
w
e
r is 1.0 and does not seem to depend on the value of n. On the other hand, the average makespan remains almost constant when the value of t
t
a
c
t is lower than t
t
a
c
t
l
o
w
e
r. The reason is that the length of the waiting sequence in front of M
k increases, where the expectation of the processing time at M
k is assumed to be the maximum. If there is more than one such M
k, then the index k is assumed to be the smallest index k among these M
k. As a result, the time instant s
t
i
(
k
) at M
k for each J
i is almost the same when t
t
a
c
t
<
t
t
a
c
t
l
o
w
e
r. (In the case of Figure 6(b), the value of k is one.) Therefore, any value of t
t
a
c
t which is larger than or equal to the threshold t
t
a
c
t
l
o
w
e
r can be considered an effective value, since the makespan does not improve when t
t
a
c
t
<
t
t
a
c
t
l
o
w
e
r. From the discussion related to Figure 6, any value of t
t
a
c
t between t
t
a
c
t
l
o
w
e
r and t
t
a
c
t
u
p
p
e
r can be considered one of the most effective values from the viewpoint of cost, space, and makespan necessary for manufacturing.Finally, we survey the relationship betweent
t
a
c
t and B in the cases of three types as in Table 1. The reason is that the expectation of the processing time is not always the same value for each piece of equipment in a real production line. The other parameters are as follows: n
=
100, m
=
8, and α
=
0. The results obtained by the heuristics are shown in Figure 7. From Figure 7, we could understand that there is not so much of a difference among the three types. However, Type 1’s B value is the smallest when the value of t
t
a
c
t is small. Therefore, when the value of t
t
a
c
t is small, Type 1 is the most effective, then Type 2, and finally Type 3.Table 1
The expectation of the processing time on each piece of equipment. For all types, the variance of the processing time on each piece of equipment is 0.01.
M
1
M
2
M
3
M
4
M
5
M
6
M
7
M
8
Type 1
4
4
3
3
2
2
1
1
Type 2
1
2
3
4
4
3
2
1
Type 3
1
1
2
2
3
3
4
4Figure 7
The relationship betweent
t
a
c
t and B when α
=
0. Each marker corresponds to the result obtained by the heuristics.For each type, the average makespan is almost the same whent
t
a
c
t is fixed. Throughout the three types, the average makespan is almost constant when t
t
a
c
t
≤
4 and increases with an increasing value of t
t
a
c
t when t
t
a
c
t
≥
4. The reason is that, for each type, the largest value of the average processing times for all pieces of equipment is the same (i.e., four).


## 7. Conclusions

In this paper, we considered the in-line machines model with buffers. This is a generalized model of the known model in [9, 10]. We formulated the buffer allocation problem with collision probability. The problem has applications in the design of manufacturing systems. We also presented the heuristics to solve the problem. The heuristics computes a locally optimal buffer allocation in realistic computation time. Moreover, we implemented the heuristics and showed its performance through computational experimentation. We also discussed the effective values for tact time from a practical point of view. The discussion might be useful when designing production systems.This paper presented the discussion in an in-line system. Discussion in a parallel or network system could be considered as one possible area of future work.



---

*Source: 424370-2015-05-26.xml*