Two-sided assembly line balancing to maximize work relatedness and slackness

This paper considers two-sided (left- and right-side) assembly lines that are often used in assembling large-sized products, such as trucks and buses. A large number of exact algorithms and heuristics have been proposed to balance one-sided assembly lines. However, little attention has been paid to balancing the two-sided lines. An efficient assignment procedure is developed for two-sided assembly line balancing problems. A special emphasis is placed on maximizing work relatedness and maximizing work slackness, which are of practical significance especially in two-sided lines. We first investigate the characteristics of two-sided lines and define new measures for the balancing. Then, a group assignment procedure, which assigns a group of tasks at a time rather than a unit task, is designed. Experiments are carried out to demonstrate the performance of the proposed method. The results show that our procedure is promising in the solution quality.     

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.     

2-ANTBAL: An ant colony optimisation algorithm for balancing two-sided assembly lines

Two-sided assembly lines are a special type of assembly lines in which workers perform assembly tasks in both sides of the line. This type of lines is of crucial importance, especially in the assembly of large-sized products, like automobiles, buses or trucks, in which some tasks must be performed at a specific side of the product. This paper presents an approach to address the two-sided mixed-model assembly line balancing problem. First, a mathematical programming model is presented to formally describe the problem. Then, an ant colony optimisation algorithm is proposed to solve the problem. In the proposed procedure two ants ‘work’ simultaneously, one at each side of the line, to build a balancing solution which verifies the precedence, zoning, capacity, side and synchronism constraints of the assembly process. The main goal is to minimise the number of workstations of the line, but additional goals are also envisaged. The proposed procedure is illustrated with a numerical example and results of a computational experience that exhibit its superior performance are presented.     

蚁群算法求解装配线平衡第一类问题

装配线平衡问题是生产管理中重要且较难解决的问题,其中第一类问题是装配线平衡问题的关键问题。本文通过对装配线平衡问题的分析与建模,提出了利用蚁群算法这种人工智能优化算法求解一般装配线平衡第一类问题的步骤和算法。采用启发式的方法构造分配方案的生成策略,并对信息素的更新采用局部更新与全局更新相结合的规则,从而使得该算法具有较好的目的性,大大提高了获得最优解的效率。通过该蚁群算法能得到装配线平衡第一类问题质量较优的解,且有速度快、鲁棒性、通用性等优势。     

Two-sided assembly line balancing considering the relationships between tasks

Previous studies of the two-sided assembly line balancing problem assumed equal relationships between each two tasks assignable to a side of the line. In practice, however, this relationship may be related to such factors as the distance between the implementation place and the tools required for implementation. We know that the more relationships exist between the tasks assigned to each station, the more efficient will be the assembly line. In this paper, we suggest an index for calculating the value of the relationship between each two tasks, and define a performance criterion called ‘assembly line tasks consistency’ for calculating the average relationship between the tasks assigned to the stations of each solution. We propose a simulated annealing algorithm for solving the two-sided assembly line balancing problem considering the three performance criteria of number of stations, number of mated-stations, and assembly line tasks consistency. Also, the simulated annealing algorithm is modified for solving the two-sided assembly line balancing problem without considering the relationships between tasks. This modification finds five new best solutions for the number of stations performance criterion and ten new best solutions for the number of mated-stations performance criterion for benchmark instances.     

A multi-objective TLBO algorithm for balancing two-sided assembly line with multiple constraints

Two-sided assembly line is often designed to produce large-sized high-volume products such as cars, trucks and engineering machinery. However, in real-life production process, besides the elementary constraints in the one-sided assembly line, additional constraints, such as zoning constraints, positional constraints and synchronous constraints, may occur in the two-sided assembly line. In this paper, mathematical formulation of balancing multi-objective two-sided assembly line with multiple constraints is established, and some practical objectives, including maximization of the line efficiency, minimization of the smoothness index and minimization of the total relevant costs per product unit (Tcost), have been considered. A novel multi-objective optimization algorithm based on improved teaching–learning-based optimization (ITLBO) algorithm is proposed to obtain the Pareto-optimal set. In the ITLBO algorithm, teacher and learner phases are modified for the discrete problem, and late acceptance hill-climbing is integrated into a novel self-learning phase. A novel merging method is proposed to construct a new population according to the ordering relation between the original and evolutionary population. The proposed algorithm is tested on the benchmark instances and a practical case. Experimental results, compared with the ones computed by other algorithm and in current literature, validate the effectiveness of the proposed algorithm.     

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.     

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.     

