A novel meta-heuristic evolutionary algorithm for multi-objective flow-shop scheduling problems

カテゴリ: 部門大会

論文No: OS5-3

グループ名: 【C】平成18年電気学会電子・情報・システム部門大会講演論文集

発行日: 2006/09/05

タイトル(英語): A novel meta-heuristic evolutionary algorithm for multi-objective flow-shop scheduling problems

著者名: 師 瑞峰(JANA Solutions),玄 光男(Waseda University),周泓 (Beihang University),程潤偉 (JANA Solutions)

著者名(英語): Ruifeng Shi(JANA Solutions),Mitsuo Gen(Waseda University),Hong Zhou(Beihang University),Runwei Cheng(JANA Solutions)

キーワード: Escalating evolutionary algorithm|multi-objective optimization|flow-shop|meta-heuristic algorithm

要約(日本語): The problem of multi-objective optimization by genetic algorithms (GA) was first systematically studied by Schaffer in his thesis in 1984, in which he proposed an algorithm based on what he called vector evaluation process [1]. The algorithm is, in fact, just a simply extension of GA with single objective, without considering very much the natures of multi-objective optimization. Hence it is not very efficient for finding a good non-inferior frontier. However, it does promote the efforts to solving multi-objective optimization problems by GA. Several years later, Goldberg gave a relatively comprehensive expounding on multi-objective genetic algorithm in his famous book published in 1989 (referred to reference [2]), in which he investigated and summarized some important profiles of applying GA to problems with multiple objectives, including non-inferior solutions classification and niching strategies, and provided some guidelines to the design of multi-objective genetic algorithms. Following these suggestions, Horn, Nafpliotis, Srivinas, Deb, Fonseca, Fleming and many other authors proposed various implementation schemes for searching non-inferior frontiers (referred to [3][4][5]). Among the existing investigations, niching strategy and elite strategy are regarded as powerful weapons for achieving good non-inferior frontiers[6][7]. Most of those approaches are developed for solving function optimization problems, especially for continuous functions. Ishibuchi and Murata [8] applied multi-objective GA to combinatorial optimization problems. They employed a kind of randomly weighted sum method to encourage the searching diversity in order to obtain more non-inferior solutions. The algorithm was applied to a flow shop scheduling problem and achieved a favorable result.

A novel escalating multi-objective evolutionary algorithm, which aims at solving multi-objective flow shop scheduling problem, was proposed in this paper. The proposed hybrid algorithm combined the meta-heuristic algorithms, which is adept at solving the specific objective optimization of flow shop scheduling problems, into a variable Pareto local search strategy during the population escalating process. Numerical experiments have been made, which employ the improved algorithm to solve 31 typical bi-objective flow shop scheduling problems from the benchmark testing data set. The optimization results have shown that, our new algorithm have got outstanding Pareto frontier in all test problems compared with that produced by NSGA-II and MOGLS with each algorithm have its own optimal evolutionary parameters, which futherly revealed the new algorithm’s outstanding efficiency and high performance in optimization for multi-objective flow shop scheduling problems.

PDFファイルサイズ: 4,716 Kバイト