2機械ジョブショップスケジューリング問題における尺取法による計算高速化手法

情報処理学会

この論文をさがす

抄録

ジョブショップスケジューリング問題は，複数の機械と複数の仕事が与えられ，各仕事が順序制約のある作業から構成されるとき，最大完了時刻等を最小化するスケジュールを求める問題である．機械数は2台として，機械間の搬送時間を考慮する．1つを除く全ての仕事は，全作業がいずれか片方の機械のみで処理される問題を扱う．まず仕事の数が入力として与えられる場合は強NP困難であることを示す．仕事が2つまたは3つであるケースに対して動的計画法に基づく多項式時間アルゴリズム，さらに尺取法の適用による計算量の改善手法を提案する．上記手法を一般化することで，仕事の数を任意の定数とするケースに対する厳密解法も示す．

収録刊行物

キーワード

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

問題の指摘

ページトップへ