An effective hybrid honey bee mating optimization algorithm for balancing mixed-model two-sided assembly lines

Mixed-model two-sided assembly lines are widely used in a range of industries for their abilities of increasing the flexibility to meet a high variety of customer demands. Balancing assembly lines is a vital design issue for industries. However, the mixed-model two-sided assembly line balancing (MTALB) problem is NP-hard and difficult to solve in a reasonable computational time. So it is necessary for researchers to find some efficient approaches to address this problem. Honey bee mating optimization (HBMO) algorithm is a population-based algorithm inspired by the mating process in the real colony and has been applied to solve many combinatorial optimization problems successfully. In this paper, a hybrid HBMO algorithm is presented to solve the MTALB problem with the objective of minimizing the number of mated-stations and total number of stations for a given cycle time. Compared with the conventional HBMO algorithm, the proposed algorithm employs the simulated annealing (SA) algorithm with three different neighborhood structures as workers to improve broods, which could achieve a good balance between intensification and diversification during the search. In addition, a new encoding and decoding scheme, including the adjustment of the final mated-station, is devised to fit the MTALB problem. The proposed algorithm is tested on several sets of instances and compared with Mixed Integer Programming (MIP) and SA. The superior results of these instances validate the effectiveness of the proposed algorithm.     

Balancing stochastic two-sided assembly line with multiple constraints using hybrid teaching-learning-based optimization algorithm

Two-sided assembly lines are usually found in the factories which produce large-sized products. In most literatures, the task times are assumed to be deterministic while these tasks may have varying operation times in real application, causing the reduction of performance or even the infeasibility of the schedule. Moreover, the ignorance of some specific constraints including positional constraints, zoning constraints and synchronism constraints will result in the invalidation of the schedule. To solve this stochastic two-sided assembly line balancing problem with multiple constraints, we propose a hybrid teaching-learning-based optimization (HTLBO) approach which combines both a novel teaching-learning-based optimization algorithm for global search and a variable neighborhood search with seven neighborhood operators for local search. Especially, a new priority-based decoding approach is developed to ensure that the selected tasks satisfy most of the constraints identified by multiple thresholds of the priority value and to reduce the idle times related to sequence-dependence among tasks. Experimental results on benchmark problems demonstrate both remarkable efficiency and universality of the developed decoding approach, and the comparison among 11 algorithms shows the effectiveness of the proposed HTLBO.     

Comprehensive review and evaluation of heuristics and meta-heuristics for two-sided assembly line balancing problem

This paper presents a comprehensive review and evaluation of heuristics and meta-heuristics for the two-sided assembly line balancing problem. Though a few reviews have been presented, some latest methods are not included and there is no comparison of the meta-heuristics in terms of their performances. Furthermore, since various kinds of encoding schemes, decoding procedures and objective functions have been applied, the results cannot be generalized and the published comparison might be unfair. This paper contributes to knowledge by comparing the published methods, ranging from well-known simulated annealing to recent published iterated local search, and evaluating the six encoding schemes, 30 decoding procedures and five objective functions on the performances of the meta-heuristics meanwhile. The experimental design approach is applied to obtain valid and convincing results by testing algorithms under four termination criteria. Computational results demonstrate that the proper selection of encoding scheme, decoding procedure and objective function improves the performance of the algorithms by a significant margin. Another unique contribution of this paper is that 15 new best solutions are obtained for the large-sized type-II two-sided assembly line balancing problem during the re-implementation and evaluation of the meta-heuristics tested.     

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.     

Two-sided assembly line balancing using teaching–learning based optimization algorithm

