Multi-objective Local Search Combined with NSGA-II for Bi-criteria Permutation Flow Shop Scheduling Problem

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2012/01/01

タイトル(英語): Multi-objective Local Search Combined with NSGA-II for Bi-criteria Permutation Flow Shop Scheduling Problem

著者名: Xiu Wei (Graduate School of Information, Production and Systems, Waseda University), Wenqiang Zhang (Graduate School of Information, Production and Systems, Waseda University), Wei Weng (Graduate School of Information, Production and Systems, Waseda Unive

著者名(英語): Xiu Wei (Graduate School of Information, Production and Systems, Waseda University), Wenqiang Zhang (Graduate School of Information, Production and Systems, Waseda University), Wei Weng (Graduate School of Information, Production and Systems, Waseda University), Shigeru Fujimura (Graduate School of Information, Production and Systems, Waseda University)

キーワード: Flow Shop，Multi-objective Genetic Algorithm，Makespan，Maximum Tardiness

要約(英語): This paper proposed a multi-objective local search procedure (MOLS). It is combined with NSGA-II for solving bi-criteria PFSP with the objectives of minimizing makespan and maximum tardiness. Utilizing the properties of active blocks for flow shop scheduling problem, neighborhood structures MOINS (multi-objective insertion) and MOEXC (multi-objective exchange) are designed in order to improve efficiency of perturbation. Any perturbation based on MOINS and MOEXC takes effect on different criteria simultaneously. The original idea of MOLS is systematic change neighborhoods in the local search procedure. The search direction of MOLS on an individual is naturally guided by interaction of MOINS and MOEXC. Moreover, there is no need to set parameters in MOLS. The MOLS combined with popular multi-objective evolutionary algorithm NSGA-II (Non-dominated Sorting Genetic Algorithm-II) is called as “NSGA-II-MOLS”. To illustrate the efficacy of proposed approach, four different scaled problems are used to test performance of NSGA-II-MOLS. The numerous comparisons show efficacy of NSGA-II-MOLS is better than most of algorithms even with the same number of individual evaluations and parameters setting.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.132 No.1 （2012） 特集：確率的最適化と機械学習の統計的設計と応用

本誌掲載ページ: 32-41 p

原稿種別: 論文／英語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/132/1/132_1_32/_article/-char/ja/