確率的探索と確定的探索の組合せによるジョブショップスケジューリング問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
ジョブショップスケジューリング問題(JSSP)はNP-困難な組合せ最適化問題の中でも特に難しい問題のひとつとされている. 本論文では, 確率的な局所探索法であるシミュレーテッドアニーリング(SA)法を用い, これに確定的(deterministic)な局所探索法であるshifting bottkeneck(SB)法を組み合わせることによってJSSPの効率的な近似解法を提案する.現在のスケジュールに対して新たなスケジュールがクリティカルパス上の作業順序の入れ換えと, Giffer and Thompsonのアクテイブスケジュール生成法を用いて生成され, SAによって確率的に受理される. さらに, 受理されなかったスケジュールに対して, 本方法のために変更を加えたSB法が適用され, スケジュールは修正される. 修正されたスケジュールは改善が見られた場合に限って受理される. 本方法をよく知られたいくつかのべンチマーク問題に適用した結果, 解の品質において従来の近似解法を上回る結果を得ることができた.
- 1996-04-15
論文 | ランダム
- C-14Bis(2-ethylphenyl)phenylphosphonateのイエバエ体内における代謝産物のdiasteremeric選択性(一般講演)(支部講演会ならびにシンポジウム報告)
- 技術小講座 最近のネットワーク&サービスの動向
- 斉藤 孝著『歴史の感覚-同時代史的考察-』, 日本エディタースクール出版部, 一九九〇・七刊, B6, 二五八頁
- 技術小講座 ZigBeeで創るワイヤレス・センサネットワーク
- 社会科学の振興--ある経済理論研究者の視点 (特集 人文・社会科学の振興)