Robotic U-shaped assembly line balancing using particle swarm optimization

Automation in an assembly line can be achieved using robots. In robotic U-shaped assembly line balancing (RUALB), robots are assigned to workstations to perform the assembly tasks on a U-shaped assembly line. The robots are expected to perform multiple tasks, because of their capabilities. U-shaped assembly line problems are derived from traditional assembly line problems and are relatively new. Tasks are assigned to the workstations when either all of their predecessors or all of their successors have already been assigned to workstations. The objective function considered in this article is to maximize the cycle time of the assembly line, which in turn helps to maximize the production rate of the assembly line. RUALB aims at the optimal assignment of tasks to the workstations and selection of the best fit robot to the workstations in a manner such that the cycle time is minimized. To solve this problem, a particle swarm optimization algorithm embedded with a heuristic allocation (consecutive) procedure is proposed. The consecutive heuristic is used to allocate the tasks to the workstation and to assign a best fit robot to that workstation. The proposed algorithm is evaluated using a wide variety of data sets. The results indicate that robotic U-shaped assembly lines perform better than robotic straight assembly lines in terms of cycle time.     

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 hybrid multi-objective particle swarm algorithm for a mixed-model assembly line sequencing problem

Mixed-model assembly line sequencing is one of the most important strategic problems in the field of production management where diversified customers' demands exist. In this article, three major goals are considered: (i) total utility work, (ii) total production rate variation and (iii) total setup cost. Due to the complexity of the problem, a hybrid multi-objective algorithm based on particle swarm optimization (PSO) and tabu search (TS) is devised to obtain the locally Pareto-optimal frontier where simultaneous minimization of the above-mentioned objectives is desired. In order to validate the performance of the proposed algorithm in terms of solution quality and diversity level, the algorithm is applied to various test problems and its reliability, based on different comparison metrics, is compared with three prominent multi-objective genetic algorithms, PS-NC GA, NSGA-II and SPEA-II. The computational results show that the proposed hybrid algorithm significantly outperforms existing genetic algorithms in large-sized problems.     

A novel integer programming formulation with logic cuts for the U-shaped assembly line balancing problem

U-shaped assembly lines are regarded as an efficient configuration in Just-In-Time manufacturing. Balancing the workload in these lines is an unsolved problem that attracted significant research within the past two decades. We present a novel integer programming formulation for U-shaped line balancing problems, where cycle time, the interval between two consecutive outputs, is known and the aim is to minimize the number of workstations. To enhance the efficiency of the LP relaxation of the new formulation, we present three types of logic cuts (assignable-station-cuts, task-assignment-cuts and knapsack-cuts) that exploit the inherent logic of the problem structure. The new formulation and logic cuts are tested on an extensive set of benchmark problems to provide a comparative analysis with the existing models in the literature. The results show that our novel formulation augmented by assignable-station-cuts is significantly better than the previous formulations.     

An adaptive genetic algorithm approach for the mixed-model assembly line sequencing problem

A mixed-model assembly line (MMAL) is a type of production line that is capable of producing a variety of different product models simultaneously and continuously. The design and planning of such lines involve several long- and short-term problems. Among these problems, determining the sequence of products to be produced has received considerable attention from researchers. This problem is known as the Mixed-Model Assembly Line Sequencing Problem (MMALSP). This paper proposes an adaptive genetic algorithm approach to solve MMALSP where multiple objectives such as variation in part consumption rates, total utility work and setup costs are considered simultaneously. The proposed approach integrates an adaptive parameter control (APC) mechanism into a multi-objective genetic algorithm in order to improve the exploration and exploitation capabilities of the algorithm. The APC mechanism decides the probability of mutation and the elites that will be preserved for succeeding generations, all based on the feedback obtained during the run of the algorithm. Experimental results show that the proposed adaptive GA-based approach outperforms the non-adaptive algorithm in both solution quantity and quality.     

Integrated assembly line balancing with resource restrictions

This paper documents a study carried out on the problem of designing an integrated assembly line when many workers with a variety of skills are employed. This study addresses the problem of selecting multi-functional workers with different salaries to match their skills and of assigning tasks to work stations when there are precedence restrictions among the tasks. The objective of this study is to minimise the total annual work station costs and the annual salary of the assigned workers within a predetermined cycle time. A mixed integer linear program is developed with a genetic algorithm in order to address the problem of resource restrictions related to integrated assembly line balancing. Numerical examples demonstrate the efficiency of the developed genetic algorithm.     

