The sequence-dependent assembly line balancing problem

Assembly line balancing problems (ALBP) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along the line. The sequence-dependent assembly line balancing problem (SDALBP) is an extension of the standard simple assembly line balancing problem (SALBP) which has significant relevance in real-world assembly line settings. SDALBP extends the basic problem by considering sequence-dependent task times. In this paper, we define this new problem, formulate several versions of a mixed-integer program, adapt solution approaches for SALBP to SDALBP, generate test data and perform some preliminary computational experiments. As a main result, we find that applying SALBP-based search procedures is very effective, whereas modelling and solving the problem with MIP standard software is not recommendable.     

One- and two-sided assembly line balancing problems with real-world constraints

In this study, we consider balancing problems of one- and two-sided assembly lines with real-world constraints like task or machine incompatibilities. First, we study the one-sided assembly line balancing problem (ALBP) with a limited number of machine types per workstation. Using a genetic algorithm (GA), we find optimal results for real-world instances. A set of larger test cases is used to compare two well-established solution approaches, namely GA and tabu search (TS). Additionally, we apply a specific differential evolution algorithm (DE), which has recently been proposed for the considered ALBP. Our computational results show that DE is clearly dominated by GA. Furthermore, we show that GA outperforms TS in terms of computational time, if capacity constraints are tight. Given the algorithm’s computational performance as well as the fact that it can easily be adapted to additional constraints, we then use it to solve two-sided ALBP. Three types of constraints and two different objectives are considered. We outperform all previously published methods in terms of solution quality and computational time. Finally, we are the first to provide feasible test instances as well as benchmark results for fully constrained two-sided ALB.     

Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach

In this paper, a novel stochastic two-sided U-type assembly line balancing (STUALB) procedure, an algorithm based on the genetic algorithm and a heuristic priority rule-based procedure to solve STUALB problem are proposed. With this new proposed assembly line design, all advantages of both two-sided assembly lines and U-type assembly lines are combined. Due to the variability of the real-life conditions, stochastic task times are also considered in the study. The proposed approach aims to minimise the number of positions (i.e. the U-type assembly line length) as the primary objective and to minimise the number of stations (i.e. the number of operators) as a secondary objective for a given cycle time. An example problem is solved to illustrate the proposed approach. In order to evaluate the efficiency of the proposed algorithm, test problems taken from the literature are used. The experimental results show that the proposed approach performs well.     

A genetic algorithm for the stochastic mixed-model U-line balancing and sequencing problem

Mixed-model assembly lines are widely used to improve the flexibility to adapt to the changes in market demand, and U-lines have become popular in recent years as an important component of just-in-time production systems. As a consequence of adaptation of just-in-time production principles into the manufacturing environment, mixed-model production is performed on U-lines. This type of a production line is called a mixed-model U-line. In mixed-model U-lines, there are two interrelated problems called line balancing and model sequencing. In real life applications, especially in manual assembly lines, the tasks may have varying execution times defined as a probability distribution. In this paper, the mixed-model U-line balancing and sequencing problem with stochastic task times is considered. For this purpose, a genetic algorithm is developed to solve the problem. To assess the effectiveness of the proposed algorithm, a computational study is conducted for both deterministic and stochastic versions of the problem.     

Mixed model assembly system with multiple secondary feeder lines: layout design and balancing procedure for ATO environment

The constant research for efficiency and flexibility has forced assembly systems to change from simple/single assembly lines to mixed model assembly lines, while the necessity to reduce inventory has led the transition from single to multi-line systems, where some components are assembled in secondary lines, called feeder lines, connected to the main one by a ‘pull philosophy’. A possible approach to configure such an assembly system is to balance the main line first and use the retrieved cycle time to balance each feeder line separately, which is a questionable solution, especially if operators can perform tasks on both the feeder and the main line. Moreover for its complexity the mixed model balancing problem is usually solved transforming it into a single model by creating a single ‘virtual average model’, representative of the whole production mix. The use of a virtual average model assumes that the processing times of some models are higher or lower than the cycle time, which creates overload/idle time at the stations. This approach, especially in complex multi line production systems, largely reduces the assembly line productivity and increases the buffers dimensions. This paper faces the mixed model assembly line balancing problem in the presence of multiple feeder lines, introducing an innovative integrated main-feeder lines balancing procedure in case of unpaced assembly systems. The proposed approach is compared with the classical one and validated through simulation and industrial applications.     

Analysis of the type II robotic mixed-model assembly line balancing problem

In recent years, there has been an increasing trend towards using robots in production systems. Robots are used in different areas such as packaging, transportation, loading/unloading and especially assembly lines. One important step in taking advantage of robots on the assembly line is considering them while balancing the line. On the other hand, market conditions have increased the importance of mixed-model assembly lines. Therefore, in this article, the robotic mixed-model assembly line balancing problem is studied. The aim of this study is to develop a new efficient heuristic algorithm based on beam search in order to minimize the sum of cycle times over all models. In addition, mathematical models of the problem are presented for comparison. The proposed heuristic is tested on benchmark problems and compared with the optimal solutions. The results show that the algorithm is very competitive and is a promising tool for further research.     

