An algorithm for optimal buffer placement in reliable serial lines

The optima] allocation of buffer capacity in unbalanced production lines with reliable but variable workstations is a complex and little-researched topic. Analytic formulas for the throughput of these lines do not exist, so simulation is the only practical alternative for estimating throughput. Exhaustive search over all possible buffer allocations quickly becomes impractical beyond short lines and few buffers. Thus an algorithm is needed to efficiently find optimal or near-optimal allocations. We develop a simple search algorithm for determining the optimal allocation of a fixed amount of buffer capacity in an n-station serial line. The algorithm, which is an adaptation of the Spendley-Hext and Nelder-Mead simplex search algorithms, uses simulation to estimate throughput for every allocation considered. An important feature of the algorithm is that the simulation run length is adjusted during the running of the algorithm to save simulation run time when high precision in throughput estimates is not needed, and 10 ensure adequate precision when it is needed. We describe the algorithm and show that it can reliably find the known optimal allocation in balanced lines. Then we test the ability of the algorithm to find optimal allocations in unbalanced lines, first for cases in which the optimal allocation is known, and subsequently for cases in which the optimal allocation is not known. We focus particularly on lines with multiple imbalances in means and variances. In general, our algorithm proves highly efficient in finding a near-optimal allocation with short simulation run times. It also usually finds the true optimal allocation, but it is in the nature of this problem that many buffer allocations differ in throughput by small amounts that are difficult to resolve even with long simulation runs.     

A tabu search approach for buffer allocation in production lines with unreliable machines

The optimal allocation of buffers is an important research issue in designing production lines. In this study, a tabu search (TS) algorithm is proposed to find near-optimal buffer allocation plans for a serial production line with unreliable machines. The main objective is to maximize the production rate, i.e. throughput, of the line. The efficiency of the proposed method is also tested to solve buffer allocation problems with the objective of total buffer size minimization. To estimate the throughput of the line with a given specific buffer allocation, an analytical decomposition approximation method is used. The performance of the tabu search algorithm is demonstrated on existing benchmark problems. The results obtained by the TS algorithm are clearly encouraging, as the TS algorithm is much better than the other algorithms for all considered benchmark problems.     

Approximation of Flow Lines with Integrally Controlled Buffers

Production lines with integral control limits are studied in this paper. The behaviour of such lines can be shown to be approximated by that of flow lines with local buffers. The reduction of an integrally controlled line to a locally controlled one is computationally simple and accurate in the estimation of such performance measures as throughput, probabilities of buffers being full or empty and throughput time.

The advantage of such a reduction is that good techniques are available for estimating the performance of flow lines with local buffers only. Furthermore, a direct method is described for obtaining an estimate of the throughput of lines with integrally controlled buffers only. In the model used here, the product flow is continuous and the production units are unreliable. Both lifetimes and repair times of machines are distributed exponentially.     

Allocation of buffers to serial production lines with bottlenecks

The optimal placement of a predetermined amount of buffer capacity in balanced serial production lines is a well-understood problem: in lines with moderate variability, the optimal allocation involves equal numbers of buffers at each site; in lines with severe variability, the equal allocation is modified slightly to place more buffers toward the center of the line. Buffering unbalanced lines is a much less well-understood problem. We study the problem of buffering serial lines with moderate variability and a single bottleneck; i.e., a single station with a larger mean processing time than all other stations. Our analysis shows that a bottleneck station draws buffers toward it, but the optimal allocation depends on the location and severity of the bottleneck, as well as the number of buffers available. Furthermore, relatively large imbalances in mean processing times are required to shift the optimal buffer allocation away from an equal allocation. Finally, line length appears to have a relatively small effect on the optimal allocation with a given bottleneck. These results suggest that, at least for the class of lines studied here, equal buffer allocations may be optimal except in severely unbalanced lines. Furthermore, in severely unbalanced lines, throughput appears to be insensitive to the allocation of buffers.     

Joint optimization of maintenance,buffers and machines in manufacturing lines

This article considers a series manufacturing line composed of several machines separated by intermediate buffers of finite capacity. The goal is to find the optimal number of preventive maintenance actions performed on each machine, the optimal selection of machines and the optimal buffer allocation plan that minimize the total system cost, while providing the desired system throughput level. The mean times between failures of all machines are assumed to increase when applying periodic preventive maintenance. To estimate the production line throughput, a decomposition method is used. The decision variables in the formulated optimal design problem are buffer levels, types of machines and times between preventive maintenance actions. Three heuristic approaches are developed to solve the formulated combinatorial optimization problem. The first heuristic consists of a genetic algorithm, the second is based on the nonlinear threshold accepting metaheuristic and the third is an ant colony system. The proposed heuristics are compared and their efficiency is shown through several numerical examples. It is found that the nonlinear threshold accepting algorithm outperforms the genetic algorithm and ant colony system, while the genetic algorithm provides better results than the ant colony system for longer manufacturing lines.     

