A meta-heuristic algorithm for the fuzzy assembly line balancing type-E problem

Consideration is given to a single-model assembly line balancing problem with fuzzy task processing times. The problem referred to herein as f-SALBP-E consists of finding a combination of the number of workstations and the cycle time as well as a respective line balance such that the efficiency of the line is maximized. f-SALBP-E is an extension of the classical SALBP-E under fuzziness. First, a formulation of the problem is given with the tasks processing times presented by triangular fuzzy membership functions. Then, since the problem is known to be NP-hard, a meta-heuristic based on a Genetic Algorithm (GA) is developed for its solution. The performance of the proposed solution approach is studied and discussed over multiple benchmarks test problems taken from the open literature. The results demonstrate very satisfactory performance for the developed approach in terms of both solution time and quality.     

An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times

In this paper the setup assembly line balancing and scheduling problem (SUALBSP) is considered. Since this problem is NP-hard, a hybrid genetic algorithm (GA) is proposed to solve the problem. This problem involves assigning the tasks to the stations and scheduling them inside each station. A simple permutation is used to determine the sequence of tasks. To determine the assignment of tasks to stations, the algorithm is hybridized using a dynamic programming procedure. Using dynamic programming, at any time a chromosome can be converted to an optimal solution (subject to the chromosome sequence).     

A genetic algorithm based approach to the mixed-model assembly line balancing problem of type II

Mixed-model assembly lines allow for the simultaneous assembly of a set of similar models of a product, which may be launched in the assembly line in any order and mix. As current markets are characterized by a growing trend for higher product variability, mixed-model assembly lines are preferred over the traditional single-model assembly lines.

This paper presents a mathematical programming model and an iterative genetic algorithm-based procedure for the mixed-model assembly line balancing problem (MALBP) with parallel workstations, in which the goal is to maximise the production rate of the line for a pre-determined number of operators.

The addressed problem accounts for some relevant issues that reflect the operating conditions of real-world assembly lines, like zoning constraints and workload balancing and also allows the decision maker to control the generation of parallel workstations.     

An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem

The consideration of this paper is given to address the straight and U-shaped assembly line balancing problem. Although many attempts in the literature have been made to develop deterministic version of the assembly line model, the attention is not considerably given to those in uncertain environment. In this paper, a novel bi-objective fuzzy mixed-integer linear programming model (BOFMILP) is developed so that triangular fuzzy numbers (TFNs) are employed in order to represent uncertainty and vagueness associated with the task processing times in the real production systems. In this proposed model, two conflicting objectives (minimizing the number of stations as well as cycle time) are considered simultaneously with respect to set of constraints. For this purpose, an appropriate strategy in which new two-phase interactive fuzzy programming approach is proposed as a solution method to find an efficient compromise solution. Finally, validity of the proposed model as well as its solution approach are evaluated though numerical examples. In addition, a comparison study is conducted over some test problems in order to assess the performance of the proposed solution approach. The results demonstrate that our proposed interactive fuzzy approach not only can be applied in ALBPs but also is capable to handle any practical MOLP models. Moreover, in light of these results, the proposed model may constitute a framework aiming to assist the decision maker (DM) to deal with uncertainty in assembly line problem.     

Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models

Two-sided assembly lines are especially used at the assembly of large-sized products, such as trucks and buses. In this type of a production line, both sides of the line are used in parallel. In practice, it may be necessary to optimize more than one conflicting objectives simultaneously to obtain effective and realistic solutions. This paper presents a mathematical model, a pre-emptive goal programming model for precise goals and a fuzzy goal programming model for imprecise goals for two-sided assembly line balancing. The mathematical model minimizes the number of mated-stations as the primary objective and it minimizes the number of stations as a secondary objective for a given cycle time. The zoning constraints are also considered in this model, and a set of test problems taken from literature is solved. The proposed goal programming models are the first multiple-criteria decision-making approaches for two-sided assembly line balancing problem with multiple objectives. The number of mated-stations, cycle time and the number of tasks assigned per station are considered as goals. An example problem is solved and a computational study is conducted to illustrate the flexibility and the efficiency of the proposed goal programming models. Based on the decision maker's preferences, the proposed models are capable of improving the value of goals.     

