A Novel Genetic Algorithm and its Application to Optimize Manufacturing Schedules

John Holland and his colleagues at the University of Michigan introduced genetic algorithms (GAs) in 1992. The algorithmic coding of Genetic Algorithms was described by Goldberg. Since of the real world problems studied in operations research and management science are too complex to be solved by using conventional optimization techniques, genetic algorithms have been widely used in their solution. Furthermore, problems with stochastic characteristics are also typical in analysis, design, and operation of modern systems. Stochastic optimization methods are even more complex than deterministic methods. Since the 1960’s researches have tried to simulate biological process for solving hard optimization problems including stochastic optimization problems. Evolutionary Algorithms (EAs) have been introduced to imitate natural evolutionary processes of human beings. The Genetic Algorithm is an example of EAs. Simulated Annealing and Genetic Algorithms are two examples of optimization methods applied to solving stochastic optimization problems. According to Darwin Evolution’s theory, a process must exist which determines how traits get passed from one generation to the next. Moreover, there must always be diversity of traits present in the population. The last element of Darwin’s Theory is natural selection, which is a way to protect the functional advantages that enables a species have an advantage in competition with others in nature. John Holland used these ideas from Darwin’s Theory when he introduced the Genetic Algorithm. GAs initiate with a set of random solutions for the problem, and this set of solutions is called the population. Each individual (random solution) in a population is called a chromosome and satisfies the constraints for the problem. To facilitate convergence and make the algorithm less sensitive to modeling error, randomness is occasionally used in the search process. This dissertation, which proposes, tests and utilizes a new approach for GAs, will be discussed in four manuscripts: The objective of Manuscript I (in preparation for submission to the journal of Association for Computation Machinery) was to modify the conventional concept of Genetic Algorithm base on human cell division mechanisms. Based on an undirected mechanism of evolution and the natural selection processes, genetic algorithms have been applied for solving many complex problems. Generally, GAs work with a pool of candidate solutions (codified as a genome expression) via crossover and mutation mechanisms for generating new solution proposals for the problem. Algorithms differ in the customization of the genome representation of the solution for the problem, and in the fitness function used to evaluate the quality of solutions, based on the problem characteristics. In this paper an extension of the genetic algorithm itself is described. Using correspondents to the Mitosis and Meiosis processes for cell division, a framework for an extended genetic algorithm is developed. Numerical results with benchmark problems show that the solution quality obtained using the proposed algorithm is superior to that achieved by application of the original Genetic Algorithm. However, proposed GA couldn’t intelligently control the populations for the rate of Meiosis and Mitosis. Manuscript II (in preparation for submission to Journal of Production Research) presents an intelligent controller to increase the performance of proposed GA and tested on the flow line sequencing problem to check the robustness of algorithm on real manufacturing problem. This part focuses on the general form of the flow line scheduling problem with the objective of minimizing the makespan. Fuzzy Cell Genetic Algorithm (FCGA) algorithm makes use of fuzzy logic to control the cell mechanisms intelligently, applied for flow line sequencing problems. This approach is intended to improve the performance of genetic algorithm in permutation flow line scheduling problems. A relative evaluation of the FCGA with well-known existing heuristic and metaheuristic methods on recognized benchmarks problems is presented. FCGA is found to be very efficient on examined problems in comparison with other algorithms which solved in permutation schedules for the problems. In Manuscript III (in preparation for submission to Journal of Operation Research), the novel algorithm (FCGA) has been tested on Flexible flow line problems, a more complex version of the flow line problem, to minimize the makespan for the process. Real world applications of this problem can commonly be found in printing and electronic circuit board manufacturing industries. A generalized integer programming (IP) model for this problem is proposed. The Fuzzy Cell Genetic Algorithm (FCGA) is proposed to solve the IP model, which has been proven to be NP-hard. Sample problems are generated with known good solutions to evaluate the effectiveness of the FCGA approach. The FCGA matches the performance of the IP model for small sized problem instances and it is proven to be effective for larger problem instances. The results show the robustness of FCGA for flexible flow line problems. Manuscript IV, (in preparation for submission to international of Production research) focuses on different manufacturing problems which are more specifically related to assembly line balancing problem. It is not simple to solve this class of manufacturing problem based on just a single objective; hence a multi-objective genetic algorithm has been designed. For automotive assembly, robots have been used to increase line productivity and efficiency, and improve quality. However, robot failures reduce the throughput rate and product quality. There are several ways of recovering from line failures. One approach is to establish a manual backup station dedicated to processing those jobs that were incomplete when the line failed, allowing the line to re-start with fresh jobs at each station. Operations performed at this station usually take longer, and are not commensurate in quality with the automated stations. Another approach, developed in this paper, is to design a line with some redundancy: in-line backup stations and a manual recovery station. The backup stations are part of the main line but utilize versatile robots. In this case, a line failure is handled by reconfiguring the backup stations to perform as many make-up operations as possible, but the manual backup station is used for tasks that are not very demanding in complexity or precision. A multi-objective Genetic Algorithm approach for line design and for reallocating tasks when failure occurs is presented. This system is compared with an alternate approach that configures the line with a high level of redundancy and uses a backup station for all recovery. A comparable throughput is achieved with lower levels of redundancy and with fewer jobs sent for manual completion