軽野 義行 (教授)
多目的0-1ナップサック問題に対する動的計画法の適用
- 多目的0-1ナップサック問題に対して動的計画法を適用し，辞書式配列法に基づく多目的決定を擬似多項式的な計算手間で行うアルゴリズムを提供する．
- 食品製造業における自動化工程の一例として，組合せ計量装置による袋詰めがある．この装置はある種の多目的0-1ナップサック問題を解きながら袋詰めの作業を行うが，0-1変数ベクトルの列挙に基づいたアルゴリズムはホッパ数に対して指数関数的な計算手間を要する．各ホッパに投入される食品の重量の上限値が極端に大きくないならば，本手法はホッパ数に対して多項式的な計算手間で動作するので，装置の性能解析に必要な計算実験も実施し易くなる．