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

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.     

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.     

基于遗传算法的焊接生产线工位平衡规划方法

在现代化大规模大批量的流水装配制造业中,数量众多的作用分配和多工位的合理安排使工位平衡问题显得更为突出。针对第一类工位平衡问题,即在给定的生产节拍下最小化工位数,首先分析了该问题并建立了数学模型,进而提出了一种基于改进遗传算法求解工位平衡问题的方法。该算法以焊接任务的操作顺序优先关系为约束前提,在初始种群的生产以及交叉和变异过程中保证了染色体解的可行性,同时在遗传算法的选择过程中考虑了具有相同工位数的最优作业方案的工时标准差,从而提高了算法的搜索效率和解的可靠性。最后通过实例求解验证了该算法的有效性。     

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.     

A Simulated Annealing algorithm for a mixed model assembly U-line balancing type-I problem considering human efficiency and Just-In-Time approach

This research deals with balancing a mixed-model U-line in a Just-In-Time (JIT) production system. The research intends to reduce the number of stations via balancing the workload and maximizing the weighted efficiency, which both are considered as the objectives of this research paper.After balancing the line and determining the number of stations, the labor assignment policy should be set. In this study, it was assumed that there are two types of operators: permanent and temporary. Both types can work in regular and overtime periods. Based on their skill levels, workers are classified into four types. The sign at each work station indicates types of workers allowed to work at that station. An alert system using the hybrid kanban systems was also considered. To solve this problem, a Simulated Annealing algorithm was applied in the following three stages. First, the balancing problem was solved and the number of stations was determined. Second, workers were assigned to the workstations in which they are qualified to work. Following that, an alert system based on the kanban system was designed to balance the work in the process inventory. This was achieved by defining control points based on the processing time and making control decisions to minimize the number of kanban cards. In the proposed SA algorithm, two methods for the temperature cooling schedule were considered and two methods were defined for determining the number of neighborhood search. The initial temperature was considered equal to the cost of the initial solution to reach the convergence situation as soon as possible. Five problems were solved in small size using the GAMS software. The results obtained from the GAMS software were compared with those obtained from the SA algorithm to determine the performance difference. The computational results demonstrated that the SA algorithm is more consistent with the answers obtained. Also seven large scale problems were solved. The results showed that the SA algorithm still have better reliability. To show the efficiency of the proposed SA algorithm, an axel assembly company was studied. To satisfy demands and reduce backlogging, a mixed model assembly line was designed for this case study. The results showed that the mixed model assembly line designed using the SA algorithm had good efficiency.     

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.     

The definition of assembly line balancing difficulty and evaluation of balance solution quality

Assembly line balancing is a classic ill-structured problem where total enumeration is infeasible and optimal solutions uncertain for industrial problems. A quantitative approach to classifying problem difficulty and solution quality is therefore important. Two existing measures of difficulty, order strength and west ratio are compared to a new compound expression of difficulty, project index. Project index is based on individual assessment of precedence (precedence index) and task time (task time index). The current working definition of project index is given. Early criteria for judging assembly lines use balance delay and smoothness index, both are flawed as criteria. Line and balance efficiency are developed as more appropriate. Project index, line and balance efficiency will be illustrated for a published test-case examined by the “ALine” balancing package. The potential for a “learning” approach, selecting models to suit problems using the measures of difficulty, will form part of the conclusions within this paper.     

IEEE 802.11宽带无线局域网负载均衡优化研究

在基于IEEE 802.11的宽带无线局域网中,随着终端STA的接入、移动和无线信道的时变性,各个接入点（AP）的负载将会产生差异,需要负载均衡优化机制平衡各个AP的差异,以达到网络资源的最大利用率。详细讨论了无线局域网中用到的几种负载均衡机制,分析了各自的优缺点,结合这些特点给出一种新的负载均衡机制。该机制能较准确地统计终端业务信息,降低切换失败风险,快速达到APs之间的负载均衡,优化提高网络整体性能。     

Multi-objective optimization of stochastic disassembly line balancing with station paralleling

One of the major activities performed in product recovery is disassembly. Disassembly line is the most suitable setting to disassemble a product. Therefore, designing and balancing efficient disassembly systems are important to optimize the product recovery process. In this study, we deal with multi-objective optimization of a stochastic disassembly line balancing problem (DLBP) with station paralleling and propose a new genetic algorithm (GA) for solving this multi-objective optimization problem. The line balance and design costs objectives are simultaneously optimized by using an AND/OR Graph (AOG) of the product. The proposed GA is designed to generate Pareto-optimal solutions considering two different fitness evaluation approaches, repair algorithms and a diversification strategy. It is tested on 96 test problems that were generated using the benchmark problem generation scheme for problems defined on AOG as developed in literature. In addition, to validate the performance of the algorithm, a goal programming approach and a heuristic approach are presented and their results are compared with those obtained by using GA. Computational results show that GA can be considered as an effective and efficient solution algorithm for solving stochastic DLBP with station paralleling in terms of the solution quality and CPU time.     