A branch-and-bound algorithm for assembly line worker assignment and balancing problems

In this paper, we studied the assembly line worker assignment and balancing problem, which is an extension of the classical assembly line balancing problem in which an optimal partition of the assembly work among the stations is sought along with the assignment of the operators to the stations. The relationship between this problem and several other well-studied problems is explored, and new lower bounds are derived. Additionally, an exact enumeration algorithm, which makes use of the lower bounds, is developed to solve the problem. The algorithm is tested by using a standard benchmark set of instances. The results show that the algorithm improves upon the best-performing methods from the literature in terms of solution quality, and verifies more optimal solutions than the other available exact methods.     

Firing sequences backward algorithm for simple assembly line balancing problem of type 1

The objective of simple assembly line balancing problem type-1 (SALBP-1) is to minimize the number of workstations on an assembly line for a given cycle time. Since SALBP-1 is NP-hard, many iterative backtracking heuristics based on branch and bound procedure, tabu search, and genetic algorithms were developed to solve SALBP-1. In this study, a new heuristic algorithm based on Petri net approach is presented to solve the problem. The presented algorithm makes an order of firing sequence of transitions from Petri net model of precedence diagram. Task is assigned to a workstation using this order and backward procedure. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. Computational study validates its effectiveness on the benchmark problems. Also comparison results show that the algorithm is efficiency to solve SALBP-1.     

A mathematical model and a genetic algorithm for two-sided assembly line balancing

A two-sided assembly line is a type of production line where tasks are performed in parallel at both sides of the line. The line is often found in producing large products such as trucks and buses. This paper presents a mathematical model and a genetic algorithm (GA) for two-sided assembly line balancing (two-ALB). The mathematical model can be used as a foundation for further practical development in the design of two-sided assembly lines. In the GA, we adopt the strategy of localized evolution and steady-state reproduction to promote population diversity and search efficiency. When designing the GA components, including encoding and decoding schemes, procedures of forming the initial population, and genetic operators, we take account of the features specific to two-ALB. Through computational experiments, the performance of the proposed GA is compared with that of a heuristic and an existing GA with various problem instances. The experimental results show that the proposed GA outperforms the heuristic and the compared GA.     

Two-sided assembly line balancing problem of type I: Improvements,a simple algorithm and a comprehensive study

Many meta-heuristic methods have been applied to solve the two-sided assembly line balancing problem of type I with the objective of minimizing the number of stations, but some of them are very complex or intricate to be extended. In addition, different decoding schemes and different objectives have been proposed, leading to the different performances of these algorithms and unfair comparison. In this paper, two new decoding schemes with reduced search space are developed to balance the workload within a mated-station and reduce sequence-depended idle time. Then, graded objectives are employed to preserve the minor improvements on the solutions. Finally, a simple iterated greedy algorithm is extended for the two-sided assembly line balancing problem and modified NEH-based heuristic is introduced to obtain a high quality initial solution. And an improved local search with referenced permutation and reduced insert operators is developed to accelerate the search process. Computational results on benchmark problems prove the efficiency of the proposed decoding schemes and the new graded objectives. A comprehensive computational comparison among 14 meta-heuristics is carried out to demonstrate the efficiency of the improved iterated greedy algorithm.     

Line balancing of PCB assembly line using immune algorithms

Printed Circuit Boards (PCBs) are widely used in most electronic devices. Typically, a PCB design has a set of components that needs to be assembled. In a broad sense, this assembly task involves placing PCB components at designated location on a PCB board; fixing PCB components; and testing the PCB after assembly operation to ensure that it is in proper working order. The stringent requirements of having a higher component density on PCBs, a shorter assembly time, and a more reliable product prompt manufacturers to automate the process of PCB assembly. Frequently, a few placement machines may work together to form an assembly line. Thus, the application of more than one machine for component placement on a PCB presents a line-balancing problem, which is basically concerned with balancing the workload of all the machines in an assembly line. This paper describes the application of a new artificial intelligence technique known as the immune algorithm to PCB component placement as well as the line balancing of PCB assembly line. It also includes an overview of PCB assembly and an outline of the assembly line balancing problem. Two case studies are used to validate the IA engine developed in this work. The details of IA, the IA engine and the case studies are presented.     