Performance evaluation of a make-tO-stock production line with a two-parameter-per-machine policy: the control point policy

This paper presents a decomposition method for evaluating the performance of a production line with finite buffers controlled by the Control Point Policy (CPP), a policy with two parameters per machine. (One parameter is the buffer size; the other is a local hedging point.) Policies with two parameters per machine show very good performance while remaining simple to use. However, decomposition methods have not yet been developed for their analysis. We consider a production line, with exponentially distributed processing, failure, and repair times, controlled by a CPP. We decompose this line into two-machine CPP-controlled lines, which considerably simplifies the decomposition equations. Furthermore, the information loops are then included in the building blocks, and can be solved numerically. A numerical study shows that the method is accurate.     

A new method for the placement of buffers in serial production lines

The placement of buffers in a production line is an old and well-studied problem in industrial engineering/operations research that is still relevant today. Decisions regarding the amount and placement of buffers in a production line occur repeatedly in system design. In this paper we document a new buffer placement method for serial production lines that operate under a variety of assumptions. The method uses information generated in a production line simulation, whose conceptual representation of job flow and workstation interaction can be described with a network, to place buffers in order to maximise throughput. This buffer placement method is very efficient and can be implemented in a spreadsheet. We demonstrate the effectiveness of the method by comparing our results against those produced by a genetic algorithm for buffer placement. Experiments are conducted on a variety of test cases. This new buffer placement optimisation method will permit designers to quickly and effectively evaluate many design alternatives and thus improve final production system performance.     

A stochastic model of an unreliable kanban production system

We analyze a stochastic model of a production line withk stations (machines) in series. There are finitecapacity buffers between the machines and at the end of the line. The movement of the workpieces through the line is demand-driven, i.e. we deal with a pull (kanban) production system. Processing times are assumed to be deterministic and constant. There are two sources of randomness in the model: Demand for workpieces from outside is stochastic, and the machines may break down (and then be repaired) with a given probability. A demand from outside is lost if the final buffer is empty. This system is described by a discrete-time Markov chain. The steadystate distribution is given for k=1. This is the basis of a decomposition algorithm which approximates the throughput of the line and the percentage of satisfied demand for arbitraryk. A comparison with simulation results shows that this algorithm is very accurate.     

Simulation of unbalanced buffer allocation in unreliable unpaced production lines

This article presents the results of a study investigating the performance of unpaced unreliable production lines (i.e. subject to breakdown) that are unbalanced in terms of their buffer storage sizes. Simulation is carried out for five, eight and 10 station lines with mean buffer space set at two, four and six units. Buffer capacity is allocated in different configurations for each of these lines. Performance indicators on throughput, idle time and average buffer level are analysed using a range of statistical tools, and relationships between the independent and dependent variables are determined. Overall results show that the best patterns for unreliable lines in terms of generating higher throughput rates (or lower idle times) as compared to a balanced line are those where total available buffer capacity is allocated as evenly as possible between workstations. In contrast, concentrating more buffer capacity towards the end of the line gives best average buffer level results.     

Predictive models for performance evaluation of serial production lines

An efficient predictive model is proposed for analysing the throughput rate of balanced serial production lines where all stations are identical and buffers between stations have the same capacity. The predictive model is based on the simulation data. The experimental design and analysis technique is used to conduct the simulation experiments and the regression analysis method is used to build the predictive model. The model can be applied to a wide range of values in terms of the coefficient of variation of processing times at stations, the buffer size between stations and the number of stations in a system. Comparisons are made with simulation results and previous works. The model can also be extended to account for situations where different stations have different coefficients of variation of processing times.     

PERFORMANCE ANALYSIS OF A TRANSFER LINE WITH UNRELIABLE MACHINES AND FINITE BUFFERS

This paper examines the performance analysis of a transfer line with unreliable machines and finite buffers. All machines have the same processing times. We propose a new decomposition method which decomposes a line into a set of two-machine lines. A set of equations is established to find performance measures such as production rate and average buffer levels. A simple iterative algorithm is then proposed to solve these equations. We also prove that the set of decomposition equations has a unique solution and that die computation algorithm converges to this unique solution. Experimental results show that the computation algorithm leads to a good solution.     

Buffer capacity allocation for a desired throughput in production lines

In this study, we are concerned with finding the minimum-total-buffer allocation for a desired throughput in production lines with phase-type processing times. We have implemented a dynamic programming algorithm that uses a decomposition method to approximate the system throughput at every stage. We provide numerical examples to show the buffer allocation and compare the corresponding simulated throughput and its bounds with the desired throughput.     

Performance analysis of multi-server tandem queues with finite buffers and blocking

In this paper we study multi-server tandem queues with finite buffers and blocking after service. The service times are generally distributed. We develop an efficient approximation method to determine performance characteristics such as the throughput and mean sojourn times. The method is based on decomposition into two-station subsystems, the parameters of which are determined by iteration. For the analysis of the subsystems we developed a spectral expansion method. Comparison with simulation shows that the approximation method produces accurate results. So it is useful for the design and analysis of production lines.     