Modelling and optimisation of energy-efficient U-shaped robotic assembly line balancing problems

Within U-shaped assembly lines, the increase of labour costs and subsequent utilisation of robots has led to growing energy consumption, which is the current main expense of auto and electronics industries. However, there are limited researches concerning both energy consumption reduction and productivity improvement on U-shaped robotic assembly lines. This paper first develops a nonlinear multi-objective mixed-integer programming model, reformulates it into a linear form by linearising the multiplication of two binary variables, and then refines the weight of multiple objectives so as to achieve a better approximation of true Pareto frontiers. In addition, Pareto artificial bee colony algorithm (PABC) is extended to tackle this new complex problem. This algorithm stores all the non-dominated solutions into a permanent archive set to keep all the good genes, and selects one solution from this set to overcome the strong local minima. Comparative experiments based on a set of newly generated benchmarks verify the superiority of the proposed PABC over four multi-objective algorithms in terms of generation distance, maximum spread, hypervolume ratio and the ratio of non-dominated solution.     

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.     

Sustainable operator assignment in an assembly line using genetic algorithm

This paper addresses the operator assignment in predefined workstations of an assembly line to get a sustainable result of fitness function of cycle time, total idle time and output where genetic algorithm is used as a solving tool. A proper operator assignment is important to get a sustainable balanced line. To improve the efficiency and meet the desired target output within the time limit, a balanced assembly line is a must. Real world lines consist of a large number of tasks and it is very time consuming and crucial to choose the most suitable operator for a particular workstation. In addition, it is very important to assign the suitable operator at the right place as his skill of operating machines finally reflects in productivity or in the cost of production. To verify better assignments of workers, a genetic algorithm is adopted here. A heuristic is proposed to find out the sustainable assignment of operators in the predefined workstations.     

A multi-decision genetic approach for workload balancing of mixed-model U-shaped assembly line systems

A mixed-model assembly line is a type of production line where a variety of product models similar in product characteristics are produced. As a consequence of introducing the just-in-time (JIT) production principle, it has been recognised that a U-shaped assembly line system offers several benefits over the traditional straight line system. This paper proposes a new evolutionary approach to deal with workload balancing problems in mixed-model U-shaped lines. The proposed method is based on the multi-decision of an amelioration structure to improve a variation of the workload. This paper considers both the traditional straight line system and the U-shaped assembly line, and is thus an unbiased examination of line efficiency. The performance criteria considered are the number of workstations (the line efficiency) and the variation of workload, simultaneously. The results of experiments enhanced the decision process during multi-model assembly line system production; thus, it is therefore suitable for the augmentation of line efficiency in workstation integration and simultaneously enhancement of the variation of the workload. A case study is examined as a validity check in collaboration with a manufacturing company.     

Non-dominated ranked genetic algorithm for a multi-objective mixed-model assembly line sequencing problem

The increasing market demand for product variety forces manufacturers to design mixed-model assembly lines (MMAL) on which a variety of product models similar to product characteristics are assembled. This paper presents a method combining the new ranked based roulette wheel selection algorithm with Pareto-based population ranking algorithm, named non-dominated ranking genetic algorithm (NRGA) to a just-in-time (JIT) sequencing problem when two objectives are considered simultaneously. The two objectives are minimisation the number of setups and variation of production rates. This type of problem is NP-hard. Various operators and parameters of the proposed algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. The solutions obtained via NRGA are compared against solutions obtained via total enumeration (TE) scheme in small problems and also against four other search heuristics in small, medium and large problems. Experimental results show that the proposed algorithm is competitive with these other algorithms in terms of quality and diversity of solutions.     

A heuristic approach for balancing mixed-model assembly line of type I using genetic algorithm

The mixed model assembly line is becoming more important than the traditional single model due to the increased demand for higher productivity. In this paper, a set of procedures for mixed-model assembly line balancing problems (MALBP) is proposed to make it efficiently balance. The proposed procedure based on the meta heuristics genetic algorithm can perform improved and efficient allocation of tasks to workstations for a pre-specified production rate and address some particular features, which are very common in a real world mixed model assembly lines (e.g. use of parallel workstations, zoning constraints, resource limitation). The main focus of this study is to study and modify the existing genetic algorithm framework. Here a heuristic is proposed to reassign the tasks after crossover that violates the constraints. The new method minimises the total number of workstation with higher efficiency and is suitable for both small and large scale problems. The method is then applied to solve a case of a plastic bag manufacturing company where the minimum number of workstations is found performing more efficiently.     

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.     

