線学生論文賞受賞論文

要約機

OnDiscrete‑
TimeSingle圃Server Queues
wit
hMarkovModulatedBatchBernoulliInpu
tandFiniteCapacity
土屋利明(東京工業大学大学院理工学研究科情報科学専攻

現所属 :NTT)

指導教官高橋幸雄教授れる.ここで ， {Yn } は M 状態の時間離散型マルコフ主主1. はじめに

鎖で待ち行列のモデルが利用される分野の l つに，通信シYη の値が第 n スロットにおける客の到着過程の状態を表現し

X n は時点 n における系への客の到着数
X n の分布をYn の値に依存させるこステムにおける性能評価がある.通信システムの分野を表現している .

で現在最も注目されているトピックスの 1 つとして，とで，パースト性，および相関性をもたせることが可能

B‑ISDN (broad‑band integratedservicedigitalとなる.また，サービス時間はすべての客について互いnetwork) におけるATMMode: 非同期転送モード)(AsynchronusTransferに独立かつ同ーの一般分布に従うものとする.さらに，システムのモデル化および系内の客数(サービス中の客を含む)の上限を K( パッゾ

その評価法があげられる.このようなシステムをモデル

ァ・+イズと呼ぶ)とし，客の到着数とすで‘に系にいる化する際に考慮しなければならない特徴としては，客数との和が K を超えた場合には ，K を超えた分だけの(1)時間離散型であること

客が，サービスを受けずに系を離れる(損失あるいは呼(2)入力が再生型でなく，パースト性および相関をもっ損と呼ぶ)ものとする.
以上に述べたようなタイプの待ち行列モデんを，ここていること(3)待合い室の容量が有限であり，したがって客の損失

では MMBP/G/1/K で表わす.に述べた特徴のうち，があること(4)客のクラスが複数あり，それぞれのクラスがサ}ビ
スの品質に関して異なった要求をもつことがある.これまでにも，上にあげた特徴をそれぞれ個別

このモデんは最初(1)から (3) までを有している.

(4) に関しては，損失確率(呼損率)の上限について異なった要求をもっ 2 種類の客のクラスを仮定する.
異なる要求を同時に満たすためクラス毎に

4 節ではスペースプラにとらえた待ち行列モデルは扱われているが，本論文でイオリティと呼ばれるサービス規律を導入する.比較のはこれらすべての要素をとり入れたタイプの待ち行列モため

デル(MMBP / G /1/K) について考察を行なう.

2.

3 節では客のクラスを区別しないで，先着順にサービスを行なうようなモデルについて考える.

3. 客のクラスを区別しない MMBP/G

毛デルの説明

ここで扱うシステムは時間離散型である.時間軸上の区間 (n -1 , n) を第 n スロットと呼ぶことにする.客は/l/K 毛デル
客のクラスを区別しないモデルでは，クラスにかかわ各スロットの初めに系に到着し，叶ーピスを受け終えたりなし先着順にサービスを行なっていくものとする.

ならば，スロットの終りで系から退去する.したがってしたがって，事実上単ークラスの(通常の)待ち行列七客のサービス時間はスロットの数で表わされる.

パースト性および相関をもっ入力を表現するため，本
論文では時間連続型の MMPP

Poisson Process)558 (48)

こちらのモデノL を NP (No Priority) と呼ぶ.

