2機械ジョブショップスケジューリング問題における尺取法による計算高速化手法
Search this article
Abstract
ジョブショップスケジューリング問題は,複数の機械と複数の仕事が与えられ,各仕事が順序制約のある作業から構成されるとき,最大完了時刻等を最小化するスケジュールを求める問題である.機械数は2台として,機械間の搬送時間を考慮する.1つを除く全ての仕事は,全作業がいずれか片方の機械のみで処理される問題を扱う.まず仕事の数が入力として与えられる場合は強NP困難であることを示す.仕事が2つまたは3つであるケースに対して動的計画法に基づく多項式時間アルゴリズム,さらに尺取法の適用による計算量の改善手法を提案する.上記手法を一般化することで,仕事の数を任意の定数とするケースに対する厳密解法も示す.
Journal
-
- 第85回全国大会講演論文集
-
第85回全国大会講演論文集 2023 (1), 409-410, 2023-02-16
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1050016803517064320
-
- NII Book ID
- AN00349328
-
- Web Site
- http://id.nii.ac.jp/1001/00229620/
-
- Text Lang
- ja
-
- Article Type
- conference paper
-
- Data Source
-
- IRDB