On solving the assembly line worker assignment and balancing problem via beam search

Certain types of manufacturing processes can be modelled by assembly line balancing problems. In this work we deal with a specific assembly line balancing problem that is known as the assembly line worker assignment and balancing problem (ALWABP). This problem appears in settings where tasks must be assigned to workers, and workers to work stations. Task processing times are worker specific, and workers might even be incompatible with certain tasks. The ALWABP was introduced to model assembly lines typical for sheltered work centers for the Disabled.     

Robust assembly line balancing with heterogeneous workers

Assembly lines are manufacturing systems in which a product is assembled progressively in workstations by different workers or machines, each executing a subset of the needed assembly operations (or tasks). We consider the case in which task execution times are worker-dependent and uncertain, being expressed as intervals of possible values. Our goal is to find an assignment of tasks and workers to a minimal number of stations such that the resulting productivity level respects a desired robust measure. We propose two mixed-integer programming formulations for this problem and explain how these formulations can be adapted to handle the special case in which one must integrate a particular set of workers in the assembly line. We also present a fast construction heuristic that yields high quality solutions in just a fraction of the time needed to solve the problem to optimality. Computational results show the benefits of solving the robust optimization problem instead of its deterministic counterpart.     

Optimisation of mixed-model assembly line balancing problem under uncertain demand

Assembly lines play a crucial role in determining the profitability of a company. Market conditions have increased the importance of mixed-model assembly lines. Variations in the demand are frequent in real industrial environments and often leads to failure of the mixed-model assembly line balancing scheme. Decision makers have to take into account this uncertainty. In an assembly line balancing problem, there is a massive amount of research in the literature assuming deterministic environment, and many other works consider uncertain task times. This research utilises the uncertainty theory to model uncertain demand and introduces complexity theory to measure the uncertainty of assembly lines. Scenario probability and triangular fuzzy number are used to describe the uncertain demand. The station complexity was measured based on information entropy and fuzzy entropy to assist in balancing systems with robust performances, considering the influence of multi-model products in the station on the assembly line. Taking minimum station complexity, minimum workload difference within station, maximum productivity as objective functions, a new optimization model for mixed-model assembly line balancing under uncertain demand was established. Then an improved genetic algorithm was applied to solve the model. Finally, the effectiveness of the model was verified by several instances of mixed-model assembly line for automobile engine.     

An advanced multiobjective genetic algorithm design for the time and space assembly line balancing problem

Time and space assembly line balancing considers realistic multiobjective versions of the classical assembly line balancing industrial problems involving the joint optimization of conflicting criteria such as the cycle time, the number of stations, and/or the area of these stations. In addition to their multi-criteria nature, the different problems included in this field inherit the precedence constraints and the cycle time limitations from assembly line balancing problems, which altogether make them very hard to solve. Therefore, time and space assembly line balancing problems have been mainly tackled using multiobjective constructive metaheuristics. Global search algorithms in general - and multiobjective genetic algorithms in particular - have shown to be ineffective to solve them up to now because the existing approaches lack of a proper design taking into account the specific characteristics of this family of problems. The aim of this contribution is to demonstrate the latter assumption by proposing an advanced multiobjective genetic algorithm design for the 1/3 variant of the time and space assembly line balancing problem which involves the joint minimization of the number and the area of the stations given a fixed cycle time limit. This novel design takes the well known NSGA-II algorithm as a base and considers the use of a new coding scheme and sophisticated problem specific operators to properly deal with the said problematic questions. A detailed experimental study considering 10 different problem instances (including a real-world instance from the Nissan plant in Barcelona, Spain) will show the good yield of the new proposal in comparison with the state-of-the-art methods.     

A review of the current applications of genetic algorithms in assembly line balancing

Most of the problems involving the design and plan of manufacturing systems are combinatorial and NP-hard. A well-known manufacturing optimization problem is the assembly line balancing problem (ALBP). Due to the complexity of the problem, in recent years, a growing number of researchers have employed genetic algorithms. In this article, a survey has been conducted from the recent published literature on assembly line balancing including genetic algorithms. In particular, we have summarized the main specifications of the problems studied, the genetic algorithms suggested and the objective functions used in evaluating the performance of the genetic algorithms. Moreover, future research directions have been identified and are suggested.     

