A classification of assembly line balancing problems

Assembly lines are special flow-line production systems which are of great importance in the industrial production of high quantity standardized commodities. Recently, assembly lines even gained importance in low volume production of customized products (mass-customization). Due to high capital requirements when installing or redesigning a line, its configuration planning is of great relevance for practitioners. Accordingly, this attracted attention of many researchers, who tried to support real-world configuration planning by suited optimization models (assembly line balancing problems). In spite of the enormous academic effort in assembly line balancing, there remains a considerable gap between requirements of real configuration problems and the status of research. To ease communication between researchers and practitioners, we provide a classification scheme of assembly line balancing. This is a valuable step in identifying remaining research challenges which might contribute to closing the gap.     

A dynamic programming based heuristic for the assembly line balancing problem

The simple assembly line balancing problem is the simplification of a real problem associated to the assignment of the elementary tasks required for assembly of a product in an assembly line. This problem has been extensively studied in the literature for more than half a century. The present work proposes a new procedure to solve the problem we call Bounded Dynamic Programming. This use of the term Bounded is associated not only with the use of bounds to reduce the state space but also to the reduction of such space based on heuristics. This procedure is capable of obtaining an optimal solution rate of 267 out of 269 instances, which have been used in previous works, thus obtaining the best-known performance for the problem. These results are an improvement from any previous procedure found in the literature even when using smaller computing times.     

Simple and U-type assembly line balancing problems with a learning effect

In this paper, we introduced learning effect into assembly line balancing problems. In many realistic settings, the produced worker(s) (or machine(s)) develops continuously by repeated the same or similar activities. Therefore, the production time of product shortens if it is processed later. We show that polynomial solutions can be obtained for both simple assembly line balancing problem (SALBP) and U-type line balancing problem (ULBP) with learning effect.     

A station-oriented enumerative algorithm for two-sided assembly line balancing

In this paper, a station-oriented enumerative algorithm for two-sided assembly lines balancing (TALB) is proposed. First, the time transfer function is defined and combined with the precedence relation to compute the earliest and the latest start time of tasks. With the direction and cycle time constraints, a station-oriented procedure based on the start time is designed to assign tasks, starting from the left station to the rightstation of the position. Some unsuitable position assignments would be finally removed by checking the precedence constraints among the assigned tasks. The proposed algorithm is integrated with the Hoffmann heuristic to develop a system for solving TALB problems. The test is performed on the well-known benchmark set of problem instances. Experimental results demonstrate that the proposed procedure is efficient.     

A balancing method and genetic algorithm for disassembly line balancing

Disassembly activities take place in various recovery operations including remanufacturing, recycling and disposal. The disassembly line is the best choice for automated disassembly of returned products. It is therefore important that the disassembly line be designed and balanced so that it works as efficiently as possible. The disassembly line balancing problem seeks a sequence which: is feasible, minimizes workstations, and ensures similar idle times, as well as other end-of-life specific concerns. However finding the optimal balance is computationally intensive with exhaustive search quickly becoming prohibitively large even for relatively small products. In this paper the problem is mathematically defined and proven NP-complete. Additionally, a new formula for quantifying the level of balancing is proposed. A first-ever set of a priori instances to be used in the evaluation of any disassembly line balancing solution technique is then developed. Finally, a genetic algorithm is presented for obtaining optimal or near-optimal solutions for disassembly line balancing problems and examples are presented to illustrate implementation of the methodology.     

A comparison of heuristic algorithms for cost-oriented assembly line balancing

Two new heuristic algorithms for solving cost-oriented assembly line balancing problems -the Wage-Rate-Method (WR) and the Wage-Rate-Smoothing-Method (WRS) — are presented and compared with two known heuristics — the Positional-Weight-Method (PW) and the Positional-Weight-Wage-Rate-Difference-Method (PWWD) with respect to their solution qualities. Firstly, the heuristics are outlined and their computational effort is stated. Then, a theoretical worst-case bound for the solution quality is given and the results of an extensive performance study are reported. In the study the heuristics were investigated with respect to their solution quality by solving randomly generated line balancing problems and problems from literature. It can be concluded that PWWD and WRS are generally superior to PW and WR.Parts of this research have been supported by the Stiftung Industrieforschung.     

A branch-and-bound algorithm to minimize the line length of a two-sided assembly line

A new branch-and-bound algorithm is presented to solve the two-sided assembly line balancing problem of type 1 (TALB-1). First, a pair of two directly facing station is defined as a position, and then the two-sided assembly line (TAL) is relaxed to a one-sided assembly line (OAL). Some new lower bound on positions are computed, and dominance rules and reduction rules for the one-sided assembly line balancing problem of type 1 (OALB-1) are extended and incorporated into a station-oriented assignment procedure for the TALB-1 problem. Finally, the tests are carried out on a well-known benchmark set of problem instances, and experimental results demonstrate that the proposed procedure is efficient.     

Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry

In production systems of automobile manufacturers, multi-variant products are assembled on paced final assembly lines. The assignment of operations to workplaces and workers deter mines the productivity of the manufacturing process. In research, various exact and heuristic solution procedures have been developed for different versions of the so-called assembly line balancing problem.     

Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing

