@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00229730,
 author = {沼口, 寛樹 and 呉, 偉 and 胡, 艶楠},
 book = {第85回全国大会講演論文集},
 issue = {1},
 month = {Feb},
 note = {ジョブショップスケジューリング問題は，複数の機械と複数の仕事が与えられ，各仕事が順序制約のある作業から構成されるとき，最大完了時刻等を最小化するスケジュールを求める問題である．機械数は2台として，機械間の搬送時間を考慮する．1つを除く全ての仕事は，全作業がいずれか片方の機械のみで処理される問題を扱う．まず仕事の数が入力として与えられる場合は強NP困難であることを示す．仕事が2つまたは3つであるケースに対して動的計画法に基づく多項式時間アルゴリズム，さらに尺取法の適用による計算量の改善手法を提案する．上記手法を一般化することで，仕事の数を任意の定数とするケースに対する厳密解法も示す．},
 pages = {409--410},
 publisher = {情報処理学会},
 title = {2機械ジョブショップスケジューリング問題における尺取法による計算高速化手法},
 volume = {2023},
 year = {2023}
}