確率的探索と確定的探索の組合せによるジョブショップスケジューリング問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
ジョブショップスケジューリング問題(JSSP)はNP-困難な組合せ最適化問題の中でも特に難しい問題のひとつとされている. 本論文では, 確率的な局所探索法であるシミュレーテッドアニーリング(SA)法を用い, これに確定的(deterministic)な局所探索法であるshifting bottkeneck(SB)法を組み合わせることによってJSSPの効率的な近似解法を提案する.現在のスケジュールに対して新たなスケジュールがクリティカルパス上の作業順序の入れ換えと, Giffer and Thompsonのアクテイブスケジュール生成法を用いて生成され, SAによって確率的に受理される. さらに, 受理されなかったスケジュールに対して, 本方法のために変更を加えたSB法が適用され, スケジュールは修正される. 修正されたスケジュールは改善が見られた場合に限って受理される. 本方法をよく知られたいくつかのべンチマーク問題に適用した結果, 解の品質において従来の近似解法を上回る結果を得ることができた.
- 1996-04-15
論文 | ランダム
- 実験的心不全ラットにおけるアミノ酸代謝
- 反対称性を有する二次元異方性複合領域の抵抗値
- 二本の鏡映対称軸を有する領域の抵抗値に関する特殊な性質
- 2.予測困難な垂直的下顎位の変化に対する下顎タッピング特性 : 咬合力と咬筋筋活動の調整(一般口演,第41回学術大会)
- 咬合物質硬度の予測できない変化に対する下顎タッピング力の調節