Multi-objective optimization of a stochastic assembly line balancing: A hybrid simulated annealing algorithm

This paper deals with multi-objective optimization of a single-model stochastic assembly line balancing problem with parallel stations. The objectives are as follows: (1) minimization of the smoothness index and (2) minimization of the design cost. To obtain Pareto-optimal solutions for the problem, we propose a new solution algorithm, based on simulated annealing (SA), called m_SAA. m_SAA implements a multinomial probability mass function approach, tabu list, repair algorithms and a diversification strategy. The effectiveness of m_SAA is investigated comparing its results with those obtained by another SA (using a weight-sum approach) on a suite of 24 test problems. Computational results show that m_SAA with a multinomial probability mass function approach is more effective than SA with weight-sum approach in terms of the quality of Pareto-optimal solutions. Moreover, we investigate the effects of properties (i.e., the tabu list, repair algorithms and diversification strategy) on the performance of m_SAA.     

Multi-objective partial disassembly optimization based on sequence feasibility

A sustainable manufacturing system integrates production systems, consumer usage behavior, and End-of-Life (EoL) product value recovery activities. Facilitating multi-objective disassembly planning can be a step toward analyzing the tradeoffs between the environmental impact and profitability of value recovery. In this paper, a Genetic Algorithm (GA) heuristic is developed to optimize partial disassembly sequences based on disassembly operation costs, recovery reprocessing costs, revenues, and environmental impacts. EoL products may not warrant disassembly past a unique disassembly level due to limited recovered component market demand, minimal material recovery value, or minimal functional recovery value. The effectiveness of the proposed GA is first verified and tested using a simple disassembly problem and then applied to the traditional coffee maker disassembly case study. Analyses are disaggregated into multiple disassembly network optimization problems, one for each product subassembly, resulting in a bottom-up approach to EoL product partial disassembly sequence optimization.     

Artificial bee colony algorithm for solving sequence-dependent disassembly line balancing problem

In this paper, we consider a sequence-dependent disassembly line balancing problem (SDDLBP) with multiple objectives that requires the assignment of disassembly tasks to a set of ordered disassembly workstations while satisfying the disassembly precedence constraints and optimizing the effectiveness of several measures. Since the complexity of SDDLBP increases with the number of parts of the product, an efficient methodology based on artificial bee colony (ABC) is proposed to solve the SDDLBP. ABC is an optimization technique which is inspired by the behavior of honey bees. The performance of the proposed algorithm was tested against six other algorithms. The results show that the proposed ABC algorithm performs well and is superior to the other six algorithms in terms of the objective values performance.     

多目标拆卸线平衡问题的Pareto细菌觅食算法*

拆卸线平衡问题的优化涉及多个目标,为克服传统方法在求解多目标拆卸线平衡问题时不能很好处理各子目标间冲突及易于早熟等不足,提出了一种多目标细菌觅食优化算法。算法采用Pareto非劣排序技术对种群进行分级,并结合拥挤距离机制评价同级个体的优劣。为提高算法收敛性能,在趋向性操作结束后引入精英保留策略保留优秀个体,并采用全局信息共享策略引导菌群不断向均匀分布的Pareto最优前沿趋近。通过不同规模算例的对比验证表明了算法的有效性与优越性。     

Assembly line balancing under uncertainty: Robust optimization models and exact solution method

This research deals with line balancing under uncertainty and presents two robust optimization models. Interval uncertainty for operation times was assumed. The methods proposed generate line designs that are protected against this type of disruptions. A decomposition based algorithm was developed and combined with enhancement strategies to solve optimally large scale instances. The efficiency of this algorithm was tested and the experimental results were presented. The theoretical contribution of this paper lies in the novel models proposed and the decomposition based exact algorithm developed. Moreover, it is of practical interest since the production rate of the assembly lines designed with our algorithm will be more reliable as uncertainty is incorporated. Furthermore, this is a pioneering work on robust assembly line balancing and should serve as the basis for a decision support system on this subject.     

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

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.     

Multi-objective supply planning for two-level assembly systems with stochastic lead times

This paper considers two-level assembly systems whose lead times of components are stochastic with known discrete random distributions. In such a system, supply planning requires determination of release dates of components at level 2 in order to minimize expected holding cost and to maximize customer service. Hnaien et al. [Hnaien F, Delorme X, Dolgui A. Multi-objective optimization for inventory control in two-level assembly systems under uncertainty of lead times. Computers and Operations Research 2010; 37:1835-43] have recently examined this problem, trying to solve it through multi-objective genetic algorithms. However, some reconsideration in their paper is unavoidable. The main problem with Hnaien et al. proposal is their wrong mathematical model. In addition, the proposed algorithms do not work properly in large-scale instances. In the current paper, this model is corrected and solved via a new approach based on NSGA-II that is called Guided NSGA-II. This approach tries to guide search toward preferable regions in the solution space. According to the statistical analyses, the guided NSGA-II has the higher performance in comparison with the basic NSGA-II used by Hnaien et al. Moreover, the wrongly reported characteristics of the Pareto front shape provided by Hnaien et al. are modified.     

