الگوریتم اکتشافی برای تخصیص بافر در خطوط تولید نامتعادل غیر قابل اعتماد

In this work we investigate the buffer allocation problem (BAP) in short unbalanced production lines consisting of up to six machines that are subject to breakdowns. Times to failure are assumed exponential whereas service and repair times are allowed to follow any Erlang-k distribution (with k≥1). An algorithm that is based on the sectioning (segmentation) approach was developed which solves the BAP. This, in conjunction with a method not previously reported that determines a “good” initial solution for the buffer allocation constitutes the main contribution of the present work. The accuracy of the proposed heuristic algorithm is remarkably good and its convergence is fast making it a promising tool that can be implemented in conjunction with a fast decomposition method to solve the BAP in large production lines.

Over the years a large amount of research has been devoted to the analysis of production lines. Much of this research has concerned the design of these manufacturing systems when there is considerable inherent variability in the processing times at the various stations, a common situation with human operators/assemblers. The literature on the modeling of production lines is vast, allowing us to review only the most directly relevant studies here. For a systematic classification of the relevant works on the stochastic modeling of these and other types of manufacturing systems (e.g. transfer lines, flexible manufacturing systems (FMS) and flexible assembly systems (FAS)), the interested reader is addressed to a review paper by Papadopoulos and Heavey (1996) and some recently published books, such as Altiok, 1997, Askin and Standridge, 1993, Buzacott and Shanthikumar, 1993, Gershwin, 1994, Papadopoulos et al., 1993 and Viswanadham and Narahari, 1992. Two significant papers with efficient numerical procedures are those by Heavey et al., 1993 and Hillier and Boling, 1967 for short lines and Dallery and Frein (1993) for longer lines. The former make use of the traditional Markovian state model whereas the latter apply decomposition methods to calculate the various performance measures of the production systems. One of the key questions that the designers face in a serial production line is the buffer allocation problem (BAP), i.e. how much buffer storage to allow and where to place it within the line. This is an important question because buffers can have a great impact on the efficiency of the production line. They compensate for the blocking and the starving of the line's stations. Unfortunately, buffer storage is expensive both due to its direct cost and due to the increase of the work-in-process (WIP) inventories. Moreover, the requirement to limit the buffer storage can also be a result of space limitations in the shop floor. In Papadopoulos et al. (1993) both evaluative and generative (optimization) models are given for modeling the various types of manufacturing systems. The former are concerned with the evaluation of the various performance measures of the systems whereas the latter try to optimize these measures by determining the optimal values of the decision variables involved. This work falls into the second category. The literature on this problem again is vast. A systematic classification of the research work in this area is given in Singh, 1997 and Papadopoulos et al., 1993. The works are splitted according to the method used to solve the BAP. To our knowledge, three are the basic optimization methods: 1. Search methods. Traditional search methods such as the Hooke–Jeeves method have been applied as well as various heuristic methods. Some representative papers falling into this category are Altiok and Stidham 1983, MacGregor Smith and Daskalaki, 1988, Seong et al., 1995, Hillier and So, 1991a and Hillier and So, 1991b. 2. Dynamic programming methods. Several authors have employed the dynamic programming method for solving the BAP problem (see Kubat and Sumita, 1985, Jafari and Shanthikumar, 1989 and Yamashita and Altiok, 1997, among others). However, this method was employed in the case of a production line with synchronous transfer as defined in Papadopoulos et al. (1993), among others, where the steady-state throughput can be approximated in a closed and recursive form. Unfortunately, the dynamic programming method is not applicable to our case as this method needs a recursive formula for the throughput function and this is not possible for asynchronous transfer lines. 3. Simulation methods. These methods are evaluative rather than optimization methods. However, some authors have conducted extended simulation experiments to derive some design rules for the BAP (see for example Conway, Maxwell, McClain and Thomas 1988). Also, Ho, Eyler and Chien (1979) applied perturbation analysis in conjunction with simulation. These methods are not so efficient as simulation is time consuming and cannot be applied as an evaluation tool in conjunction with any search method. Another classification of the research work relevant to the BAP is based on whether the lines under study are balanced or unbalanced. A line is called balanced (or unbalanced) if the mean processing times at each station are equal (or unequal). Powell (1994) provided a literature review according to this scheme. Hillier's team (Hillier, So and Boling) were the pioneers who have been dealt in depth with both the performance evaluation and the BAP in production lines (see Hillier and Boling, 1967 and Hillier and Boling, 1979). Hillier, So and Boling (1993), in the case of balanced single-server station exponential lines, succeeded to reduce greatly the number of serious candidates of being the optimal buffer configurations (allocations), by using two key theoretical results: (i) the reversibility property (shown by various investigators: Muth, 1979 and Yamazaki et al., 1985, among others) and (ii) the concavity property of the throughput function. Several other researchers have considered the general question of the design of buffer storage capacity in a variety of contexts (see Sarker (1984) for a survey in this area). The majority of the existing papers deal with reliable lines, i.e. the machines at each workstation are assumed to be perfectly reliable and therefore do not fail. Only a few papers consider the assumption of unreliable stations. The reason is simple. Only a few algorithms have been developed to calculate the performance measures of unreliable production lines (see Choong and Gershwin, 1987, Gershwin, 1989, Glassey and Hong, 1983 and Heavey et al., 1993). Hillier and So, 1991a and Seong et al., 1995 have been dealt with the BAP in unreliable production lines. Only a few researchers have been dealt with the BAP in production lines with multiple (parallel) machines at each workstation (see Hillier and So, 1995, Magazine and Stecke, 1996 and Singh, 1997). A last classification scheme is given in Section 2 where the BAP is expressed in mathematical terms. This scheme is based on the type of the objective function that is used. The present work deals with the BAP in unreliable unbalanced production lines with single-machine stations. We propose a heuristic search algorithm that starts with a ‘good’ initial buffer allocation. This is found by a buffer allocation scheme that exploits the parameters of the production line. With this buffer allocation, which was found to be close enough to the optimal buffer allocation (determined by enumeration), it was observed that the convergence of the algorithm was very fast. We used this search algorithm in conjunction with the evaluative algorithm of Heavey et al. (1993) which can handle not only exponential lines but also lines with the service and repair times following the Erlang-k distribution with any k≥1 number of phases. However, this evaluative algorithm can solve only short lines in contrast to the evaluative decomposition algorithm of Glassey and Hong (1983) used by Seong et al. which solves large production lines very fast but at the expense of accuracy. The accuracy of the proposed search algorithm is remarkably good and its convergence is very fast. We believe that this algorithm could be applied in conjunction with a decomposition algorithm to solve the BAP in large production lines fast and accurately. The remainder of the paper is organized as follows. In Section 2, we describe the production line model and the problem of our interest. In Section 3, we give the solution approach and the algorithm. In Section 4, numerical results are provided which show the remarkably good accuracy of the proposed algorithm for solving the BAP. Finally, Section 5 concludes the paper and some future research directions are suggested.