Assembly line balancing plays a crucial role in modern manufacturing companies in terms of the growth in productivity and reduction in costs. The problem of assigning tasks to consecutive stations in such a way that one or more objectives are optimized subject to the required tasks, processing times and some specific constraints is called the assembly line balancing problem (ALBP). Depending on production tactics and distinguishing working conditions in practice, assembly line systems show a large diversity. Although, a growing number of researchers addressed ALBP over the past fifty years, real-world assembly systems which require practical extensions to be considered simultaneously have not been adequately handled. This study deals with an industrial assembly system belonging to the class of two-sided line with additional assignment restrictions which are often encountered in practice. Teaching–learning based optimization (TLBO), which is a recently developed nature-inspired search method, is employed to solve the line balancing problem. Computational results are compared with the current situation in terms of the line efficiency, and the solution structure with workload assigned to the stations is presented.     

A Lagrangian relaxation technique for the general assembly line balancing problem

This paper addresses the problem of balancing assembly or fabrication lines. In order to achieve a given production rate or to optimize the use of workstations, one has to tackle the problem of balancing the production lines. It is well known that this problem belongs to the class of NP-hard problems. In this paper the polyhedron of the feasible solutions of the assembly line balancing problem is first studied. Then a Lagrangian relaxation algorithm that incorporates the set of cycle constraints in the objective function is proposed. These constraints are the complicating restrictions in the model. The relaxed problem has the interesting property that its linear programming relaxation always has integer optimal solutions. The subgradient algorithm is then used to maximize the Lagrangian dual. A heuristic is also used to find primal feasible solutions for the original line balancing integer program. These two bounds are then used to reduce the size of the branch-and-bound tree.     

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.     

Comparative Corrigendum note on papers “Fuzzy adaptive GA for multi-objective assembly line balancing” continued “Modified GA for different types of assembly line balancing with fuzzy processing times”: differences and similarities [Appl. Soft Comput. 34 (September 2015) 655–677]

In the very few recently published paper by Alavidoost et al. [1], they proposed a novel fuzzy adaptive genetic algorithm for multi-objective assembly line balancing problem, in continue of their previous presented work by Alavidoost et al. [2], as a modification on genetic algorithm for assembly line balancing with fuzzy processing times. Despite the fact that both of them are well-written, and completely discussed their contributions, this note looks forward to collate these papers together. Likewise provides the correct order of the figures in [1] matching with their corresponding caption.     

A simulated annealing algorithm for multi-manned assembly line balancing problem

Assembly line balancing problems with multi-manned workstations usually occur in plants producing high volume products (e.g. automotive industry) in which the size of the product is reasonably large to utilize the multi-manned assembly line configuration. In these kinds of assembly lines, usually there are multi-manned workstations where a group of workers simultaneously performs different operations on the same individual product. However, owing to the high computational complexity, it is quite difficult to achieve an optimal solution to the balancing problem of multi-manned assembly lines with traditional optimization approaches. In this study, a simulated annealing heuristic is proposed for solving assembly line balancing problems with multi-manned workstations. The line efficiency, line length and the smoothness index are considered as the performance criteria. The proposed algorithm is illustrated with a numerical example problem, and its performance is tested on a set of test problems taken from literature. The performance of the proposed algorithm is compared to the existing approaches. Results show that the proposed algorithm performs well.     

A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem

In this paper, a mixed-model assembly line (MMAL) sequencing problem is studied. This type of production system is used to manufacture multiple products along a single assembly line while maintaining the least possible inventories. With the growth in customers’ demand diversification, mixed-model assembly lines have gained increasing importance in the field of management. Among the available criteria used to judge a sequence in MMAL, the following three are taken into account: the minimization of total utility work, total production rate variation, and total setup cost. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional approaches. Therefore, a hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and bacteria optimization (BO) are deployed. The performance of the proposed hybrid algorithm is then compared with three well-known genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed hybrid algorithm outperforms the existing genetic algorithms, significantly in large-sized problems.     

A modified particle swarm optimization algorithm to mixed-model two-sided assembly line balancing

In this paper, a new modified particle swarm optimization algorithm with negative knowledge is proposed to solve the mixed-model two-sided assembly line balancing problem. The proposed approach includes new procedures such as generation procedure which is based on combined selection mechanism and decoding procedure. These new procedures enhance the solution capability of the algorithm while enabling it to search at different points of the solution space, efficiently. Performance of the proposed approach is tested on a set of test problem. The experimental results show that the proposed approach can be acquired distinguished results than the existing solution approaches.