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.     

A multi-objective genetic algorithm for mixed-model assembly line rebalancing

When demand structure or production technology changes, a mixed-model assembly line (MAL) may have to be reconfigured to improve its efficiency in the new production environment. In this paper, we address the rebalancing problem for a MAL with seasonal demands. The rebalancing problem concerns how to reassign assembly tasks and operators to candidate stations under the constraint of a given cycle time. The objectives are to minimize the number of stations, workload variation at each station for different models, and rebalancing cost. A multi-objective genetic algorithm (moGA) is proposed to solve this problem. The genetic algorithm (GA) uses a partial representation technique, where only a part of the decision information about a candidate solution is expressed in the chromosome and the rest is computed optimally. A non-dominated ranking method is used to evaluate the fitness of each chromosome. A local search procedure is developed to enhance the search ability of moGA. The performance of moGA is tested on 23 reprehensive problems and the obtained results are compared with those by other authors.     

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.     

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.     

A beam search approach for solving type II robotic parallel assembly line balancing problem

In a robotic assembly line, a series of stations are arranged along a conveyor belt and a robot performs on tasks at each station. Parallel assembly lines can provide improving line balance, productivity and so on. Combining robotic and parallel assembly lines ensure increasing flexibility of system, capacity and decreasing breakdown sensitivity. Although aforementioned benefits, balancing of robotic parallel assembly lines is lacking – to the best knowledge of the authors- in the literature. Therefore, a mathematical model is proposed to define/solve the problem and also iterative beam search (IBS), best search method based on IBS (BIBS) and cutting BIBS (CBIBS) algorithms are presented to solve the large-size problem due to the complexity of the problem. The algorithm also tested on the generated benchmark problems for robotic parallel assembly line balancing problem. The superior performances of the proposed algorithms are verified by using a statistical test. The results show that the algorithms are very competitive and promising tool for further researches in the literature.     

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

Modeling and solving mixed-model assembly line balancing problem with setups. Part II: A multiple colony hybrid bees algorithm

This paper is the second one of the two papers entitled “Modeling and Solving Mixed-Model Assembly Line Balancing Problem with Setups”, which deals with the mixed-model assembly line balancing problem of type I (MMALBP-I) with some particular features of the real world problems such as parallel workstations, zoning constraints and sequence dependent setup times between tasks. Due to the complex nature of the problem, we tackled the problem with bees algorithm (BA), which is a relatively new member of swarm intelligence based meta-heuristics and tries to simulate the group behavior of real honey bees. However, the basic BA simulates the group behavior of real honey bees in a single colony; we aim at developing a new BA, which simulates the group behavior of honey bees in a single colony and between multiple colonies. The multiple colony type of BA is more realistic than the single colony type because of the multiple colony structure of the real honey bees; each colony represents the honey bees living in a different hive and is generated with a different heuristic rule. The performance of the proposed multiple colony algorithm is tested on 36 representatives MMALBP-I extended by adding low, medium and high variability of setup times. The results are compared with single colony algorithms in terms of solution quality and computational times. Computational results indicate that the proposed multiple colony algorithm has superior performance. Part II of the paper also presents optimal solutions of some problems provided by MILP model developed in Part I.     

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.     

Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimisation with negative knowledge

Particle swarm optimisation (PSO) is an evolutionary metaheuristic inspired by the swarming behaviour observed in flocks of birds. The applications of PSO to solve multi-objective discrete optimisation problems are not widespread. This paper presents a PSO algorithm with negative knowledge (PSONK) to solve multi-objective two-sided mixed-model assembly line balancing problems. Instead of modelling the positions of particles in an absolute manner as in traditional PSO, PSONK employs the knowledge of the relative positions of different particles in generating new solutions. The knowledge of the poor solutions is also utilised to avoid the pairs of adjacent tasks appearing in the poor solutions from being selected as part of new solution strings in the next generation. Much of the effective concept of Pareto optimality is exercised to allow the conflicting objectives to be optimised simultaneously. Experimental results clearly show that PSONK is a competitive and promising algorithm. In addition, when a local search scheme (2-Opt) is embedded into PSONK (called M-PSONK), improved Pareto frontiers (compared to those of PSONK) are attained, but longer computation times are required.     

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.     

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.     

Accumulated risk of body postures in assembly line balancing problem and modeling through a multi-criteria fuzzy-genetic algorithm