Assembly line balancing generally requires a set of acceptable solutions to the several conflicting objectives. In this study, a binary fuzzy goal programming approach is applied to assembly line balancing. Models for balancing straight and U-shaped assembly lines with fuzzy goals (the number of workstations and cycle time goals) are proposed. The binary fuzzy goal programming models are solved using the methodology introduced by Chang [Chang, C.T., 2007. Binary fuzzy goal programming. European Journal of Operational Research 180 (1), 29–37]. An illustrative example is presented to demonstrate the validity of the proposed models and to compare the performance of straight and U-shaped line configurations.     

A chance-constrained approach to stochastic line balancing problem

In this paper, chance-constrained 0–1 integer programming models for the stochastic traditional and U-type line balancing (ULB) problem are developed. These models are solved for several test problems that are well known in the literature and the computational results are given. In addition, a goal programming approach is presented in order to increase the system reliability, which is arising from the stochastic case.     

An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem

This paper evaluates a set of constructive heuristic methods developed to solve the novel Alternative Subgraphs Assembly Line Balancing Problem (ASALBP), which considers variants for different parts of a production or manufacturing process. Each variant is represented by a precedence subgraph that defines the tasks to be performed and their processing times. The proposed methods use priority rules and random choice to select the assembly subgraphs and to assign the tasks to the stations in order to minimize the number of required workstations. The methods are evaluated by a computational experiment based on medium- and large-scale benchmark problems. This work is supported by the Spanish MCyT project DPI2004-03472, co-financed by FEDER, and by a Venezuelan Grant by the University of Los Andes.     

Bi-criteria assembly line balancing by considering flexible operation times

This paper addresses a novel approach to deal with Flexible task Time Assembly Line Balancing Problem (FTALBP). In this regard, machines are considered in which operation time of each task can be between lower and upper bounds. These machines can compress the processing time of tasks, but this action may lead to higher cost due to cumulative wear, erosion, fatigue and so on. This cost is described in terms of task time via a linear function. Hence, a bi-criteria nonlinear integer programming model is developed which comprises two inconsistent objective functions: minimizing the cycle time and minimizing the machine total costs. In order to sustain these objectives concurrently, this paper applies the LP-metric method to make a combined dimensionless objective. Moreover, a genetic algorithm (GA) is presented to solve this NP-hard problem and design of experiments (DOE) method is hired to tune various parameters of our proposed algorithm. The computational results demonstrate the effectiveness of implemented procedures.     

Incorporating ergonomic risks into assembly line balancing

In manufacturing, control of ergonomic risks at manual workplaces is a necessity commanded by legislation, care for health of workers and economic considerations. Methods for estimating ergonomic risks of workplaces are integrated into production routines at most firms that use the assembly-type of production. Assembly line re-balancing, i.e., re-assignment of tasks to workers, is an effective and, in case that no additional workstations are required, inexpensive method to reduce ergonomic risks. In our article, we show that even though most ergonomic risk estimation methods involve nonlinear functions, they can be integrated into assembly line balancing techniques at low additional computational cost. Our computational experiments indicate that re-balancing often leads to a substantial mitigation of ergonomic risks.     

A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

An application of the branch,bound, and remember algorithm to a new simple assembly line balancing dataset

The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.     

An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem.     

Simple assembly line balancing—Heuristic approaches

In this paper heuristics for Type 1 and Type 2 of the Simple Assembly Line Balancing Problem (SALBP) are described. Type 1 of SALBP (SALBP-1) consists of assigning tasks to work stations such that the number of stations is minimized for a given production rate whereas Type 2 (SALBP-2) is to maximize the production rate, or equivalently, to minimize the sum of idle times for a given number of stations. In both problem types, precedence constraints between the tasks have to be considered.We describe bidirectional and dynamic extensions to heuristic priority rules widely used for SALBP-1. For the solution of SALBP-2 we present search methods which involve the repetitive application of procedures for SALBP-1. Furthermore, improvement procedures for SALBP-2 are developed and combined with tabu search, a recent strategy to overcome local optimality. Several optional elements of tabu search are discussed. Finally, the application of a nontraditional tabu search approach to solve SALBP-1 is investigated. Computational experiments validate the effectiveness of our new approaches.     

Assembly line balancing as generalized bin packing

Bin packing heuristics are generalized and adapted to solve the assembly line balancing problem. Worst-case analysis is provided. The results are compared to those for a resource constrained scheduling problem considered by Garey, Graham, Johnson and Yao.     

Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing

Recently, the importance of correctly designed computational experiments for testing algorithms has been a subject of extended discussions. Whenever real-world data is lacking, generated data sets provide a substantive methodological tool for experiments. Focused research questions need to base on specialized, randomized and sufficiently large data sets, which are sampled from the population of interest. We integrate the generation of data sets into the process of scientific testing.     

A two-process implicit enumeration algorithm for the simple assembly line balancing problem

We present an implicit-enumeration algorithm for the simple assembly line balancing problem, with the objective of minimizing the number of stations along the line for a fixed cycle time. The algorithm traverses two branch-and-bound trees, one assigning tasks that appear earlier in the precedence network at lower levels of the tree, the other assigning later tasks at lower levels. The two processes alternately expand nodes of their respective trees, and share information about each other's progress in the form of global bounds. Computational results are reported on several well-known problems from the literature.