グループ制約付き大規模ジョブショップ問題におけるジョブ自由度分析及びタブー<p>サーチによる高速立案方式

カテゴリ: 部門大会

論文No: GS17-3

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

発行日: 2003/08/29

タイトル(英語): A High Speed Scheduling Method by Analyzing Job Flexibility and Tabu Search for A Large Scale Job Shop Problem with Group Constraints

著者名: 大前寿敏 (大阪大学),石原 杏平(大阪大学),一階 良知(大阪大学),堀内 邦義(新日鉄ソリューションズ),濱本 英宣(新日鉄ソリューションズ)

著者名(英語): Hisatoshi Omae(Osaka University),Kyohei Ishihara(Osaka University),Yoshitomo Ikkai(Osaka University),Kuniyoshi Horiuchi(NS Solutions),Hidemobu Hamamoto(NS Solutions)

キーワード: ジョブショップ問題|グループ制約|自由度分析|タブーサーチ|job shop problem|group constraints|flexibility analysis|tabu search

要約(日本語): 本研究では、複数の処理工程を必要とするジョブを各ラインに割当てるジョブショップ問題の中でも、各処理工程ごとに同処理が必要なジョブを複数まとめたグループで処理を行う必要がある問題を対象とする。本問題はジョブ数2000程度の大規模な組合せ問題であり、全ジョブの平均製造工期、グループ切替回数、ライン休止回数の3項目で評価される。このなかで、様々な制約を満たして評価の高い解を生成するには効率的な手法が必要となる。

そこで本研究では、ヒューリスティクスにより高速に得られた初期解に対してタブーサーチを用いた改善を繰り返す手法を提案する。この手法を現実の問題に適用し、専門家の手作業による解と評価比較を行った結果、1時間以内の実用的な時間で、評価比較が96%以上の解を得ることができ、本手法の有効性が確認された。

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