http://www.dmst.aueb.gr/dds/pubs/conf/1997-Perf-Anneal/html/anneal.html This is an HTML rendering of a working paper draft that led to a publication. The publication should always be cited in preference to this draft using the following reference:
Citation(s): 3 (selected). This document is also available in PDF format. The document's metadata is available in BibTeX format. Find the publication on Google Scholar This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. |
D. Spinellis and H. T. Papadopoulos
Department of Mathematics
University of the Aegean
GR-832 00 Karlovasi, Samos
Greece
e-mail: {dspin,hpap}@aegean.gr
April, 1997
We describe a simulated annealing approach for solving the buffer allocation problem in reliable production lines. The problem entails the determination of near optimal buffer allocation plans in large production lines with the objective of maximising their average throughput. The latter is calculated utilising a decomposition method. The allocation plan is calculated subject to a given amount of total buffer slots in a computationally efficient way.
Buffer allocation is a major optimisation problem faced by manufacturing systems designers. It has to do with devising an allocation plan for distributing a certain amount of buffer space among the intermediate buffers of a production line. This problem is a very complex task that must account for the random fluctuations in mean production rates of the individual workstations of the lines. To solve this problem there is a need of two different tools. The first is a tool that calculates the performance measure of the line which has to be optimised (e.g., the average throughput or the mean work-in-process). This may be an evaluative method such as simulation or a decomposition method or the traditional Markovian state model. The second tool is a search (generative) method that tries to determine an optimal or near optimal value for the decision variables, which in our case are the buffer capacities of the intermediate buffer locations of the line. Examples of such methods are the classical search methods such as the well-known Hooke-Jeeves method, various heuristic methods, knowledge based methods, and genetic algorithms.
There are some advantages and disadvantages of the various evaluative methods used for modelling production lines. For example, simulation can handle production lines with more realistic processing times but it is a time-consuming method that cannot be utilised in conjunction with a search method that needs to apply it many times. The Markovian state model, on the other hand, provides with an exact solution of only short lines (with up to twelve stations). Besides, the processing time distribution has to be of phase-type. This is very a restrictive and unrealistic assumption, however, the method has been used to provide some insights into the problem under investigation. Finally, the decomposition method, works well for large systems (with well over than 50 stations), and it is also applicable to exponentially distributed service times. On the other hand, this method is inaccurate for short lines (with up to 10 stations).
As far as the search methods are concerned, the traditional segmentation methods (such as the well-known Hooke-Jeeves method) fail to provide with an optimal solution in all cases, whereas, the various heuristic methods reported in the literature have the advantage of being very fast but are in general also inaccurate. Lately, genetic algorithms have been applied to solve the buffer allocation problem. The accuracy and the efficiency of these algorithms have to be tested to proceed with an assessment.
For a systematic review of the existing literature in the area of evaluative and generative models of manufacturing systems, the interested reader is addressed, respectively, to two review papers by [DG92] and [PH96] and to the books by [PHB93], [AS93], [BS93], [Ger94], [Per94] and [Alt97], among others.
Although several researchers have studied the problem of optimising buffer allocation to maximise the efficiency of a reliable production line, there is no method that can handle this problem for large production lines, in a computationally efficient way (see for example, [HS91], and [HSB93]). These methods are based on comprehensive studies to characterise the optimal buffer allocation pattern. Authors have provided extensive numerical results for balanced lines with up to 6 stations and limited results for lines with up to 9 stations.
Other relevant studies are: [CMMT88], who used simulation to investigate the buffer allocation problem. [Pow92], who studied the buffer allocation problem for unbalanced production lines. [So97], who presented a heuristic method for determining a near optimal buffer allocation in production lines. The differentiation of So's work from the others was that the objective was to minimise the average work-in-process, provided a minimum required throughput is attained.
Recently, [PV97] developed a knowledge based system, called ASBA, for solving the buffer allocation problem in reliable production lines.
Furthermore, [BDI95] applied genetic algorithms for the buffer allocation in asynchronous assembly systems.
The objective of this paper is to present a search method for solving the buffer allocation problem in large reliable, balanced and unbalanced, production lines with computational efficiency. The proposed method is a simulated annealing approach that works in close cooperation with a decomposition method as given in [DF93].
Simulated annealing is an adaptation of the simulation of physical thermodynamic annealing principles described by [MRR+53] to the minimisation of combinatorial optimisation problems [KGV83,Cer85]. In common with genetic algorithms [Hol75] and tabu search techniques [Glo90] it follows the ``local improvement'' paradigm for harnessing the exponential complexity of the solution space.
The algorithm is based on randomisation techniques. An overview of algorithms based on such techniques can be found in [GSB94]. A complete presentation of the method and its applications can be found in [LA87] and accessible algorithms for its implementation are presented by [CMMR87,PFTV88]. A critical evaluation of different approaches to annealing schedules and other method optimisations are given by [Ing93].
As a tool for operational research simulated annealing is presented by [Egl90], while [KAJ94] provide a complete survey of simulated annealing applications to operations research problems.
This paper is organised as follows. Section 2 states the problem and the assumptions of the model, whereas, section 3 describes the proposed simulated annealing approach. In section 4, we provide numerical results obtained from the algorithm. Finally, section 5 concludes the paper and suggests some future research directions.
In asynchronous production lines, each part enters the system from the first station, passes in order from all stations and the intermediate buffer locations and exits the line from the last station. The flow of the parts works as follows: in case a station has completed its processing and the next buffer has space available, the processed part is passed on. Then, the station starts processing a new part that is taken from its input buffer. In case the buffer has no parts, the station remains empty until a new part is placed in the buffer. This type of line is subject to manufacturing blocking (or blocking after service) and starving.
Assumptions of the model: It is assumed that the first station is never starved and the last station is never blocked. The processing (service) times at each station are assumed to be independent random variables following the exponential distribution, with mean service rates, $\mu $_{i} , $i=1,2,\&ldots;,\; K$. In our model, the stations of the line are assumed to be perfectly reliable, that is, breakdowns are not allowed.
Figure 1 depicts a $K$-station line that has $K-1$ intermediate locations for buffers, labelled $B$_{2}, B_{3}, &ldots;, B_{K} .
The basic performance measures in the analysis of production lines are the average throughput (or mean production rate) and the average work-in-process (WIP) or equivalently the average production (sojourn) time.
The object of the present work is the buffering of asynchronous, reliable production lines with the assumptions given above. The objective is the maximisation of the line's throughput, subject to a given total buffer space.
The buffer allocation problem: In mathematical terms, our problem can be stated as follows:
$$ | (1) |
(2) |
$B=(B$_{2},B_{3},&ldots;,B_{K}) is the `buffer vector', i.e., a vector with elements the buffer capacities of the $K-1$ buffers.
$X$_{K} , denotes the average throughput of the $K$-station line. This is a function of the mean service rates of the $K$ stations, $\mu $_{i}, (i=1,2,&ldots;,K) , of the coefficients of variation, $CV$_{i} , of the service times and the buffer capacities, $B$_{i} .
Methodology of investigation: To solve the optimal buffer allocation problem (P), we have performed the following steps:
(3) |
When metals slowly cool and anneal their atoms are often ordered in the minimal energy crystalline state for distances billions of times their diameter in all directions i.e. the solid is in a state of a global minimum. During the cooling process the system can escape local minima by moving to a thermal equilibrium of a higher energy potential based on the probabilistic distribution $w$ of entropy $S$
$S\; =\; klnw$ | (4) |
$dS\; =\; \{d\xaf\; ET\}$ | (5) |
$w\; \sim exp(\{-EkT\})$ | (6) |
The application of the annealing optimisation method to other processes works by repeatedly changing the problem configuration and gradually lowering the temperature until a minimum is reached.
This can be expressed for the production line buffer allocation using the pseudocode listed in figure 3.
select an initial line configuration C_{0} and an initial temperature T_{0} repeat until no better configurations can be found repeat for a number of optimisation steps for the given temperature Configure a new line C_{n} by moving a random ammount of buffer space from one randomly selected buffer to another Calculate the energy differential Delta E between the current line configuration C and the new one C_{n} If the new line C_{n} is more efficient (Delta E < 0) or it satisfies the Metropolis criterion R < exp(-Delta E/T) for a random number R, 0 < R < 1 and an annealing temperature T then Make the new configuration C_{n} the current configuration C Lower the annealing temperature T following the cooling schedule (equation 7). |
In order to evaluate the applicability of the simulated annealing method to the buffer allocation problem we designed and implemented a system to calculate the optimum buffer configuration for a given reliable production line using a simulated annealing algorithm. The system takes as input:
The system is based on the simulated annealing algorithm as described in [PFTV88]. The authors do not clarify that, strictly described, their implementation is a simulated quenching [Ing93] algorithm as it uses an exponential cooling schedule. Our implementation, for efficiency reasons, uses the same exponential cooling schedule namely:
(7) |
$T(k)\; =\; T$_{0}{ | (8) |
In order to evaluate our method's applicability in selecting line configurations we run a number of tests on both balanced and unbalanced lines and compared the simulated annealing results against the results obtained by other methods. For short lines and limited buffer space a full enumeration of all configurations provided an accurate measure when comparing with the simulated annealing results. For larger configurations we used a reduced enumeration in order to provide the comparative measure. Both methods are subject to the reduced evaluative accuracy of the decomposition method compared to the Markovian model. In figure 4 we present the optimum throughput configurations for balanced lines found using the simulated annealing method against the throughput found using full (for 9 stations) and reduced enumeration techniques. It is apparent that the simulated annealing results follow closely the results obtained by the other methods.
Our goal for using the simulated annealing method was to test its applicability to large production line problems where the cost of other methods was prohibitevely expensive. As an example the reduced enumeration method when run on a 15 station line with a buffer capacity of 30 units took more than 10 hours to complete on a 100MHz processor. As shown in figure 6 the cost of the simulated annealing method is higher than the cost of the full and reduced enumeration methods for small lines and buffer allocations. However, it quickly becomes competitive as the number of stations and the available buffer size increase. Notice that -- in contrast to the other methods -- the simulated annealing cost does not increase together with the available buffer space and that it increases only linearly with the number of stations.
Further investigation is needed in order to fully evaluate the method's potential. The annealing schedule that we used can clearly be optimised potentially increasing both the method's accuracy and its performance. Methods such as adaptive simulated annealing [Ing89] can be tried on the problem set in order to test their applicability. The use of heuristics in setting up the initial buffer configuration can decrease the number of steps needed for reaching the optimal. Other evaluative methods such as the Markovian model can be used in place of the decomposition algorithm for determining the change differentials. Furthermore, the small nature of changes made to the configuration during the annealing process could be taken into account for optimising the evaluative procedure. Finally, we would like to test the method's potential on similar problems especially involving parallel station production lines.