111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111/1111111111111111111111111111111111111111111111111111

論文誌掲載論文概要
Vol.35, No.3
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
11
11111111111111111111111111111111
1
1
1
1
1
1
1
1
1
1
1
11
1
1
11
1
1
1
1
1
1
1
1
1
1

多重休暇期間をもっゲート式 MjGjl 待ち

ペルヌーイ・スケジュールに従う 2 クラス

行列についての優先処理方式の待ち時間分布の解析
富山県立大学片山京都大学遁根哲哉，畏谷川利治

NTT 通信網総合研究所高橋敬隆

休暇期間をもっ待ち行列モデルは計算機通信システムや生産システムの数学的モデノレとして活発な研究が行な動

本論文で提案するベルヌーイ・スケジュールに従う優われている.特に全処理式 M/G/1 待ち行列については先処理方式は ，N クラスの呼(処理要求)の優先度が，(P h P 2 ，・・ ， P N ) により調節可能なこと定常解のみならず，時間依存型解析も行なわれている.

可変パラメータ

本論文では多重休暇期間をもっゲート式 M/G/1 待ち行を特長とし，列について考察する.ゲート式モデルは全処理式モデノL

0 ，… ， PN=O) や交番優先処理 (P 1 =P 2 = … =P N = 1)と並んで最も基本的な休駁期閣をもっ待ち行列モデルのなどを特別な場合として含むより一般化された次のスケ通常の非割り込み優先処浬

(Pl=l ， P2=1 つである.しかし従来の研究では定常解のみが解析さジューリングに従う処理方式である: I クラス i の呼の処れており，時間依存型解析はその困難さのために行なわ理が終了した時点、に，クラス z の呼とそれより優先度のれていなかった.本論文は多重休暇期闘をもっゲート式

高いクラス J の呼 (i>j)があれば，次に確率 P t でM/G/1 待ち行列の時間依存型解析を行なう.まず 2 章

クラス i の呼を処理し，確率 1-P t でクラス j の呼を処において，従来の研究とは全く異なる接近法を用いて待理する.これ以外の場合には，システム内の最上位のクち時間の極限分布のラプラス変換形を導出する.結果はラスの呼を常に処理する J

すでによく知られたものであるが，この解析を通じて，論文では，扱い者(プロセツサなど)が空き状態に到ゲート式モデルの確率的構造を明らかにする.つづいて着した呼に対してそのクラスに対応した準備時間

3 章では2 章における考察にもとづいてゲート式モデup time) を伴う 2 クラスの優先処理方式 (N=2) をルの再生ザイクルについて考察する.これは通常の待ち取り扱い，各クラスの呼の待ち時間分布や平均待ち時行列における全稼働期間に相当し，最も基本的な性能尺間，待ち率等の評価式を導出している.

度の l つである.ここでは再生サイクルのラプラス笈換形を導出する.