Monotonous body postures during repetitive jobs negatively affect assembly-line workers with the developing of Work-related Musculoskeletal Disorders (WMSDs). Ergonomics specialists have offered auxiliary posture diversity to deal with the lack of varieties, especially for high-risk ones. Meanwhile, Assembly Line Balancing (ALB) problem has been recognized as a prior thinking to (re)configure assembly lines via the balancing of their tasks among their workstations. Some conventional criteria, cycle time and overall workload are often considered during the balancing. This paper presents a novel model of ALB problem that incorporates assembly worker postures into the balancing. In addition to the conventional ALB criteria, a new criterion of posture diversity is defined and contributes to enhance the model. The proposed model suggests configurations of assembly lines via the balancing; so that the assigned workers encounter the opportunities of changing their body postures, regularly. To address uncertainties in the conventional criteria, a fuzzy goal programming is used, and an appropriate genetic algorithm is developed to deal with the model. Various computational tests are performed on the different models made with combinations of the three criteria mentioned above. Comparing the pay-offs among the combinations, results show that well balanced task allocation can be obtained through the proposed model.     

A genetic algorithm based approach for simultaneously balancing and sequencing of mixed-model U-lines with parallel workstations and zoning constraints

This paper presents a Priority-Based Genetic Algorithm (PGA) based method for the simultaneously tackling of the mixed-model U-shape assembly line (MMUL) line balancing/model sequencing problems (MMUL/BS) with parallel workstations and zoning constraints and allows the decision maker to control the process to create parallel workstations and to work in different scenarios. In the presented method, simulated annealing based fitness evaluation approach (SABFEA) is developed to be able to make fitness function calculations easily and effectively. A new fitness function is adapted to MMULs for aiming at minimizing the number of workstations as primary goal and smoothing the workload between-within workstations by taking all cycles into consideration. A numerical example to clarify the solution methodology is presented. Performance of the proposed approach is tested through sets of test problem with randomly generated minimum part sets. The results of the computational experiments indicate that SABFEA works with PGA very concordantly; and it is an effective method in solving MMUL/BS with parallel workstations and zoning constraints.     

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.     

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.     

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.     

An imperialist competitive algorithm for a mixed-model assembly line sequencing problem

This paper presents a novel imperialist competitive algorithm (ICA) to a just-in-time (JIT) sequencing problem where variations of production rate are to be minimized. This type of problem is NP-hard. Up to now, some heuristic and meta-heuristic approaches are proposed to minimize the production rates variation. This paper presents a novel algorithm for optimization which inspired by imperialistic competition in real world. Sequences of products where minimize the production rates variation is desired. Performance of the proposed ICA was compared against a genetic algorithm (GA) in small, medium and large problems. Experimental results show the ICA performance against GA.     

A simulated annealing algorithm based approach for balancing and sequencing of mixed-model U-lines

It is known that two interrelated problems called as line balancing and model sequencing should be solved simultaneously for an efficient implementation of a mixed-model U-shape assembly line in a JIT (Just in Time) environment. On the other hand, three versions of assembly line balancing problem can be identified: Type I, Type II, and Type E. There are only two articles ( Kara, Ozcan, & Peker, 2007a and Hamzadayi & Yildiz, 2012) related to simultaneous balancing and sequencing of mixed-model U-lines for minimizing the number of stations (Type 1 problem) by ignoring the fixed model sequence in the current literature. In this paper, a simulated annealing algorithm is proposed for solving a problem of type 1 by ignoring the fixed model sequence. Accordingly, simulated annealing based fitness evaluation approach proposed by Hamzadayi and Yildiz (2012) is enhanced by adding the tabu list, and inserted into the proposed algorithm. Implementation difficulties experienced in meta-heuristics based on solution modification for solving these types of problems are demonstrated. ‘Absolute deviation of workloads’ (ADW) is quite frequently used as performance criteria in the literature. It is found that ADW is an insufficient performance criterion for evaluating the performance of the solutions, and this is showed by means of an illustrative example. The parameters of the proposed algorithm are reviewed for calibrating the algorithm by means of Taguchi design of experiments. Performance of the proposed approach is tested through a set of test problems. The results of computational experiments indicate that the proposed approach is an effective method in solving simultaneous line balancing/model sequencing problems for mixed-model U-lines for minimizing the number of stations.     

基于遗传的装配线平衡系统研究

给出了用于求解装配线平衡的遗传算法。在此基础上,分析了装配线平衡系统的功能和工作机理。并采用面向对象语言开发了装配线平衡系统。最后将此系统用于某装配线的平衡,并依据平衡结果进行仿真,证明该算法效果较好。利用该系统可以有效地解决装配线平衡问题,大大降低成本,为提高装配线的生产效率和改进装配线提供了技术依据。