Optimal buffer allocation in production lines

The optimal allocation of buffers in production lines is an important research issue in the design of a manufacturing system. We present a new hybrid algorithm for this complex design problem: the hybrid Nested Partitions (NP) and Tabu Search (TS) method. The Nested Partitions method is globally convergent and can utilize many of the existing heuristic methods to speed up its convergence. In this paper, we incorporate the Tabu Search heuristic into the NP framework and demonstrate through numerical examples that using the hybrid method results in superior solutions. Our numerical results illustrate that the new algorithm is very efficient for buffer allocation problems in large production lines.     

Automated flow lines with shared buffer

The paper addresses the problem of fully using buffer spaces in manufacturing flow lines. The idea is to exploit recent technological devices to move in reasonable times pieces from a machine to a common buffer area of the system and vice versa. In such a way machines can avoid their blocking since they can send pieces to the shared buffer area. The introduction of the buffer area shared by all machines of the system leads to an increase of production rate as demonstrated by simulation experiments. Also, a preliminary economic evaluation on a real case has been carried out to estimate the profitability of the system comparing the increase of production rate, obtained with the new system architecture, with the related additional cost. Correspondence to: A. Matta     

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.     

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.     

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.     

A stochastic programming model for resequencing buffer content optimisation in mixed-model assembly lines

In mixed-model assembly lines, smooth operation of the assembly line depends on adherence to the scheduled sequence. However, during production process, this sequence is altered both intentionally and uninstentionally. A major source of unintentional sequence alteration in automobile plants is the paint defects. A post-paint resequencing buffer, located before the final assembly is used to restore the altered sequence. Restoring the altered sequence back to the scheduled sequence requires three distinct operations in this buffer: Changing the positions (i.e. resequencing) of vehicles, inserting spare vehicles in between difficult models and replacing spare vehicles with paint defective vehicles. We develop a two-stage stochastic model to determine the optimal number of spare vehicles from each model-colour type to be placed into the Automated Storage and Retrieval System resequencing buffer that maximises the scheduled sequence achievement ratio (SSAR). The model contributes to the literature by explicitly considering above three distinct operations and random nature of paint defect occurrences. We use sample average approximation algorithm to solve the model. We provide managerial insights on how paint entrance sequence, defect rate and buffer size affect the SSAR. A value of stochastic solution shows that the model significantly outperforms its deterministic counterpart.     

The buffer allocation problem for general finite buffer queueing networks

The Buffer Allocation Problem (BAP) is a difficult stochastic, integer, nonlinear programming problem. In general, the objective function and constraints of the problem are not available in a closed form. An approximation formula for predicting the optimal buffer allocation is developed based upon a two-moment approximation formula involving the expressions for M/ M/1/ K systems. The closed-form expressions of the M/ M/1/ K and M/ G/1/ K systems are utilized for the BAP in series, merge, and splitting topologies of finite buffer queueing networks. Extensive computational results demonstrate the efficacy of the approach.     

Analysis of serial production lines: characterisation study and a new heuristic procedure for optimal buffer allocation

Buffer allocation in serial production lines is one of the important design issues, and hence it has been studied extensively in the literature. In this paper, we analyse the problem to characterise the optimal buffer allocation; specifically, we study the cases with single and multiple bottleneck stations under various experimental conditions. In addition, we develop an efficient heuristic procedure to allocate buffers in serial production lines to maximise throughput. The results of the computational experiments indicate that the proposed algorithm is very efficient in terms of both solution quality and CPU time requirements. Moreover, the characterisation study yields interesting findings that may lead to important practical implications. A comprehensive bibliography is also provided in the paper.     

A fast algorithm for buffer allocation problem

In this paper, we address the problem of seeking optimal buffer configurations in unreliable production lines with the objective of maximising their production rates. A fast algorithm is proposed for solving the problem. The key idea is to decompose a long production line into a set of overlapping three-machine two-buffer systems. The performance of the algorithm is demonstrated by a comparison with the degraded ceiling (DC) algorithm. Numerical results show that the proposed algorithm is almost as accurate as the DC algorithm, but it is much faster, especially for long production lines.     

Analysis of flow lines with Cox-2-distributed processing times and limited buffer capacity

We describe a flow line model consisting of machines with Cox-2-distributed processing times and limited buffer capacities. A two-machine subsystem is analyzed exactly and a larger flow lines are evaluated through a decomposition into a set of coupled two-machine lines. Our results are compared to those given by Buzacott, Liu and Shantikumar for their Stopped Arrival Queue Modell.The author thanks the anonymous referees for their helpful comments and suggestions.     

Worker allocation in lean U-shaped production lines

