A problem of buffer allocation in production lines: complexity analysis and genetic algorithms

http://www2.lifl.fr/META10/proceedings//meta20100_submission_158.pdfInternational audienceIn this paper, we consider a line with machines in series, where the parts are moved from one machine to the next by some kind of transfer mechanism. The machines are supposed to be separated by finite buffers (waiting capacities). The parts are accumulated in a buffer when the downstream machine is less productive or stopped. The machines are subject to breakdowns. When a breakdown occurs, the corresponding machine is unusable during a random repair time. The lines without buffers and the lines with infinite buffers are precisely described by analytical models. However, if the buffers are finite, the performance evaluation of line becomes much more complicated. Several approximation methods for evaluation of such lines have been proposed on the basis of aggregation [1]-[3] or decomposition [4], when the behavior of M-machine line is calculated based on the behavior of two-machine lines. In this paper, we use two-machines-one-buffer Markov model, independently developed in [5]-[7], see also [2], for each tentative buffer allocation decision, the production rate is evaluated via an aggregation algorithm [2], [3], which is similar to the Terracol and David [1] techniques. This aggregation approach appears to be sufficiently rapid for evaluation of tentative buffer allocations within the optimization algorithms. These performance evaluation techniques are connected with some genetic algorithms. The objective is to optimize the buffer allocation of such a line