In this work, we presented ‘PaVi’, an algorithm for solving the BAP in an unreliable unbalanced production line. To our knowledge, the solution of the OBA problem in general production lines has been attempted by very few researchers, so far. More specifically, only Seong et al. (1995) proposed two heuristic algorithms to solve the problem in exponential lines. In our model, the service and repair times are allowed to follow any Erlang distribution with k and m phases, respectively, whereas the times to failure are assumed to be exponential. The main contribution of the proposed algorithm relies on the determination of a “good” initial buffer vector which is found by exploiting the information about the parameters of the production line, that is, the mean service rates, μi's, the mean repair rates, ri's and the mean failure rates, βi's. Then based on this information, the stations of the line are ordered according to the value of the mean effective service rates, ρi's, starting with the bottleneck station and ending with the faster one. Some priority rules are utilized and the initial buffer capacities are determined based on a linear buffer allocation scheme, not previously reported. After the determination of the initial buffer vector, a sectioning search method is called to search for the OBA. This method searches for each variable in two directions, one buffer slot up and one down of a certain value of the decision variables, which are the buffer capacities. The optimal buffer allocation was found in almost all the cases (above 97% of the 373 experiments we have tried) and in the cases where the heuristic algorithm fails to find the OBA, the solution was near optimal. We believe that the proposed idea of using a “good” initial buffer allocation can speed up the solution to the BAP in a production line of any size. It is the evaluation tool that restricts the applicability of the proposed heuristic algorithm and not the search algorithm itself. We could not solve large production lines because we used the proposed search algorithm in combination with the exact evaluative algorithm by Heavey et al. (1993) for the calculation of the mean throughput of the lines. The latter is restricted by the computer memory and cannot solve large systems of linear equations. In general, we propose use of the ‘PaVi’ search algorithm in conjunction with the evaluative algorithm of Heavey et al. (1993) or that by Hillier and Boling (1967) for short lines (up to six stations) and of a good decomposition algorithm (say that by Choong and Gershwin (1987) or the one by Glassey and Hong (1983)) for longer production lines. This is an area for further investigation. Another area for further improvement would be to focus more on finding an even better initial solution by further exploiting our knowledge about the criticality of the unreliable stations of the line. In general, the use of a “good” initial solution is a critical point to find a fast solution. This criticality has to be quantified and used in the first step of the search algorithm. A potential alternative might be a linear approach for deriving “good” initial solutions which would reflect, for example, on the values of the stages parameters ρi's (not necessarily in a linear fashion), not just their size order. In this way, both the number of iterations will be reduced and the accuracy of the algorithm will be further improved, that is, to obtain the OBA in all cases.