一つの付加線形条件を有する最小費用プロジェクト・スケジューリング問題を解くための辞書式制約付き流れアルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• この論文では、右辺がパラメータである一つの付加線形条件を有する最小費用プロジェクト・スケジューリング問題を解くためのアルゴリズムを提示する。付加条件をおく代わりに、そこに現れる関数にパラメータを乗じて、目的関数に組みいれる。まず、パラメータが0であるときの最適解を求め、次に、パラメータを∞まで大きくしていく。そうするために、与えられたアロー・ダイアグラム上で、2次元の流れを求めることをくりかえす。アロー上の流量に対しては、そのときに得られている解から上限と下限が定められる。上限、下限の第1成分は、費用に関連し、第2成分は、付加条件の係数に関連している。辞書式順序に関して、それらの制約を満たす流れを「辞書式制約付き流れ」という。辞書式制約付き流れが存在するときは、パラメータの値が増大し、存在しないときは、付加条件に現れる関数の値が増大する。この解法の主要部分は、一つの付加線形条件を有する最小費用流問題を解くための辞書式最短路アルゴリズムと双対的である。また、この解法は、二つの目的関数をパラメータによって結合することにより、二目的プロジェクト・スケジューリング問題にも適用できる。

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• 古林 隆

  埼玉大学

関連論文

• 最大流問題
• 最短路問題
• 一つの付加線形条件を有する最小費用プロジェクト・スケジューリング問題を解くための辞書式制約付き流れアルゴリズム
• 一つの付加線形条件を有する最小費用流問題を解くための辞書式最短路アルゴリズム
• ネットワ-ク流のモデリングと解法 (ネットワ-ク技術) -- (ネットワ-クに関する解析・設計・運用技法)
• ORにおける組合せ論的な問題とその解法 (組合せ論的システム特集号)

スポンサーリンク