Guided ejection searchの提案とジョブショップスケジューリング問題への適用

カテゴリ: 部門大会

論文No: TC3-7

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

発行日: 2011/09/07

タイトル(英語): Guided ejection search to the Jobshop Scheduling Problem

著者名: 永田 裕一(東京工業大学)

著者名(英語): Yuichi Nagata(Tokyo Institute of Technology)

キーワード: ジョブショップスケジューリング|メタヒューリスティクス|近似解法近似解法|job shop scheduling|metaheuristics|approximation solutio method|ejection chain

要約(日本語): 本稿では組合せ最適化問題に対する新しいメタヒューリスティクスの枠組みとしてGuided ejection searchと呼ぶ局所探索法を提案する．多くの組合せ最適化問題では実行可能解は解を構成する基本的な要素の分割や順列などで表現されるが，提案する方法は解要素の一部を一時的に無視した部分解を探索する．探索近傍は解要素の部分解への挿入と抜出しで定義されるが，提案法では近傍内の部分解のどの解へ遷移するかを決定するためにguided local searchのアイデアを用いる．提案する枠組みをジョブショップスケジューリング問題へ適用した結果を紹介する．

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