Study On Assembly Line Balancing Problem By Hybrid Evolutionary Algorithm

Assembly lines are typical flow oriented production systems which are of great importance in the industrial production of high quantity standardized commodities.Among the decision problems which arise in managing such systems,Assembly Line Balancing(ALB)problems are important tasks in medium-term production planning.The ALB problems are to determine the assignment of various tasks to an ordered sequence of workstations,while optimizing one or more objectives without violating restrictions imposed on the line.Many operations researchers have been engaged with developing effective solution procedures for exactly solving ALB problems.This has resulted in about two dozens of procedures which can be subdivided into branch and bound(B&B)procedures and dynamic programming(DP)approaches.However,due to the complexity(NP-hard)of the ALB problems, formulating a mathematical model and solving it by traditional methods is not realistic for finding an optimal solution in case of real-world instances.Recent advances in Evolutionary Computation(EC)have made it possible to solve such practical ALB problems.As one of EC methods,Genetic Algorithm(GA)is one of the most powerful and broadly applicable stochastic search and optimization techniques based on principles from evolution theory.In the past few years,the genetic algorithms community has turned much of its attention toward the optimization of ALB problems.However,for many GA applications,especially for ALB problems,the simple GA approach is difficult to be applied directly.Thus,how to design efficient algorithms suitable for complex cases of ALB models by GA technique is a key issue of this research work.The main contributions of this thesis are:We survey the main features of application of genetic algorithms for optimization problems, and based on that survey we propose a formal model on applying genetic algorithm for a specific problem.This model helps us study the existing application of genetic algorithms for optimization problems and aids in exploration of new hybrid genetic algorithms for those problems.For simple ALB problem,we formulate the mathematical model;propose a genetic algorithm based grouping technique.New chromosome representation and advanced evolutionary operators which incorporate the specific characteristics are developed.Grouping genetic algorithm can preserve the most promising genes from the parents in order to ensure the convergence in the optimal area.In the process of fitness evaluation,a fitness function to realize the continuous improvement for the solutions is selected.Moreover,according to Lamarckian evolutionary principle,an iterative hill climbing method was inserted in order to improve the search ability.For assembly line balancing problem with worker allocation that is expanded from simple ALB problem,we formulate the mathematical model,propose a hybrid genetic algorithm.New genetic operators are designed to carry out crossover and mutation operations for two-vector based chromosomes.Moreover,we present the auto-tuning strategy that it adopts fuzzy logic controller to tune the probabilities of the genetic operators depending on the change of the average fitness of parents and offspring which is occurred at each generation.Numerical experiments for various scales of ALB problems have demonstrated the effectiveness of the proposed approaches with a higher search capability that improves quality of solutions and enhances rate of convergence than other existing GA approaches.This study proposes effective representation methods to express solution candidates for ALB problems.In order to enhance the performance of GA,innovative local search methods and fuzzy logic controller are developed.Finally,we are able to give satisfactory solutions for the targeted problems in an acceptable time span.