(Markov Modulated

MMBP/G/1/K 型の系の状態を表現するために，

MMBP (Markov

第 n スロットにおける客数，およびサービス中の客の残に類似した，ModulatedBatchBernoull
iProcess)
L 、る. MMBP はデノ~:を考えることになる.次節で述べるモデルとの区別のため，なる過程を用

2 変数過程 {Yn ， Xn} の形で表現さりサービス時聞をそれぞれ Nη ， Rn で表わす (N.π=0ならば ，Rn=0 とする).

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

すると，先に述べた Yn を加オペレーションズ・リサーチ

えた 3 変数の過程 {Nno Rn , Yn} は，マルコプ連鎖となるので，状態方程式を作り，そこから定常確率を求めることができる.解くべき状態方程式系はRn の値 t ごとに状態を13:;ゴlゴ 11
図 1に表現することができる.

ここで ， r (l} はすべての状態確率のうち，Rn=1 の場合を並べた KM 次元ベクトル，(Mは Yn の状態の数 ). (1)式を解くことで，NP

図 2

スペース・プライオリティを用いた

MMBP/G/l/K 毛デルトー-SI 一一斗

パップ 7 ・リザベーションを用いたモデル

後方に並ぶことが許される.クラス l の客は，いったんパップァに並んだとしても，順番がふ以下となるまでは，サービスを受けられなくなる可能性が残っていることになる.しかしながら，サーピス時間分布が各グラス仮定する 2 種類の客を，ここではクラス 1 ，クラス 2の客と呼び，クラス 2 の客の方が呼損率の上限に関してより厳しい要求をもち，プッシュアウトを用いたモデルj
卜 S2 = J(‑ SI ‑の系内数分布や呼損率のような評価尺度が求められる.

4.

111 ト①一81一一→!R出叫」」2 よlU|;;:山出αJ川|ハ| 百日日) |い川I I|令h は客のサーピス時間が t である確率 ， A ， C ，V はすべて KMxKM 確率行列である

1111 .
.
.

ムト 82 =J(‑ 81 I

まとめてベクトル表示することで，次のようr(l)=br(1)CV+r(l+l)AV,tl=I , 2, …(1).
.
1.

クラス 1 の方は待ち時間の上限

共通と L 、う仮定から，+ーピスを受けられなくなる客の総数は，NP の場合と変わらない.したがって，システムの系内数分布および全体の呼損率に関しては3 節のに関してより厳しい要求をもつものと仮定する.このよ結果をそのまま用いることができる.

うなクラスごとに異なる要求を同時に満たすようにする

率の求め方は簡単ではないが，本論文では n 番目の位置ために，プツ‘ンュアウト (PO) およびバッファ・リザベにいるクラス l の客が最終的にサーピスを受けられる確ーション (BR) と呼ばれる 2 種類のプライオリティを用率のクラスごとの呼損n に関する再帰的な表現を導き，そこからクラスいたモデルを考える.これらの方式では，大きさ K のパ1 の客の呼損率が求められる.クラス 2 の客の呼損率はと後(大きさ S2=K-Stl

クラス 1 の客の呼損率と全体の呼損率からただちに求めップァを前(大きさ SI s， K)とに分け，到着客の受け入れ方に関してそれぞれ異なっられる.

た制御を行なう.パッファの状態で客の受け入れ方が決

4.
2 パ・7 ファ・リザベーション方式

まるので，このような方法はスベース・プライオリティ

パッファ・リザベーション方式では，プツ‘ンュアウトと呼ばれる.ちなみに，従来考えられてきたサービスの方式とは異なり，ぬより後ろの順番にクラス l の客が並順序を変更する方式は，主に待ち時間に着目したものでぶことは許されず，クラス 2 の客のみが並ぶことができあり，これはタイム・プライオリティと呼ぶ.以下ではる.

同時に到着した客の集団の中ではクラス 1 の客の方が必の)客の損失が起こりうる.このことは，解くべき状態ずクラス 2 の客よりも前にいるものとし，サービス時聞方程式系 (1) が， NP ある L 、は PO とは異なったものとなは各クラスとも共通の分布に従うとする，る(具体的には，したがって，系に空きがある場合でも，(クラス 1

行列 AV ， CV の要素)ことを意味し

4.
1 プ."}シュアウト方式ている.しかし，一度状態方程式を解き終えたならば，プッ、ンュアウト方式では，以下のような制御を行なう.

客のクラスごとの呼損率は PO の場合よりも容易に求め客の損失が起きな L 、かぎりは，システムはあたかもクラられる.なぜならば，客はその到着時点でのみ損失となスが l つしかな L 、かのごとくふるまう.到着客と系内のりうるので，到着時点、での系内数分布さえわかればクラ客数の和が K を超えて，スごとに呼損率が求められるからである.到着時点でのしかもバッファ内での順番が 8 1を超えるようなクラス 1 の客が L 、た場合 ，NP ならば損分布というのは一般には定常状態の分布とは異なるが，失とされたはずのグラス 2 の到着客が，列の一番後ろに両者は Conditional GASTA と呼ばれる性質で関係いるクラス 1 の客を押し出して，かわりにパッファの最づけることができる.

1992 年 11 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(49)5595.

算を行なし、，比較を試みた.結果として，数値計算

NP に対する優位性が確隠され，PO ,BR のPO と BR とでは，比SI の値とク較する条件をどう決めるかで評価が変わることがわかっ

ラスごとの呼損率の関係や，客の到着率と，呼損率の上た.なお，詳しい条件および結果については，本論文を限を保証するために必要なパップアサイズとの関係につ参照されたい.

M=2 ， 単位サービス

いて，NP , PO ,(b 1 = 1)

として ，BR それぞれの場合について数値計

襲撃学生論文賞受賞論文

要約繊般化グルーピンゲ問題
伊藤稔(東海大学大学院工学研究科経営工学専攻

現所属:日本ユニシス)

指導教官羽田隆男助教授

1.

,(1 ，対象 i が，対象 j を中心としたグループ

はじめに

Xij=に含まれる場合\.0，その他の場合

多数の対象を，対象聞の類似度に注目して，複数のクとすると，一般化グルーピング問題 (G) は，同次クララスターに分割する問題をとりあげる.

多数の対象を，その対象間の類似度に注目してグルースタ}問題における各グループに，L:̲ GtXij;孟 C， jEN

プ分けをする問題は，同次クラスター問題として古くか'ENら一般に知られており，統計学等の分野に応用されていただし ，ai ( 主主 0，iEN): 対象 t が使用する資る.一方，配送計画や工程のライン編成問題など経営工源の量学的な諸問題に，この向次クラスター問題を適用しよう

C主~a i> iEN): 各グループが使用とすると，分割するクラスター数の制約だけでなく，各クラスターごとに使用できる資源に制約が加わる問題となることが多い.

できる資源の総量であるナップザック制約を付け加えて得られる問題，

min L:L: du Xu

たとえば，配送計画では，配送センターの商品を多数

iEN jε N8.t.の配送先に，複数のトラックで配送しようとすると，各L:
̲̲ xiJ=I , jEN ...・ H ・・ (1)トラックが受けもつ配送先が 1 つのクラスターであり，(G)4J

ndAm 宅'・Nd・

対象の集合 N={ 1 ， 2 ，...，1I} と，対象 i ，1}, i , jEN…… (5)を考える.

かを判断する 0-1 変数 Xjj ， jEN を，それ以外の変数

0-1 変数 Xij:をと明確に区別するため，

JE三 N 閣の類似度 d ij (値が小さいほど類似していると見なす)

制初(晋0)

C.
.
.
(2)

ここで，対象 j を中心としてグループを構成するか否一般化グルーピング問題の解法与えられているとき，

2/ 与一

2.

aJf間の面からその実用性を検討する.

,

XijE三 {O ，ラスター問題を[一般化グルーピング問題 j と称し，分校限定法にもとづき，より効果的な解法を考え，計算時,21クラスター数と資源に制約のあるクZjj=h/与一

qZH関係が資源制約となる.
本修士論文では，

jz
NLー内の配送先への総配送量とトラックの積載量制限とのe‑‑クラスタ

WZ

所有するトラック台数がクラスター数の制約，iENが以下では便宜上 0-1 変数曹 j，jEN と表現する.

解法としては，分校限定法の下界値計算に， (1)式を釘的関数に組みこんだラグランジェ緩和間短 (Ll' lx，© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

百)オベレーションズ・リサーチ