U-shaped lines are widely used in lean systems. In U-shaped production lines, each worker handles one or more machines on the line: the worker allocation problem is to establish which machines are handled by which worker. This differs from the widely-investigated U-line assembly line balancing problem in that the assignment of tasks to line locations is fixed. This paper address the worker allocation problem for lean U-shaped production lines where the objectives are to minimize the quantity of workers and maximize full work: such allocations provide the opportunity to eliminate the least-utilized worker by improving processes accordingly. A mathematical model is developed: the model allows for any allocation of machines to workers so long as workers do not cross paths. Walking times are considered, where workers follow circular paths and walk around other worker(s) on the line if necessary. A heuristic algorithm for tackling the problem is developed, along with a procedure representing the ‘traditional’ approach of constructing standard operations routines. Computational experiments considering three line sizes (up to 20 machines) and three takt time levels are performed. The results show that the proposed algorithm both improves upon the traditional approach and is more likely to provide optimal solutions.     

Balancing stochastic two-sided assembly lines

In a two-sided assembly line, tasks can be executed simultaneously on both sides of the line. One task cannot be started until both of its direct predecessors on the left and right sides are completed. Therefore, the start time of the task is the maximum of the two predecessors’ finish times. In many realistic situations, it is assumed that the task times are independent and normally distributed with known means and variances. However, the maximum of two normal variables is not normally distributed, but can be well approximated by results from extreme value theory. In this paper, we utilise these results to develop a solution methodology to balance two-sided assembly lines with stochastic task times, minimising the line length and the number of stations while guaranteeing all tasks are completed within the cycle time with a given confidence level.     

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 segmentation approach for solving buffer allocation problems in large production systems

Buffer space allocation is an important step in production line design. In this paper, we focus on maximising the profit rate of a line subject to a production rate constraint. We describe a newly observed property of production line optimisation. The property is that the production rate constraint, if it is effective, allows an original line to be decoupled into several short lines for optimisation. An approximation method is developed from this property. Instead of optimising a long line, the method divides it into several short lines, optimises them separately and combines their optimal buffer distributions to find the optimal or near optimal buffer distribution of the original line. The method greatly improves the computation efficiency for solving buffer allocation problem for long lines, while ensuring the accuracy of the optimal buffer distribution. A heuristic explanation is proposed. Numerical experiments are provided to show the accuracy and efficiency of the method. The effect of the number and length of line segments on the performance of the method is discussed.     

An improved robust buffer allocation method for the project scheduling problem

Unpredictable uncertainties cause delays and additional costs for projects. Often, when using traditional approaches, the optimizing procedure of the baseline project plan fails and leads to delays. In this study, a two-stage multi-objective buffer allocation approach is applied for robust project scheduling. In the first stage, some decisions are made on buffer sizes and allocation to the project activities. A set of Pareto-optimal robust schedules is designed using the meta-heuristic non-dominated sorting genetic algorithm (NSGA-II) based on the decisions made in the buffer allocation step. In the second stage, the Pareto solutions are evaluated in terms of the deviation from the initial start time and due dates. The proposed approach was implemented on a real dam construction project. The outcomes indicated that the obtained buffered schedule reduces the cost of disruptions by 17.7% compared with the baseline plan, with an increase of about 0.3% in the project completion time.     

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.     

Studying unbalanced workload and buffer allocation of production systems using multi-objective optimisation

Numerous studies have investigated the effects of unbalanced service times and inter-station buffer sizes on the efficiency of discrete part, unpaced production lines. There are two main disadvantages of many of these studies: (1) only some predetermined degree of imbalance and patterns of imbalance have been evaluated against the perfectly balanced configuration, making it hard to form a general conclusion on these factors; (2) only a single objective has been set as the target, which neglects the fact that different patterns of imbalance may outperform with respect to different performance measures. Therefore, the aim of this study is to introduce a new approach to investigate the performance of unpaced production lines by using multiple-objective optimisation. It has been found by equipping multi-objective optimisation with an efficient, equality constraints handling technique, both the optimal pattern and degree of imbalance, as well as the optimal relationship among these factors and the performance measures of a production system can be sought and analysed with some single optimisation runs. The results have illustrated that some very interesting relationships among the key performance measures studied, including system throughput, work-in-process and average buffer level, could only be observed within a truly multi-objective optimisation context. While these results may not be generalised to apply to any production lines, the genericity of the proposed simulation-based approach is believed to be applicable to study any real-world, complex production lines.     

Variability modelling and balancing of stochastic assembly lines

In a production flow line with stochastic environment, variability affects the system performance. These stochastic nature of real-world processes have been classified in three types: arrival, service and departure process variability. So far, only service process – or task time – variation has been considered in assembly line (AL) balancing studies. In this study, both service and flow process variations are modelled along with AL balancing problem. The best task assignment to stations is sought to achieve the maximal production. A novel approach which consists of queueing networks and constraint programming (CP) has been developed. Initially, the theoretical base for the usage of queueing models in the evaluation of AL performance has been established. In this context, a diffusion approximation is utilised to evaluate the performance of the line and to model the variability relations between the work stations. Subsequently, CP approach is employed to obtain the optimal task assignments to the stations. To assess the effectiveness of the proposed procedure, the results are compared to simulation. Results show that, the procedure is an effective solution method to measure the performance of stochastic ALs and achieve the optimal balance.