Studies on Multi-objective Evolutionary Algorithms with Applications to Production Scheduling


Abstract

Multi-objective scheduling is a typical combinatorial optimization problem in the production planning area, whose optimal solutions lie in a complex space with multiple conflicting optimization objectives, and can hardly be solved with traditional optimization techniques. An annotated survey on the state-of-the-art of current multi-objective evolutionary algorithm study with it’s applications to production scheduling problems was made in this paper, then a new multi-objective evolutionary algorithm named as EMEA is proposed, which is based on an escalating evolutionary strategy and a meta-heuristic problems-dependent Pareto local search strategy. The empirical studies have shown the high efficiency and excellent effectiveness of our new algorithm. The main work of this paper can be summarized as the following: 1. A brief review of the history and current studies of multi-objective evolutionary algorithm and multi-criterion scheduling problem was brought out. Based on the summarization of the advantages and disadvantages of multi-objective genetic algorithms that have been proposed during the past twenty years, the difficulties in innovations on the progress of multi-objective evolutionary algorithm were analyzed. 2. A hybrid multi-objective evolutionary algorithm is proposed based on an escalating evolutionary structure, which can overcome some deficiencies in evolutionary convergence and efficiency among current algorithms. The proposed escalating evolutionary structure in the new algorithm can improve population diversity preservation and local search capability. The proposed new elitism duplication strategy can effectively guide the searching directions without the need of calculating the individual’s fitness in the evolution. The new EMEA has been applied to optimizing a test suite including seven typical multi-objective optimization problems with continuous functions, the experimental results show that EMEA have better convergence performance in most of these test problems compared with NSGA-II and MOGLS, two famous algorithms common in use. 3. A hybrid multi-objective evolutionary algorithm, which aims at solving multi-objective flow shop scheduling problem, was proposed in this paper. The hybrid algorithm combined the meta-heuristic algorithms, which is adept at solving the specific objective of flow shop scheduling problems, into a variable Pareto local search strategy during the escalating process. Numerical experiments have been made which employ the improved algorithm to solve 31 typical bi-objective flow shop scheduling problems and one typical tri-objective flow shop scheduling problem. The optimization results have shown that, our new algorithm have got outstanding Pareto frontier in all test problems compared with that by NSGA-II and MOGLS, which futherly revealed its efficiency and effectiveness in optimization for flow shop scheduling problems. 4 A hybrid multi-objective evolutionary algorithm on solving job shop scheduling problems was proposed. A new meta-heuristic decoding algorithm, which is based on utilizing the characteristic of operation-based gene coding, was proposed in this paper. A new fitness assignment strategy, which combined the diversity preservation with Pareto ranking depth, was proposed, which help decrease of the complexity of the algorithm. The proposed algorithm, together with NSGA-II and MOGLS, are applied to 82 typical bi-objective job shop scheduling problems and 5 typical tri-objective job shop scheduling problems for comparisons. The optimization results have shown that the proposed algorithm in this paper has better convergence performance in most cases, which illustrate the effectiveness of it. 5. The new algorithms have been applied to the real production situations of a manufacturing company. In order to deal with the conflicts in milling machines, a hybrid hierarchical scheduling model, which is based on the decomposition and coordination strategy, was proposed. An improved hybrid escalating multi-objective evolutionary algorithm, which aims at solving sub-problems of the hierarchical model, was also proposed. The comparison results of the optimization by our new algorithms with those by the factory schedulers have shown that, the new decomposition and coordination algorithm have significant improvement on makespan.