Dependent-chance programming: A class of stochastic optimization

This paper provides a theoretical framework of dependent-chance programming, as well as dependent-chance multiobjective programming and dependent-chance goal programming which are new types of stochastic optimization. A stochastic simulation based genetic algorithm is also designed for solving dependent-chance programming models.     

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 solution procedure for type E simple assembly line balancing problem

This paper presents a type E simple assembly line balancing problem (SALBP-E) that combines models SALBP-1 and SALBP-2. Furthermore, this study develops a solution procedure for the proposed model. The proposed model provides a better understanding of management practice that optimizes assembly line efficiency while simultaneously minimizing total idle time. Computational results indicated that, under the given upper bound of cycle time (ct_max), the proposed model can solve problems optimally with minimal variables, constraints, and computing time.     

An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times

This study introduces the problem of minimizing average relative percentage of imbalance (ARPI) with sequence-dependent setup times in a parallel-machine environment. A mathematical model that minimizes ARPI is proposed. Some heuristics, and two metaheuristics, an ant colony optimization algorithm and a genetic algorithm are developed and tested on various random data. The proposed ant colony optimization method outperforms heuristics and genetic algorithm. On the other hand, heuristics using the cumulative processing time obtain better results than heuristics using setup avoidance and a hybrid rule in assignment.     

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.     

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.     

Multi-objective optimization of sensor array using genetic algorithm

A multi-objective optimization method using genetic algorithm was proposed for sensor array optimization. Based on information theory, selectivity and diversity were used as the criteria for constructing two objective functions. A statistic measurement of resolving power, general resolution factor, and visual inspection were used to evaluate the optimization results with the aid of principal component analysis. In each Pareto set, most nondominated solutions had better statistics than the combination using all potential sensors. Also the principal component plots showed that different vapor classes were generally better separated after optimization. The experiment results indicated that the proposed method could successfully identify a set of Pareto optimal solutions of small size; and most optimized sensor arrays provided input with improved quality, i.e. better separation of target analytes. The running time for implementing the multi-objective optimization was satisfactory.     

Evolving dynamic Bayesian networks with Multi-objective genetic algorithms

A dynamic Bayesian network (DBN) is a probabilistic network that models interdependent entities that change over time. Given example sequences of multivariate data, we use a genetic algorithm to synthesize a network structure that models the causal relationships that explain the sequence. We use a multi-objective evaluation strategy with a genetic algorithm. The multi-objective criteria are a network's probabilistic score and structural complexity score. Our use of Pareto ranking is ideal for this application, because it naturally balances the effect of the likelihood and structural simplicity terms used in the BIC network evaluation heuristic. We use a basic structural scoring formula, which tries to keep the number of links in the network approximately equivalent to the number of variables. We also use a simple representation that favors sparsely connected networks similar in structure to those modeling biological phenomenon. Our experiments show promising results when evolving networks ranging from 10 to 30 variables, using a maximal connectivity of between 3 and 4 parents per node. The results from the multi-objective GA were superior to those obtained with a single objective GA. Brian J. Ross is a professor of computer science at Brock University, where he has worked since 1992. He obtained his BCSc at the University of Manitoba, Canada, in 1984, his M.Sc. at the University of British Columbia, Canada, in 1988, and his Ph.D. at the University of Edinburgh, Scotland, in 1992. His research interests include evolutionary computation, language induction, concurrency, and logic programming. He is also interested in computer applications in the fine arts. Eduardo Zuviria received a BS degree in Computer Science from Brock University in 2004 and a MS degree in Computer Science from Queen's University in 2006 where he held jobs as teacher and research assistant. Currently, he is attending a Ph.D. program at the University of Montreal. He holds a diploma in electronics from a technical college and has worked for eight years in the computer industry as a software developer and systems administrator. He has received several scholarships including the Ontario Graduate Scholarship, Queen's Graduate Scholarship and a NSERC- USRA scholarship.     

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

水下航行器控制规律的多目标优化

水下航行器是一个大规模复杂耦合系统,其航行结果由控制规律来决定.而控制规律往往同时受多种因素的影响.控制规律的优化就是一个多目标最优化问题.寻找一个解,使多个目标同时达到最优或对各性能指标加以综合评价是比较困难的.在水下航行器深度控制中以响应时间、操舵次数、航行深度的误差为优化目标.在纵平面内进行控制规律的多目标优化设计.根据水下航行器的力学特性,建立仿真模型,解算定深弹道,得出实际弹道与理论弹道的偏差信息.基于遗传算法良好的全局搜索特性,应用批处理遗传算法进行优化,最终得到控制规律的最优解.结果证明,优化后的解更有利于指导工程实践.