A versatile algorithm for assembly line balancing

This paper discusses a two stage graph-algorithm, which was designed to solve line balancing problems including practice relevant constraints (GALBP), such as parallel work stations and tasks, cost synergies, processing alternatives, zoning restrictions, stochastic processing times or U-shaped assembly lines. Unlike former procedures, the presented approach can be easily modified to incorporate all of the named extensions. It is not only possible to select and solve single classes of constraints, but rather any combination of them with just slight modifications.     

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 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 hybrid genetic algorithm for sequence-dependent disassembly line balancing problem

For remanufacturing or recycling companies, a reverse supply chain is of prime importance since it facilitates in recovering parts and materials from end-of-life products. In reverse supply chains, selective separation of desired parts and materials from returned products is achieved by means of disassembly which is a process of systematic separation of an assembly into its components, subassemblies or other groupings. Due to its high productivity and suitability for automation, disassembly line is the most efficient layout for product recovery operations. A disassembly line must be balanced to optimize the use of resources (viz., labor, money and time). In this paper, we consider a sequence-dependent disassembly line balancing problem (SDDLBP) with multiple objectives that requires the assignment of disassembly tasks to a set of ordered disassembly workstations while satisfying the disassembly precedence constraints and optimizing the effectiveness of several measures considering sequence dependent time increments. A hybrid algorithm that combines a genetic algorithm with a variable neighborhood search method (VNSGA) is proposed to solve the SDDLBP. The performance of VNSGA was thoroughly investigated using numerous data instances that have been gathered and adapted from the disassembly and the assembly line balancing literature. Using the data instances, the performance of VNSGA was compared with the best known metaheuristic methods reported in the literature. The tests demonstrated the superiority of the proposed method among all the methods considered.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

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.     

Solving a robotic assembly line balancing problem using efficient hybrid methods

In this paper we are studying a robotic assembly line balancing problem. The goal is to maximize the efficiency of the line and to balance the different tasks between the robots by defining the suitable tasks and components to assign to each robot. We are interested in a robotic line which consists of seizing the products on a moving conveyor and placing them on different location points. The performances evaluations of the system are done using a discret event simulation model. This latter has been developed with C++ language. As in our industrial application we are bounded by the execution time, we propose some resolution methods which define the suitable component and point positions in order to define the strategy of pick and place for each robot. These methods are based on the ant colony optimization, particle swarm optimization and genetic algorithms. To enhance the quality of the developed algorithms and to avoid local optima, we have coupled these algorithms with guided local search. After that, an exact method based on full enumeration is also developed to assess the quality of the developed methods. Then, we try to select the best algorithm which is able to get the best solutions with a small execution time. This is the main advantage of our methods compared to exact methods. This fact represents a great interest taking in consideration that the selected methods are used to manage the functioning of real industrial robotic assembly lines. Numerical results show that the selected algorithm performs optimally for the tested instances in a reasonable computation time and satisfies the industrial constraint.     

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 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 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.     

Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times

Industries are incorporating robots into assembly lines due to their greater flexibility and reduced costs. Most of the reported studies did not consider scheduling of tasks or the sequence-dependent setup times in an assembly line, which cannot be neglected in a real-world scenario. This paper presents a study on robotic assembly line balancing, with the aim of minimizing cycle time by considering sequence-dependent setup times. A mathematical model for the problem is formulated and CPLEX solver is utilized to solve small-sized problems. A recently developed metaheuristic Migrating Birds Optimization (MBO) algorithm and set of metaheuristics have been implemented to solve the problem. Three different scenarios are tested (with no setup time, and low and high setup times). The comparative experimental study demonstrates that the performance of the MBO algorithm is superior for the tested datasets. The outcomes of this study can help production managers improve their production system in order to perform the assembly tasks with high levels of efficiency and quality.     

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.     

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.     

Rules-based heuristic approach for the U-shaped assembly line balancing problem

The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.     

Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem

The goal of this work is to develop an improved procedure for the solution of the lexicographic bottleneck variant of the assembly line balancing problem (LB-ALBP). The objective of the LB-ALBP is to minimize the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation and so on. This problem—recently introduced to the literature (Pastor, 2011)—has practical relevance to manufacturing facilities. We design, implement and fine-tune GRASP, tabu search (TS) and scatter search (SS) heuristics for the LB-ALBP and show that our procedures are able to obtain solutions of a quality that outperforms previous approaches. We rely on both semi-greedy and memory-based designs that our experiments show to be effective. Experimental results verify the advantages of embedding such designs to improve the solution existing in the literature of this complex problem. Additionally, the extensive experimentation with 48 variants of GRASP, 12 of TS and 1 of SS establishes the benefits of adding enhanced search strategies to basic procedures.     

A survey on problems and methods in generalized assembly line balancing

Assembly lines are traditional and still attractive means of mass and large-scale series production. Since the early times of Henry Ford several developments took place which changed assembly lines from strictly paced and straight single-model lines to more flexible systems including, among others, lines with parallel work stations or tasks, customer-oriented mixed-model and multi-model lines, U-shaped lines as well as unpaced lines with intermediate buffers.In any case, an important decision problem, called assembly line balancing problem, arises and has to be solved when (re-) configuring an assembly line. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line.Assembly line balancing research has traditionally focused on the simple assembly line balancing problem (SALBP) which has some restricting assumptions. Recently, a lot of research work has been done in order to describe and solve more realistic generalized problems (GALBP). In this paper, we survey the developments in GALBP research.     

A shortest route formulation of simple U-type assembly line balancing problem

In this paper, a shortest route formulation of simple U-type assembly line balancing (SULB) problem is presented and illustrated on a numerical example. This model is based on the shortest route model developed in [Manage. Sci. 11 (2) (1964) 308.] for the traditional single model assembly line balancing problem.     

Shortest-route formulation of mixed-model assembly line balancing problem

A shortest-route formulation of the mixed-model assembly line balancing problem is presented. Common tasks across models are assumed to exist and these tasks are performed in the same stations. The formulation is based on an algorithm which solves the single-model version of the problem. The mixed-model system is transformed into a single-model system with a combined precedence diagram. The model is capable of considering any constraint that can be expressed as a function of task assignments.     

State-of-the-art exact and heuristic solution procedures for simple assembly line balancing

The assembly line balancing problem arises and has to be solved when an assembly line has to be configured or redesigned. It consists of distributing the total workload for manufacturing any unit of the product to be assembled among the work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of the general problem, has attracted attention of researchers and practitioners of operations research for almost half a century.In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recent outstanding and guiding contributions to the field.     

Bees Algorithm for constrained fuzzy multi-objective two-sided assembly line balancing problem

Bees Algorithm is one of the swarm intelligence based heuristics which tries to model natural behaviour of honey bees in food foraging and used to solve optimization problems. On the other hand, Two-sided Assembly Line Balancing Problem is a generalization of simple Assembly Line Balancing Problem where different assembly tasks are carried out on the same product in parallel at both left and right sides of the line. Two-sided assembly lines are generally employed for the assembly of large-sized products such as buses and trucks. Furthermore, many real life problems contain imprecise objectives and Fuzzy Multi-objective Programming gives an opportunity to handle such situations. In this study, Two-sided Assembly Line Balancing Problem is considered more realistically by employing positional, zoning and synchronous task constraints and by utilizing fuzzy approaches so as to maximize work slackness index and line efficiency, and minimize total balance delay. For solving this problem Bees Algorithm is used as a search mechanism for obtaining good solutions and extensive computational results are presented.