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.     

Modeling and solving mixed-model assembly line balancing problem with setups. Part I: A mixed integer linear programming model

This paper is the first one of the two papers entitled “modeling and solving mixed-model assembly line balancing problem with setups”, which has the aim of developing the mathematical programming formulation of the problem and solving it with a hybrid meta-heuristic approach. In this current part, a mixed-integer linear mathematical programming (MILP) model for mixed-model assembly line balancing problem with setups is developed. The proposed MILP model considers some particular features of the real world problems such as parallel workstations, zoning constraints, and sequence dependent setup times between tasks, which is an actual framework in assembly line balancing problems. The main endeavor of Part-I is to formulate the sequence dependent setup times between tasks in type-I mixed-model assembly line balancing problem. The proposed model considers the setups between the tasks of the same model and the setups because of the model switches in any workstation. The capability of our MILP is tested through a set of computational experiments. Part-II tackles the problem with a multiple colony hybrid bees algorithm. A set of computational experiments is also carried out for the proposed approach in Part-II.     

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.     

Improved integer programming models for simple assembly line balancing and related problems

We propose a stronger formulation of the precedence constraints and the station limits for the simple assembly line balancing problem. The linear relaxation of the improved integer program theoretically dominates all previous formulations using impulse variables, and produces solutions of significantly better quality in practice. The improved formulation can be used to strengthen related problems with similar restrictions. We demonstrate their effectiveness on the U‐shaped assembly line balancing problem and on the bin packing problem with precedence constraints.     

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.     

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

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.     

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.     

Simultaneously solving the transfer line balancing and buffer allocation problems with a multi-objective approach

Two of the most researched problems on transfer line, transfer line balancing problem (TLBP) and buffer allocation problem (BAP), are usually solved separately, although they are closely interrelated. When machine tools have different reliability, the traditional balancing approaches lead to a deviation of the production rate from the actual throughput, which is used as the objective of the following optimization on BAP. This may not only reduce the solution space of BAP, but also bring about a biased overall result.In this paper, the simultaneous solution of these two problems is presented, which includes transfer line balancing problem, BAP, and selection of line configuration, machine tools and fixtures. Production rate computed through simulation software and total cost considering machine tools and buffer capacities are used as two objective functions. The problem is solved applying a multi-objective optimization approach. Two well-known evolutionary algorithms are considered: Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Multi-Objective Particle Swarm Optimization (MOPSO). A real case study related to automotive sector is used to demonstrate the validity of the proposed approach.     

Simultaneous solving of balancing and sequencing problems with station-dependent assembly times for mixed-model assembly lines

In spite of many studies, investigating balancing and sequencing problems in Mixed-Model Assembly Line (MMAL) individually, this paper solves them simultaneously aiming to minimize total utility work. A new Mixed-Integer Linear Programming (MILP) model is developed to provide the exact solution of the problem with station-dependent assembly times. Because of NP-hardness, a Simulated Annealing (SA) is applied and compared to the Co-evolutionary Genetic Algorithm (Co-GA) from the literature. To strengthen the search process, two main hypotheses, namely simultaneous search and feasible search, are developed contrasting Co-GA. Various parameters of SA are reviewed to calibrate the algorithm by means of Taguchi design of experiments. Numerical results statistically show the efficiency and effectiveness of the proposed SA in terms of both the quality of solution and the time of achieving the best solution. Finally, the contribution of each hypothesis in this superiority is analyzed.     

装配线生产节拍优化系统的研究与开发

为了探讨装配线生产节拍的调整与工作站分配的关系,寻求最优生产节拍,使装配线达到最大的平衡率,以韩格逊-伯尼法、最大设定准则法、优先分配后续作业最多作业法和优先分配操作时间最长作业法为依据,运用PHP开发语言,开发了装配线平衡计算机辅助系统。该系统可遍历某一范围的生产节拍,得出平衡率最高的工作站分配方案。通过对某电冰箱厂装配线的优化分析,使其平衡率提高了10%以上,验证了该系统的可行性。该装配线平衡计算机辅助系统是有效的,可为教学和工厂装配线优化提供指导。     

A Pareto biogeography-based optimisation for multi-objective two-sided assembly line sequencing problems with a learning effect

This research presents a Pareto biogeography-based optimisation (BBO) approach to mixed-model sequencing problems on a two-sided assembly line where a learning effect is also taken into consideration. Three objectives which typically conflict with each other are optimised simultaneously comprising minimising the variance of production rate, minimising the total utility work and minimising the total sequence-dependent setup time. In order to enhance the exploration and exploitation capabilities of the algorithm, an adaptive mechanism is embedded into the structure of the original BBO, called the adaptive BBO algorithm (A-BBO). A-BBO monitors a progressive convergence metric in every certain generation and then based on this data it will decide whether to adjust its adaptive parameters to be used in the next certain generations or not. The results demonstrate that A-BBO outperforms all comparative algorithms in terms of solution quality with indifferent solution diversification.     

A new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems

This paper presents a new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems which is based on the idea of adaptive learning approach and simulated annealing. The proposed approach uses a weight parameter to perturb task priorities of a solution to obtain improved solutions. The weight parameters are then modified using a learning strategy. The maximization of line efficiency (i.e., the minimization of the number of stations) and the equalization of workloads among stations (i.e., the minimization of the smoothness index or the minimization of the variation of workloads) are considered as the performance criteria. In order to clarify the proposed solution methodology, a well known problem taken from literature is solved. A computational study is conducted by solving a large number of benchmark problems available in the literature to compare the performance of the proposed approach to the existing methods such as simulated annealing and genetic algorithms. Some test instances taken from literature are also solved by the proposed approach. The results of the computational study show that the proposed approach performs quite effectively. It also yields optimal solutions for all test problems within a short computational time.     

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

Algorithms and implementation of a set partitioning approach for modular machining line design

A transfer line design problem is considered. Transfer lines are sequences of workstations equipped with processing modules called blocks each of which performs specific operations. These lines are used for mass production of one type of product and thus execute repetitively a given set of operations. The machine parts move along the stations in the same direction. An identical cost is associated with each station and differing costs are associated with the blocks. The problem is to determine the number of stations, select a set of blocks and assign selected blocks to the stations so that operations of the selected blocks constitute the original set of operations and the total cost is minimized. A distinct feature of the problem is that operations at the same station are performed in parallel. Plus, there are inclusion, exclusion and precedence relations that restrict the assignment of the blocks and operations to the same station as well as the processing order of the operations on the transfer line. We implement a novel set partitioning formulation of this design problem with pre-processing procedures and heuristics. The presented approach has the best performance among the existing methods in terms of solution time and quality.     

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.