A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks

This paper addresses the general assembly line balancing problem where the simple version is enriched by considering sequence-dependent setup times between tasks. Recently, Andres et al. (Andres, C., Miralles, C., and Pastor, R., 2008. Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. European Journal of Operational Research, 187, (3), 1212–1223.) proposed the type I general assembly line balancing problem with setups (GALBPS-I) and developed a mathematical model and several algorithms for solving the problem. In a similar vein, we scrutinised the GALBPS type II problem where the challenge is to find the minimum cycle time for a predefined number of work stations. To solve the problem, we develop a mathematical model and a novel simulated annealing (SA) algorithm to solve such an NP-hard problem. We then employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm and make the classical SA algorithm more efficient in terms of running time and solution quality. Computational results reflected the high efficiency of the SA algorithm in both aspects.     

Balancing printed circuit board assembly line systems

This paper considers the placement of components onto printed circuit boards (PCBs) using surface mount technology. Multiple automatic placement machines, a variety of PCB types and a large volume for each PCB type characterize the environment studied. The problem addressed is that of allocating and arranging the components on several placement machines, organized into one or several assembly lines, while considering a different assembly time if components are located at different feeder locations. The one assembly line problem is equivalent to balancing a multi-model assembly line where models are assembled in small batches without component rearrangement between model changes. The objective is tominimize the weighted sum of each assembly PCBcycle time, which is defined as the maximum time a PCB has to spend on each machine. We solve this problem with Lagrangian relaxation techniques. Industrial case study results are presented. We also compare the global performance of five placement machines if they are organized as a single assembly line or broken down into two or more assembly lines.     

The type-II assembly line rebalancing problem considering stochastic task learning

Assembly lines with non-constant task time attribute are widely studied in the literature. For the SALBP-II assembly line balancing problem, we take account of stochastic task time changes, which is more practical than the deterministic times often assumed in industrial application. An algorithm – ENCORE, which leverages the traditional algorithm SALOME2, is proposed to address the assembly line balancing problem with stochastic task time attribute. Computational and statistical experiments are conducted to show the efficiency of proposed algorithms over traditional methods with regards to the improvement of total production times.     

Balancing and sequencing of stochastic mixed-model assembly U-lines to minimise the expectation of work overload time

A mixed-model assembly U-line is a flexible production system capable of manufacturing a variety of similar models, and it has become popular as an important component of the just-in-time production system. However, it poses new challenges for the optimal design of assembly lines because both the task assignment and the production sequence affect the workload variance among workstations. As a consequence, this paper addresses the line balancing problem and the model sequencing problem jointly and proposes a 0–1 stochastic programming model. In this model, task times are assumed to be stochastic variables independently distributed with normal distributions and the objective is to minimise the expectation of work overload time for a given combination of cycle time and number of workstations. To solve the problem, a simulated annealing-based algorithm is developed, which can also be used to minimise the absolute deviation of workloads in a deterministic environment. The experimental results for a set of benchmark problems show that the proposed algorithm outperforms the existing algorithms in terms of solution quality and running time.     

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.     

The assembly line worker assignment and balancing problem with stochastic worker availability

Assembly lines can be employed successfully in sheltered work centres to better include persons with disabilities in the labour market as well as to improve production efficiency. The optimal assignment of a heterogeneous workforce is known as the assembly line worker assignment and balancing problem (ALWABP). These assembly lines are characterised not only by a heterogeneous workforce, but also by high levels of absenteeism, which makes it more difficult to obtain stable and efficient line balancing solutions. In this paper, an extension of the ALWABP to minimise the expected cycle time under uncertain worker availability is proposed. We model this problem as a two-stage mixed integer program, and propose local search heuristics for solving it. Computational experiments show that stochastic modelling can help to improve the line’s efficiency and that the proposed heuristics produce good results for instances of practical size.     

Using Ant Techniques to Solve the Assembly Line Balancing Problem

This paper presents an approach, based on ant techniques, to effectively address the assembly line balancing problem with the complicating factors of parallel workstations, stochastic task durations, and mixed-models. A methodology was inspired by the behavior of social insects in an attempt to distribute tasks among workers so that strategic performance measures are optimized. This methodology is used to address several assembly line balancing problems from the literature. The assembly line layouts obtained from these solutions are used for simulated production runs so that output performance measures (such as cycle time performance) are obtained. Output performance measures resulting from this approach are compared to output performance measures obtained from several other heuristics, such as simulated annealing. A comparison shows that the ant approach is competitive with the other heuristic methods in terms of these performance measures.     

Balancing mixed-model assembly lines: a computational evaluation of objectives to smoothen workload