Optimal buffer allocation strategy for minimizing work-in-process inventory in unpaced production lines

Several researchers have previously studied the problem of allocating buffer storage to maximize the throughput of a production line for a given total amount of buffer space. In this paper we study the optimal buffer allocation problem of minimizing the average work-in-process subject to a minimum required throughput and a constraint on the total buffer space. Although these two buffer allocation problems are closely related, our results show, surprisingly, that their optimal buffer allocations have very different patterns. Specifically, we show that the optimal buffer allocations for the problem considered here generally exhibit a monotonically increasing property where an increasing amount of buffer space is assigned toward the end of the line. This monotonically increasing property generally holds for both the balanced and unbalanced lines. On the basis of our empirical results, we develop a good heuristic for selecting the optimal buffer allocations.     

Availability and Average Inventory of Balanced Assembly-Like Flow Systems

An assembly-like system is one that requires resources simultaneously from more than one input source and produces a single output. Here we consider a balanced assembly-like flow system, where an assembly machine is fed from storage buffers of two input machines that are subject to random failures, and compute its average throughput and average inventories. We also show how to optimize the buffer sizes in this system     

Modeling and Analysis of Assembly Systems with Unreliable Machines and Finite Buffers

An assembly line is a tree-structured manufacturing system in which some machines perform assembly operations. In this paper, we consider assembly lines with the following features: every operation is performed in a fixed amount of time, machines are unreliable, and buffers have finite capacity. Usually, the times to failures of machines are much larger than the processing times. This allows us to approximate the behavior of these systems by a continuous flow model. The behavior of this model is then analyzed using a decomposition technique which is an extension of an earlier technique proposed in the case of transfer lines. An efficient algorithm for calculating performance measures such as production rate and average buffer levels is derived. Experimental results are provided showing mat this approximate method is quite accurate.     

Queuing network analysis approach for estimating the sizes of the time buffers in Theory of Constraints-controlled production systems

The present paper describes an open queuing network modelling approach to estimate the size of the time buffers in production systems controlled by the Theory of Constraints philosophy. Workstations in the production network are modelled as GI/G/m queues and a queuing network analysis multiproduct open queuing network modelling method is used to estimate the average flow time to the time buffer origin and the standard deviation of flow time. Using these two values together with an assumption of normally distributed flow times and a chosen service level, the final time buffer length is determined. The queuing network analysis method has been modified to enable the modelling of production networks with machine failures, batch service and varying transfer batch sizes. The modelling approach has also been incorporated in a computerized tool that uses product specific information such as bill-of-material and routing data, and production network information such as resource data to estimate the sizes and location of the necessary time buffers for each product. Simulation experiments indicate that the procedure is sufficiently accurate to provide an initial quick estimate of the needed time buffer lengths at the design stage of the line.     

How lean can lean buffers be?

This paper provides a quantitative characterization of the smallest, i.e., lean, buffer capacity necessary and sufficient to attain a desired throughput in serial production lines with identical exponential machines. The development is carried out in terms of normalized buffer capacity and production line efficiency. The smallest normalized buffer capacity required to ensure the desired line efficiency is referred to as the Lean Level of Buffering (LLB). Exact formulas for the LLB in two- and three-machine lines are presented and an approximate expression for the LLB in lines with more than three machines is derived. Along with these analytical results, several qualitative insights into the nature of lean buffering in serial production lines are presented.     

Performance evaluation of production lines with finite buffer capacity producing two different products

This paper presents an approximate analytical method for the performance evaluation of a production line with finite buffer capacity, multiple failure modes and multiple part types. This paper presents a solution to a class of problems where flexible machines take different parts to process from distinct dedicated input buffers and deposit produced parts into distinct dedicated output buffers with finite capacity. This paper considers the case of two part types processed on the line, but the method can be extended to the case of n part types. Also, the solution is developed for deterministic processing times of the machines which are all identical and are assumed to be scaled to unity. The approach however is amenable of extension to the case of inhomogeneous deterministic processing times. The proposed method is based on the approximate evaluation of the performance of the k-machine line by the evaluation of 2(k-1) two-machine lines. An algorithm inspired by the DDX algorithm has been developed and the validation of the method has been carried out by means of testing and comparison with simulation. Correspondence to: T. Tolio     

Event-driven model of unreliable production lines with storage

We have developed an event-driven algorithm for simulating a factory production line with storage. Using this algorithm a production line, with an arbitrary number of machines each processing items at different rates and with buffers of any size, can be modelled efficiently. The algorithm is based on computing the time to the next event for each buffer and machine, where the events are: a buffer becomes full, a buffer becomes empty, a machine fails and a machine is repaired. By collapsing the production line to exclude empty buffers that stay empty and full buffers that stay full, piece-by-piece computation is avoided. Computation time is reduced further by updating a buffer only when the input or output rate of that buffer changes or when the state of that buffer changes. The implementation of this model is compared to a piece-by-piece simulator.