ジョブショップスケジューリングに対する機械分解によるラグランジュ緩和

DOI Web Site 被引用文献2件 参考文献11件

書誌事項

タイトル別名
  • Machine-Based Lagrangian Decomposition for Job Shop Scheduling Problems
  • ジョブショップスケジューリング ニ タイスル キカイ ブンカイ ニ ヨル ラグランジュ カンワ

この論文をさがす

抄録

Luhや米田らは, 納期系の評価尺度を想定した上で, 機械能力制約を緩和することで問題をジョブ毎に分解する(ジョブ分解)ラグランジュ緩和法を提案し, その実用性を立証している.一方, 長谷部らは作業の先行関係制約を緩和して問題を機械毎に分解する(機械分解)ラグランジュ緩和法を提案している.本研究では, ジョブショップスケジューリング問題を取り上げ, 機械分解に基づくラグランジュ緩和法(下界値と上界値の算出法)のプロトタイプを示した.次に, ジョブ分解, 機械分解という2種類のラグランジュ緩和法の特質を整理するとともに, 計算実験をもとに両者の比較評価を行なった.また, 機械分解で発生する解の振動に関して作業納期の導入によるいくつかの対策を施し数値実験を行い, その効果を調べた.これらから, i)振動対策を施さない機械分解は, 極めて振動が大きくジョブ分解に劣る, ii)作業納期の導入は, その納期の設定如何によっては良い上界値を得られることもあるが, 期待されるほどの振動の抑制は望めない, などの結果を得た.

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (11)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