総合+ーピスディジタル網 (ISDN)(set-など複数種のサ

4 主主では 3 章の結果を用いてゲート式モーピス要求を効率的に実現する必要のある通信システムデルの時間依存型解析を行なう.待ち行列長，システムの呼処理方式には，柔軟できめ細か L 、品質制御が要求さ内残余仕事量，待ち時間に対するさまざまな公式が導出れる.提案の優先処理方式は，可変パラメータを調節するされる.最後に 5 章では消滅時間を考える.消滅時間はことにより各クラスの待ち時間特性を容易に制御でき，ある特定の時刻からそれ以降最初に客がシステム内から多種類の処理要求を統合的に処理するシステムへの応用すべて立ち去るまでの時間として定義され，システム運が期待される.また，本論文の解析結果を用いて，各ク営上の観点から興味ある量である.ここでは消滅時間分ラスの平均待ち時間が関係するような総合的なシステム布のラプラス変換形を導出する.のコスト関数のもとに， "T 変パラメータを最適化するなどの検討が可能である.

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

(45)555

を浴びている.従来の研究の多くは顧客の需要(どの地網形成費用配分問題

点からどの地点にどれだけの物を運ひたいか，どれだけ早稲田大学久保幹雄，春日井博
われわれは社会、ンステムを構築するうえで，コミュニの情報を流した L 、か等)が確定的にわかっているという仮定のもとで，網を構築するための費用と物(または情コンビュータの報)が流れるときの費用の合計を適正化することを目的回線など種々の網を形成している.このとき網を構築すとしていた.本研究では顧客の需要に関する情報が不確るための費用は何人かの人(または会社や学校)が共同実性をもっているときの網構築法を考える.この問題はして出資したものであり，社会システムの公平性のため確率的網形成問題としてモデル化される.問題の目的はには費用分担の公平な配分が必要となる.本研究では，需要が確率的に発生するときに網全体の期待費用の算出

この問題を網上における協力ゲームとしてモデル化し，を行なうことである.

ケーション網，流通網，ケーフツレ TV ，実際には，確率的に生起する母集団の数が非常に多くゲームに参加するすべてのプレーヤーが満足するような配分を考える.ここではすべてのプレーヤーが満足するまた需要の発生が確定的にわかっている問題が組合せ的ような費用の配分方法として，ゲーム理論のコアの概念に解くことが困難な問題のクラスに属するため，網構築を取り入れる.ここでコアとは，ゲームに参加するすべに関する費用の期待値を求めることは理論上は可能だがてのプレーヤーが全員で提携して網を形成するような費現実には容易でない.ここでは期待値の上界と下界を計用配分の集合である.

算することによって，その代用とする方法を用いる.上協力ゲームを規定する特性関数は網形成問題を解くこ

界は網内で使用する枝に制限を加え，物(または情報)のとによって得られ，網形成問題が巡回セールスマン問題，流れる道をあらかじめ規定しておくことによって求める最小木問題，ことができる.本研究ではこれを事前網戦略 (aスタイナー木問題なと拘種々の応用上重要なpriori問題を含んでいることから，本研究で考える網形成費用network strategy)

配分問題は従来の巡回セールスマン，最小木，スタイナ度や事前網構築のための近似解法について解析を行なっー木費用配分問題の一般化と考えられる.ている.また，下界は多面体論における諸概念を確率的と呼び，事前網を用いたときの精網形成問題自身は組合せ的に解きにくい問題であるのなものに拡張することによって得ることができる.本研

で P*NP の仮定のもとでは特性関数を決めるためには究では確率的網形成問題に特有の確率的な妥当不等式を網の大きさの指数オーダーの時間がかかり，またコアを導いている.これらを切除平面法に組み込むことによっ定義通りに計算するには各々の提携(プレーヤーの部分て下界の導出が可能になる.また，簡単な例を用いるこ集合)に対して特性関数を決める必要があるので，このとによって導いた方法の解説を行なっている.

ような方法は非常に小規模の網以外には適用不可能である.また，網形成費用配分問題のコアが存在しないこともあり得ることがコアが空の例を示すことによって証明

2 回配送プッシュコントロールシステムにおける最適 2 回目の補充方法に関する研究されている.本研究では上で述べた困難さを克服するた

東京工業大学曹

めに特性関数の下界を用いることによりコアの一般化を

徳弼，園川隆夫

本論文ではつの中央倉庫 (CW)と m 個の地方倉行な L 、，その存在を示している.下界を用いることによ

庫るコアは緩和されたコアと呼ばれ，ラグランジュ緩和法テムを対象とする.システムの補充はサイクノレを用いることによって得ることができる.このコアを拡ごとに一定であり，各サイクノレの開始時にシステムに在張した概念を用いることによって，プレーヤーが共同で庫を補充する.このとき，所定量の在庫を CW に留保す網を形成するときの費用分担の指標を得ることができると同時に，残りを各 BW に直送する.そして，る.

(BW) からなる 2 段階プッシュ・コントロールシス(H期)

CWは各 BWにおける在庫と需要情報をモニターしながら，CW に留保している在庫をサイクル中のある時期に適宜 B

確率的網形成問題

Wに割りつける.このシステムの目的はシステムの平均早稲田大学久保幹雄，春日井博

欠品数を最小にすることである.本研究では2 回目の網形成問題とは効率的な流通網または伝達網を構築す

配送時期，需要条件などに関して Jonsson and S
ilver

るための数学的モデんであり，最近多くの研究者の注目のモデルを拡張し，これにもとづいて最適な 2 回目の補556(46)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

充時期を決める.ここで特に2 回目の補充時の最適割変換によってパラメトリック計画法の適用が可能となりつけルールを横持ちを許さない条件のもとで導出し，る.具体的には大域的 ε ー最適解を有限解の反復で求めシステムの平均欠品数を最小にする最適な 2 回目の補充る分校限定法を提案する.線形計画問題に線形乗法制約時期の存在を示す.最後に，システム環境(たとえば，式を 1 本追加した問題に対して計算機実験を行なったと需要の変動係数，留保量と総在庫量との比率，補充サイころ，提案するアルゴリズムは実用的であることが示さ

クノL の長さ，れた.

BW の数など)と最適な 2 回目の補充時期との関係を明らかにする.

多重サーバー・バケーションをもっ M/G/

凸乗法制約が追加された凸計画問題に対す

l//N待ち行列の解析と，そのポーリソグ・るパラメトリック逐次過小近似法

毛デルへの応用東京工業大学久野誉人，今野浩

日本アイ・ビー・エム制

筑波大学山本芳嗣

高木英明

本論文では，まず有限母集団でサーパーのバケーショ

本論文 11 ，凸最小化問題に凸乗法制約式が l 本追加さンをともなう M/G/ 1//N 待ち行列システムの詳しい解れた問題を解くアルゴリズムについて述べたものであ析を行なう.定常状態を仮定して，稼働期間とパケーシる.凸乗法制約式とは2 つの凸関数の積が一定値以下となることを求めるもので，ヨン期間の再生サイクノレの分析からシステムのスループ

VLSI チップの設計やミクロ経済学などに用いられる.一般にットや平均待ち時間などの性能評価尺度が簡単に得られ2 つの凸関数の積る.また，任意、時刻における待ち行列の長さと経過サーは凸関数でも凹関数でもなく，対象となる問題の実行可

ビス時間もしくは経過バケーション時間の結合確率分布

能領域は凸集合とならない.したがって，複数の局所最の解析から待ち時間の分布関数が導かれる.

適解が存在するため，通常の解法を用いて大域的な解をつづいて，これらの結果を有限母集団をもっ巡回サー求めることはできない.

ビス多重待ち行列(ポーリング・システム)の解析に応

本論文では，一連の凸計画問題を解くことで，この非用する.後者は，トークン・リング LAN が有限数の対凸計画問題が解けることを示す.アルゴリズムの基本と話型ユーザーをもっコンビュータを接続しているモデルなるのは，元の問題が，パラメータを導入することで次となるものである.対称形システムについていくつかの元の 1 つ高い同値な問題に帰着されることにある.この数値計算例が与えられている.

雑誌 EJOR 購読者募集
EuropeanJournal of Operational Research (EJOR) は，
Association of European Operational Research Societies(EURO)と North Holland

1993年は，Vol.64-71 が発行されます.

出版社との共同出版によるもので，個人購入もできますが，当学会では割引価格でお取り扱し、しています.
発行回数:年 24 回( 8 巻，24間)

使用言語:英語
内容:あらゆる分野における OR に関する優れた論文，連絡事項として， letters や新刊書(最近 1 年間のもの)介)，の批評，短評(紹1993年購読料個人 30 ， 000 円(送料込)，大学 180 ， 000 円

お申し込みは当学会まで.

(申込締切12 月 21 日)『・......................・・・・圃・_.........................................・・・・・・・ a・・・・・・・・・・・・・・・・・・・・圃・・・...............周・・・・.........闘"・・・・・・・・・・・・・・・・・・・・ 6

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

(47)557