設備更改のスケジューリング問題に対するグラフ理論的考察
佐藤　全寛 1. 序論

設備更改のスケジューリング問題とは，通信サービス等において，既存の設備 を更改する際に，増収効果が最大となるように更改順序を決定する問題である[1]． この種のスケジューリング問題を解くためには，各ユーザと各設備との利用関係を 正確に把握する必要がある．本研究では両者の利用関係を2部グラフによって表現 し，2部グラフの分解原理としてごく前から研究されている基本分割の手法を適用 する．特に，1期間に1つずつユニットを更改する場合，基本分割の各成分毎の部分 問題の最適解を合成することによって全体の最適更改順序が得られることを示す．

2. 問題の設定

通信サービスを利用するユーザに，より質の高いサービスを提供するために各期 間t毎の予算制約b(t)内で既存の通信網の交換機ユニットを順次更改する．接続す る全てのユニット集合が更改し終わったユーザxには，新しいサービスが提供でき， それ以降毎期間，一定の新たな収入p(x)を得る．ユニットyの更改費用c(y)は各ユ ニット毎に決まっている．計画終了までの増収効果を最大にする更改順序を求めた い．
期間tまでに更改されたユニット集合をY(t),ユニットの部分集合をY，Yを更改した 時に収入を得るユーザ集合をX(Y)とすると問題は次のように定式化できる．
Maximize summarize{t} p(X(Y(t)))
subject to c(Y(t)\Y(t-1)) =< b(t)
(t=1,2,...,T)

3. 2部グラフの基本分割

この問題を解く手法として，各ユーザと各設備間の利用関係を2部グラフで表し
g(Y,k)={c(Y)}-k{p(X(Y))}
という関数を定める．ここで，kを固定した時にgの値が最小となるユニット集合を， 対応するkの小さいものから順にY{i} (i=0,1,...)とする．ただし，kを固定して最 小の値をとるg(Y,k)を結んだグラフに端点でのみ接する直線に対応するユニット集 合は除く．この Y{i}について，添字の小さいものは大きいものの部分集合となって いる．ユーザ集合UをY{i}\Y{i-1} (i=1,...)に分割することを基本分割という．

4. 最適更改順序の構造

ユニット集合Y{i}を更改した時の費用とその時の収入を投資-収入折れ線グラフ上 にプロットした点を線分で結んだ関数は区分線形凹関数となる．またY{i}以外のユ ニット集合Yの更改費用とユーザ集合X(Y)からの収入は，各投資額における折れ線グ ラフの値を越えない．
このことから, 基本分割を利用した更改順序の有用性が示唆される. 実際, 1期間 に1ユニットを更改する問題に関して，以下の定理を得た.

定理: 1期間に1ユニットを更改する場合，最適更改順序はY(|Y{i}|)=Y{i} (i=0,1,...)を満たす．

基本分割は，効率的に計算するアルゴリズムが知られているので，大規模なスケ ジューリング問題を解くための前処理として有効である．基本分割の各成分内での 最適更改順序の求め方は今後の課題である．
一方，1期間に複数個のユニットが更改できる場合には，基本分割によって問題を 分解しても最適更改順序が得られない例も存在する．しかしこの場合でも，近似解を 得るための発見的手法として，基本分割を用いることは有用と思われる．

参考文献
[1]須藤・井上: 設備更改計画のグラフ理論的検討, 日本OR学会1994年度春季研 究発表会.