確率的探索と確定的探索の組合せによるジョブショップスケジューリング問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
ジョブショップスケジューリング問題(JSSP)はNP-困難な組合せ最適化問題の中でも特に難しい問題のひとつとされている. 本論文では, 確率的な局所探索法であるシミュレーテッドアニーリング(SA)法を用い, これに確定的(deterministic)な局所探索法であるshifting bottkeneck(SB)法を組み合わせることによってJSSPの効率的な近似解法を提案する.現在のスケジュールに対して新たなスケジュールがクリティカルパス上の作業順序の入れ換えと, Giffer and Thompsonのアクテイブスケジュール生成法を用いて生成され, SAによって確率的に受理される. さらに, 受理されなかったスケジュールに対して, 本方法のために変更を加えたSB法が適用され, スケジュールは修正される. 修正されたスケジュールは改善が見られた場合に限って受理される. 本方法をよく知られたいくつかのべンチマーク問題に適用した結果, 解の品質において従来の近似解法を上回る結果を得ることができた.
- 1996-04-15
論文 | ランダム
- 2F15-2 96 ウェル形質転換法を用いた酵母における異種ラッカーゼ生産に関するゲノムワイド解析
- 375 酵母の遺伝子破壊株セットを用いた乾燥耐性に必要な遺伝子の網羅的解析(代謝工学,一般講演)
- 435 酵母遺伝子の発現制御を可能とするワンステッププロモーター導入システムの開発(遺伝子工学,一般講演)
- 436 酵母を利用した新規生理活性物質の探索と解析(遺伝子工学,一般講演)
- 756 清酒醸造酵母における栄養要求性マーカーを用いた遺伝子操作系の開発(醸造・醸造工学,一般講演)