Modeling and solving constrained two-sided assembly line balancing problem via bee algorithms

Designing and operating two-sided assembly lines are crucial for manufacturing companies which assemble large-sized products such as trucks, buses and industrial refrigerators. This type of assembly line structure has several advantages over one-sided assembly lines such as shortened line length and reduced throughput time. The research area has recently focused on balancing two-sided assembly lines owing to these advantages. However, due to the complex structure of this problem, some practical constraints have been disregarded or have not been fully incorporated. In order to overcome these deficiencies, a fully constrained two-sided assembly line balancing problem is addressed in this research paper. Initially, a mathematical programming model is presented in order to describe the problem formally. Due to the problem complexity, two different swarm intelligence based search algorithms are implemented to solve large-sized instances. Bees algorithm and artificial bee colony algorithm have been applied to the fully constrained two-sided assembly line balancing problem so as to minimize the number of workstations and to obtain a balanced line. An extensive computational study has also been performed and the comparative results have been evaluated.     

A hybrid genetic algorithm for mixed model assembly line balancing problem with parallel workstations and zoning constraints

In this paper, we propose a hybrid genetic algorithm to solve mixed model assembly line balancing problem of type I (MMALBP-I). There are three objectives to be achieved: to minimize the number of workstations, maximize the workload smoothness between workstations, and maximize the workload smoothness within workstations. The proposed approach is able to address some particular features of the problem such as parallel workstations and zoning constraints. The genetic algorithm may lack the capability of exploring the solution space effectively. We aim to improve its exploring capability by sequentially hybridizing the three well known heuristics, Kilbridge & Wester Heuristic, Phase-I of Moodie & Young Method, and Ranked Positional Weight Technique, with genetic algorithm. The proposed hybrid genetic algorithm is tested on 20 representatives MMALBP-I and the results are compared with those of other algorithms.     

An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations

In the event that big-sized complex products (containing a large number of assembly tasks most of which have long task times) are produced in simple or two-sided assembly lines, hundreds of stations are essentially required. Long product flow time, a large area for establishment of the line, a high budget for the investment of equipment, and tools in stations and several work-in-process are also required for these kinds of products. In order to avoid these disadvantages, assembly lines with parallel multi-manned workstations can be utilized. In this paper, these lines and one of their balancing problems are addressed, and a branch and bound algorithm is proposed. The algorithm is composed of a branching scheme, some efficient dominance and feasibility criteria based on a problem-specific knowledge. A heuristic-based guidance for enumeration process is included as an efficient component of the algorithm as well. VWSolver algorithm proposed for a special version of the problem in the literature has been modified and compared with the proposed algorithm. Results show that proposed algorithm outperforms VWSolver in terms of both CPU times and quality of feasible solutions found.     

Type II robotic assembly line balancing problem: An evolution strategies algorithm for a multi-objective model

In this paper a different type II robotic assembly line balancing problem (RALB-II) is considered. One of the two main differences with the existing literature is objective function which is a multi-objective one. The aim is to minimize the cycle time, robot setup costs and robot costs. The second difference is on the procedure proposed to solve the problem. In addition, a new mixed-integer linear programming model is developed. Since the problem is NP-hard, three versions of multi-objective evolution strategies (MOES) are employed. Numerical results show that the proposed hybrid MOES is more efficient.     

A decomposition based solution algorithm for U-type assembly line balancing with interval data

Balancing U-type assembly lines under uncertainty is addressed in this paper by formulating a robust problem and developing its optimization model and algorithm. U-type assembly layouts are shown to be more efficient than conventional straight lines. A great majority of studies on U-lines assume deterministic environments and ignore uncertainty in operation times. We aim to fill this research gap and, to the best of our knowledge, this study will be the first application of robust optimization to U-type assembly planning.We assume that the operation times are not fixed but they can vary. We employ robust optimization that considers worst case situations. To avoid over-pessimism, we consider that only a subset of operation times take their worst case values. To solve this problem, we suggest an iterative approximate solution algorithm. The efficiency of the algorithm is evaluated with some computational tests.