The type E simple assembly line balancing problem: A mixed integer linear programming formulation

Although the simple assembly line balancing problem (SALBP) is the topic of many studies, typically they either consider minimizing the number of stations for a given cycle time (called type one), or minimizing the cycle time for a given number of stations (called type two). Rarely, type E of the problem has been considered. In the type E, cycle time and number of stations are both decision variables, and the objective is to maximize the line efficiency. This paper presents a mixed integer linear programming formulation for the type E simple assembly line balancing problem. Moreover, to further strengthen the presented formulation, two enhancement techniques in the form of valid inequalities and auxiliary variables are proposed. As the secondary objectives of the problem, minimization of the number of stations, the cycle time, and the smoothness index are studied as well. In the case of workload smoothing, three different linearization methods are employed and compared for minimizing the smoothness index. The results of computational study on the benchmark data set demonstrate the efficacy of the improved formulation     

Mixed model assembly line design in a make-to-order environment

Mixed model assembly lines can be found today in many industrial environments. With the growing trend for greater product variability and shorter life cycles, they are replacing the traditional mass production assembly lines. In many cases, these lines follow a ‘make-to-order’ production policy, which reduces the customer lead-time, and is expressed in a random arrival sequence of different model types to the line. Additional common characteristics of such mixed model lines in a make-to-order environment are: small numbers of work stations, a lack of mechanical conveyance, and highly skilled workers. The design problem of mixed model assembly lines in a make-to-order environment is addressed in this paper. A mathematical formulation is presented which considers the differences between our model and traditional models. A heuristic that minimizes the number of stations for a predetermined cycle time is developed consisting of three stages: the balancing of a combined precedence diagram, balancing each model type separately subject to the constraints resulting from the first stage, and a neighborhood search based improvement procedure.     

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

Mixed-model assembly line balancing using a multi-objective ant colony optimization approach

Mixed-model assembly lines are production systems at which two or more models are assembled sequentially at the same line. For optimal productivity and efficiency, during the design of these lines, the work to be done at stations must be well balanced satisfying the constraints such as time, space and location. This paper deals with the mixed-model assembly line balancing problem (MALBP). The most common objective for this problem is to minimize the number of stations for a given cycle time. However, the problem of capacity utilization and the discrepancies among station times due to operation time variations are of design concerns together with the number of stations, the line efficiency and the smooth production. A multi-objective ant colony optimization (MOACO) algorithm is proposed here to solve this problem. To prove the efficiency of the proposed algorithm, a number of test problems are solved. The results show that the MOACO algorithm is an efficient and effective algorithm which gives better results than other methods compared.     

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.     

多移动基站无线传感器网络生命期最大化算法

无线传感器网络（WSN）的传感器节点一般由电池提供能源,故能量管理在WSN中是一个基础问题．针对受限多移动基站网络生命期最大化问题,提出了一个MMBEC算法．鉴于移动基站受到实际道路和自身能量的双重限制,算法首先通过规划平衡子回路达到基站间负载的平衡,然后控制基站周期性逗留达到邻近道路节点数据通信量的平衡．由于平衡子回路是NPC问题,采用近似算法找到近似解,控制基站周期性逗留保证邻近道路节点能量几乎同时耗尽,从而延长网络生命期．模拟实验结果证明该算法与现有算法相比能提高网络生命期和吞吐量．     

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.     

Limitations of Existing Mutation Rate Heuristics and How a Rank GA Overcomes Them

Using a set of different search metrics and a set of model landscapes we theoretically and empirically study how ldquooptimalrdquo mutation rates for the simple genetic algorithm (SGA) depend not only on the fitness landscape, but also on population size and population state. We discuss the limitations of current mutation rate heuristics, showing that any fixed mutation rate can be expected to be suboptimal in terms of balancing exploration and exploitation. We then develop a mutation rate heuristic that offers a better balance by assigning different mutation rates to different subpopulations. When the mutation rate is assigned through a ranking of the population, according to fitness for example, we call the resulting algorithm a Rank GA. We show how this Rank GA overcomes the limitations of other heuristics on a set of model problems showing under what circumstances it might be expected to outperform a SGA with any choice of mutation rate.     

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.