Mixed-model assembly lines are widely used in a range of production settings, such as the final assembly of the automotive and electronics industries, where they are applied to mass-produce standardised commodities. One of the greatest challenges when installing and reconfiguring these lines is the vast product variety modern mixed-model assembly lines have to cope with. Traditionally, product variety is bypassed during mid-term assembly line balancing by applying a joint precedence graph, which represents an (artificial) average model and serves as the input data for a single model assembly line balancing procedure. However, this procedure might lead to considerable variations in the station times, so that serious sequencing problems emerge and work overload threatens. To avoid these difficulties, different extensions of assembly line balancing for workload smoothing, i.e. horizontal balancing, have been introduced in the literature. This paper presents a multitude of known and yet unknown objectives for workload smoothing and systematically tests these measures in a comprehensive computational study. The results suggest that workload smoothing is an essential task in mixed-model assembly lines and that some (of the newly introduced) objectives are superior to others.     

Stochastic assembly line balancing using beam search

This paper presents a beam search-based method for the stochastic assembly line balancing problem in U-lines. The proposed method minimizes total expected cost comprised of total labour cost and total expected incompletion cost. A beam search is an approximate branch and bound method that operates on a search tree. Even though beam search has been used in various problem domains, this is the first application to the assembly line balancing problem. The performance of the proposed method is measured on various test problems. The results of the computational experiments indicate that the average performance of the proposed method is better than the best-known heuristic in the literature for the traditional straight-line problem. Since the proposed method is the first heuristic for the stochastic U-type problem with the total expected cost criterion, we only report its results on the benchmark problems. Future research directions and the related bibliography are also provided in the paper.     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

Two-sided U-type assembly line balancing problem

U-type and two-sided assembly lines are two types of design having advantages over traditional straight assembly lines. In this paper, a new line design hybrid of U-type and two-sided lines is presented. A bi-objective 0-1 integer programming model is developed to solve the line balancing problem of the proposed design. Zoning constraints are also considered for the proposed design. A number of test problems from the literature with up to 65 tasks are solved. Benefits of two-sided U-type lines are discussed.     

Integrated procedure of balancing and sequencing for mixed-model assembly lines: a multi-objective evolutionary approach

A mixed-model assembly line is a type of production line which is used to assemble a variety of product models with a certain level of similarity in operational characteristics. This variety causes workload variance among other problems resulting in low efficiency and line stops. To cope with these problems, a hierarchical design procedure for line balancing and model sequencing is proposed. It is structured in terms of an amelioration procedure. On the basis of our evolutionary algorithm, a genetic encoding procedure entitled priority-based multi-chromosome (PMC) is proposed. It features a multi-functional chromosome and provides efficient representation of task assignment to workstations and model sequencing. The lean production perspective recognises the U-shape assembly line system as more advanced and beneficial compared to the traditional straight line system. To assure the effectiveness of the proposed procedure, both straight and U-shape assembly lines are examined under two major performance criteria, i.e., number of workstations (or line efficiency) as static criterion and variance of workload (line and models) as dynamic criterion. The results of simulation experiments suggest that the proposed procedure is an effective management tool of a mixed-model assembly line system.     

LB-ALBP: the lexicographic bottleneck assembly line balancing problem

The classic assembly line balancing problem (ALBP) basically consists of assigning a set of tasks to a group of workstations while maintaining the tasks’ precedence relations. When the objective is to minimise the number of workstations m for a given cycle time CT, the problem is referred to as ALBP-1; if the objective is to minimise CT given m, then the problem is called ALBP-2. The only objective in ALBP-2 is to minimise CT, i.e., the workload of the most heavily loaded workstation (the bottleneck). However, considering the second-biggest, third-biggest, etc. workloads, can be important. Distributing a workload among six workstations as 10, 10, 10, 4, 3, 3, is not the same as distributing it as 10, 6, 6, 6, 6, 6. The CT value is the same, but the second distribution is beyond question more reliable and balanced. In this paper, we present and formalise a new assembly line balancing problem: the lexicographic bottleneck assembly line balancing problem (LB-ALBP). The LB-ALBP hierarchically minimises the workload of the most heavily loaded workstation (CT), followed by the workload of the second most heavily loaded workstation, followed by the workload of the third most heavily loaded workstation, and so on. We present two mixed-integer linear programming (MILP) models designed to solve the LB-ALBP optimally, together with three heuristic procedures based on these MILPs.     

Empirical evaluation of lower bounding methods for the simple assembly line balancing problem

The simple assembly line balancing problem (SALBP) is a classical problem that arises in the design of assembly lines. The objective of the SALBP is to divide the assembly work among different workstations of the assembly line in order to maximise the efficiency of the entire line. In this paper, we: (a) put forward different families of lower bounds for the SALBP; (b) introduce new lower bounds; (c) generalise previous results; and (d) analyse the performance of these lower bounding techniques in terms of solution quality using a recently proposed set of instances. An analysis of the results of these bounds leads us to: (1) improve the best-known lower bound for 104 out of the 175 open instances from the benchmark set; (2) identify the areas of applicability of different sources of bounds; and (3) identify possible uses of these bounds in other assembly line balancing problems.