Extending assembly line balancing problem by incorporating learning effects

In the ramp-up phase, or time to volume of new products, pronounced learning effects are observed. They are present especially on assembly lines producing mass-goods because of a high number of repetitions of the tasks. Shortening the ramp-up phase and reaching the steady-state production as soon as possible generates main advantages for firms that introduce new products. Moreover, a careful planning of the ramp-up stage is getting even more important in view of shorter product life cycles and a growing importance of the ‘time to payback’ financial indicators. Former studies on incorporation of learning effects into assembly line balancing have limited applicability, because they rely on unrealistic assumptions. We model learning effects, based on general and realistic assumptions, as an extension of the Simple Assembly Line Balancing Problem. We propose exact and heuristic solution procedures and perform extensive computational tests. We found that for instances similar to the problems, which arise in firms, the duration of the learning stage can be reduced by up to 10% if our specialised methods are applied.     

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.     

Modelling and solving a cost-oriented resource-constrained multi-model assembly line balancing problem

A line balancing problem considers the assignment of operations to workstations in an assembly line. While assembly lines are usually associated to mass production of standardised goods, their advantages have led to their widespread use whenever a product-oriented production system is applicable and the benefits of the labour division and specialisation are significant, even when some of its characteristics may deviate from classical assembly lines. In this work, we study a line balancing problem found in the textile industry in which the line must be balanced for multiple types of goods taking into account resource requirements. In order to solve the problem, a hybrid method that combines classical methods for line balancing with an Estimation of Distribution Algorithm is proposed. Computational experiments show that the new procedure improves upon the state of the art when compared using a benchmark set derived from the literature, as well as when compared using data from the manufacturer that originated this research work.     

Heuristic procedures for solving the general assembly line balancing problem with setups

The general assembly line balancing problem with setups (GALBPS) was recently defined in the literature. It adds sequence-dependent setup time considerations to the classical simple assembly line balancing problem (SALBP) as follows: whenever a task is assigned next to another at the same workstation, a setup time must be added to compute the global workstation time, thereby providing the task sequence inside each workstation. This paper proposes heuristic procedures, based on priority rules, for solving GALBPS, many of which are an improvement upon heuristic procedures published to date.     

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.     

A modified multi-objective genetic algorithm for two-sided assembly line re-balancing problem of a shovel loader

This article deals with a real-life multi-objective two-sided assembly line rebalancing problem (MTALRBP) with modifications of production demand, line’s structure and production process in a Chinese construction machinery manufacturing firm. The objectives are minimising the cycle time and rebalancing cost, considering some specific constraints associated with the inevitable wait time, such as novel cycle time, idle time and balanced constraints. A modified non-dominated sorting genetic algorithm II (MNSGA-II) is proposed to solve this problem. MNSGA-II employs some problem-specific designs for encoding and decoding, initial population, crossover operator, mutation operator and selection operator. The great performance of MNSGA-II is demonstrated from two aspects: one is through the comparison between the representative results and current situation in the production system in terms of some ALs’ performance evaluation index, the other is utilising the comparison between the proposed MNSGA-II and two versions of initial NSGA-II in terms of ratio, convergence and spread.     

A Petri net-based heuristic for mixed-model assembly line balancing problem of Type-E

To effectively respond to the changing market demands, a manufacturer should produce variety of products with small lots. Thus, multiple products (models) are assembled simultaneously on a same line. However, it is very challenging to balance such an assembly line. This paper conducts a study on balancing a mixed-model assembly line of Type E. To solve this problem, a coloured-timed Petri net model is developed to describe the task precedence relationship. Also, the optimisation problem is formulated as a mathematical programming model. Then, with the models, a two-stage heuristic algorithm is proposed to solve the problem. At the first stage, based on the Petri net model, a P-invariant algorithm (PA) is presented to minimise the number of workstations. At the second stage, a heuristic is proposed to further minimise the cycle time by combining the PA with a binary search algorithm (BSA). Performance of the proposed method is evaluated by an illustrative example and numerical experiments. It is shown that it works well in terms of both solution accuracy and computational efficiency for large size problems.