部会報告(2000年度〜2004年度) – 日本OR学会待ち行列研究部会

第183回部会報告

日時:: 2月19日(土曜日)14:00〜16:30
出席:: 22名
場所:: 東京工業大学西8号館(W)809号室
テーマと講師:（＊は講演者）

2005年02月20日

第182回部会報告

日時:: 12月18日(土曜日) 14:00〜16:30
出席:: 23名
場所:: 東京工業大学西8号館(W)809号室
テーマと講師:（＊は講演者）

2005年01月11日

第181回部会報告

日時:: 11月20日(土曜日)14:00〜16:30
出席:: 21名
場所:: 東京工業大学西８号館(Ｗ)８０９号室
テーマと講師:(＊は講演者)

2004年11月20日

第180回部会報告

日時:

10月16日(土曜日) 14:00〜16:30

出席:

26名

場所:

東京工業大学西８号館(Ｗ)８０９号室

テーマと講師:（＊は講演者）

「スペクトル法による非割り込み優先BMAP/G/1待ち行列」
＊西村彰一（東京理科大学）

2クラスの客がBMAPに従ってサービス窓口に到着し，クラス1の客が非割り込みで優先的にサービスされる待ち行列モデルについて，平衡状態における各クラスの客の系内人数同時確率分布が，スペクトル法を用いて導かれた．このアルゴリズムで同時分布が効果的に計算でき，また現実のトラヒック解析へも応用可能であることが示された．3つ以上のクラスに拡張可能かどうかなど，活発な質疑が行われた．
「センサネットワークの性能評価尺度と稼働率評価法について」
＊土屋利明，斎藤洋，南裕也（NTT）

ユビキタスサービスを実現するための有力な技術であるセンサネットワークの概要が説明された．また，センサネットワークの稼働率について，直列型およびリング型のトポロジーを仮定した場合の解析結果が報告された．今後実際に導入が予想される様々なセンサ事例との整合性に関するコメントなど，多くの質疑がなされた．

2004年10月16日

第179回部会報告

日時:

7月17日(土曜日) 14:00〜16:30

出席:

20名

場所:

東京工業大学西8号館(W)809号室

テーマと講師:（＊は講演者）

「多重クラス待ち行列システムの実現可能性判定問題に対する高速解法」
＊井床利生（日本ＩＢＭ東京基礎研究所），岩田覚（東京大学）

多重クラスM/M/1待ち行列システムを例にとり，クラスごとの平均サービス要求時間をパフォーマンス変量としたときに，その領域が特殊な形の多面体で表わされることが示された．また，この分離問題をnの2乗オーダーで解けることが証明された．特に対象となった待ち行列モデルに対して，判定できる内容や実際のシステムとの関連などについて，活発な質問や議論が行われた．
「M/G/1変形モデルと再生サイクル法」
＊中塚利直（東京都立大学）

M/G/1変形モデルの新たな解析手法として，再生サイクル法が提案された．この手法で，簡単な再生サイクルを種々組み合わせて多くのモデルを表現し，その系内客数や待ち時間の分布を導出できることが示された．従来用いられてきた隠れマルコフ法や補助変数法などとの関連を中心に，質問やコメントが寄せられた．

2004年07月17日

第178回部会報告

日時:: 5月15日(土曜日) 14:00〜16:30
出席:: ２０名
場所:: 東京工業大学西8号館(W)809号室
テーマと講師:

2004年05月15日

第177回部会報告

日時:: 4月17日(土)14:00〜16:30
出席:: 21名
場所:: 東京工業大学西8号館(W)809号室
テーマと講師:

2004年04月18日

第176回部会報告

日時:

2月21日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

24名

テーマと講師（＊は講演者）:

「ネットワーク不正アクセスパケットの抽出とその統計的性質」
藤本衡（東京電機大学）

ネットワークを介した不正アクセスの種類とその対応策についての概要が紹介された。次にサーバのアクセスログから不正アクセスの情報を主観的に分類する手法が説明され、分散分析により提案手法の統計的有効性について報告がなされた。
「個人行動をベースにした歩行モデルと高密度シミュレーション」
岡田公孝, 高橋幸雄, 大野将春（東京工業大学）

歩行シミュレーションのための歩行モデルに関する過去の関連研究について、アニメーションによる紹介がなされた。次にモデルの改良方針としてアイコンタクトによる優先権、速度ベクトル認識補正、およびペア歩行者の挙動について説明がなされ、それらを考慮したシミュレーションモデルの有効性について、アニメーションと歩行流の特性量に基づく評価より議論が行われた。

2004年02月21日

第175回部会報告

日時:

12月20日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

25名

テーマと講師（＊は講演者）:

「待ち行列の最適制御について　−いつ並ぶべきか−」
小柳淳二（鳥取大）

待ち行列システムにおける最適制御問題について、過去に取り扱われてきた問題の紹介およびマルコフ決定過程による最適政策の分析法について説明がなされた。次に待ち行列に並ぶタイミングを取り扱った代表的な問題が紹介され、ある期限内に作業を終了させる確率を最大化する問題についてはスイッチカーブ政策が最適となること、およびその解析方法を応用することで期限遅れを最小化する問題も解析できることが示された。
「PH distributions with non-distinct eigenvalues」
岸康人，＊紀一誠（神奈川大学）

PH 分布の subgenerator Q の固有値に重複がある場合、中でも唯一の実数固有値がある場合および実固有値１つと一組の共役複素数固有値を持つ場合について、Jordan標準形によるQの表現からPH分布の密度関数の具体的な形が導出されることが示された。また導出結果よりPH分布の性質を規定する本質的なパラメータはQのサイズではなく、Qの最小多項式の次数であることが報告された。

2003年12月20日

第174回部会報告

日時:

11月15日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

24名

テーマと講師（＊は講演者）:

「PONシステムの概要とメディアアクセス制御のモデル化について」
横谷哲也（三菱電機）

光アクセス技術の一つである Passive Optical Network (PON) 技術の概要が紹介され、低コスト性や標準化動向について説明がなされた。次にメディアアクセス制御技術に用いられているインターリーブポーリング方式が紹介され、一定周期内に送信許可時間と送信不許可時間が出現する待ち行列モデルの提案および数値例によるモデルの検証について報告がなされた。
「自動搬送システムにおけるAGVの割り当てとその性能評価」
山下英明（東京都立大）

ODペア（始点と終点の組）ごとの搬送要求の発生確率が既知である自動搬送システムにおいて、搬送要求の待ち時間が最小になるようにAGVをODペアに割り当てる問題について説明がなされた。次に搬送要求が幾何分布に従って到着し、先着順に搬送要求が処理される場合には、マルコフ解析によって待ち時間の分布が導出できることが示された。また他の割り当て政策におけるマルコフ解析の可能性、およびこの解法の適用例としてAGVの割り当てを伴う確率的な職場配置問題について報告がなされた。

2003年11月15日

第173回部会報告

日時:

10月18日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

24名

テーマと講師（＊は講演者）:

「確率モデルによるコンピュータウィルスの特徴分析」
岡村寛之 (広島大学)

現在のインターネット社会において脅威となっているコンピュータウィルスの拡散過程について、ウィルス警告の Kill Signal 配信を考慮したマルコフ連鎖モデルが提案された。次にウィルス拡散の定量評価のための評価尺度およびその計算方法が紹介され、数値例を基に評価尺度に対するウィルスの感染率、除去率、および Kill Signal の影響について説明が行われた。
「Modified Service Modelsについて」
高橋敬隆 (早稲田大学)

全稼働期間を開始する客のサービス時間が、同じ全稼働期間内に到着する他の客のサービス時間と異なる変形サービスモデルについて紹介がなされた。次に GI/GI/1 で変形サービスモデルを定式化した場合の拡散近似による解析法が説明され、導出された平均待ち時間の近似式が過去に導出された結果と一致していることが示された。

2003年10月18日

第172回部会報告

日時:

7月19日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

21名

テーマと講師（＊は講演者）:

「Markov processes conditioned to never exit a sub-state space」
Tomasz Rolski (Wroclaw University, Poland)

マルコフ過程がある状態部分集合に永久に留まるという条件の下で定義される Never Exiting (NE) マルコフ過程について紹介がなされた。NE マルコフ連鎖の定常測度と準定常分布との関係を明らかにし、応用例として、M/G/1待ち行列の系内仕事量過程において、仕事量が正であるという状態部分集合に対して定義される NE マルコフ過程と準定常分布に対する結果が与えられた。
「Markov Chains of GI/G/1 Type」
Yiqiang Q. Zhao (Carleton University, Canada)

GI/G/1型マルコフ連鎖のブロック型遷移確率行列において、行列因数分解のための2種類の基本行列が紹介され、マルコフ連鎖の定常状態確率ベクトル、過程の分類と安定条件、補分布の漸近特性が基本行列を用いて特徴付けられることが示された。次にα-positivityとその不変ベクトルについて説明がなされ、マルコフ連鎖のブロック行列にα-positivityの性質があるとき、そのマルコフ連鎖は幾何的な補分布を持つことが示された。

2003年07月19日

第171回部会報告

日時:

5月17日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

30名

テーマと講師（＊は講演者）:

「可変伝送レートを提供するシステムの待ち行列モデルについて –次世代移動体通信システムを例として–」
河西憲一（群馬大学）

W-CDMA方式における直交可変拡散率(OVSF: Orthogonal Variable Spreading Factor)符号について紹介がなされ，OVSF符合の効率的な配分問題について説明が行われた．次にリソース配分問題定式化のための待ち行列モデルについて現在までの研究状況および今後の研究課題について報告がなされた．
「スペクトル法によるMAPの解析とそのトラフィック・データへの応用」
西村彰一（東京理科大学）

マルコフ到着過程（MAP）を入力とする単一サーバ待ち行列のスペクトル解析法およびEMアルゴリズムによるMAP行列の推定法が説明された．次に数値例として，ツリー構造を持つMAPに実トラヒックデータを適用した例が報告され，系内客数分布について軽負荷では良好な結果が得られる一方で，高負荷時では特性量の予測が困難であることなどが示された．

2003年05月17日

第170回部会報告

日時:

4月19日(土)

場所:

東京工業大学西8号館(Ｗ)809号室

出席:

28名

テーマと講師（＊は講演者）:

「生産システムにおける待ち行列・確率モデル」
中出康一（名古屋工業大学）

生産システムにおけるJust in Time (JIT), Supply Chain Management (SCM), Theory of Constraints (TOC) の概念について説明がなされ，次に有限バッファを有する直列型生産ラインの生産指示方策について解説が行われた．また多能工とU次ラインからなる生産システムの解析モデルについての紹介がなされ，今後の方向性として多品種・多段階スケジューリングや物流・物品納入を含めたモデルの構築とその最適化が挙げられた．
「集団流体入出力のあるマルコフ変調流体待ち行列」
高田寛之（山口東京理科大学）

同時処理型の２つの並列流体待ち行列を持つネットワークモデルとして，ある量の流体の瞬時入出力を持つマルコフ変調流体待ち行列が取り上げられ，バッファ容量の標本路がSkipFreeとならないことに起因する解析の困難さについて解説がなされた．次に集団入力と集団出力を指数分布と仮定することで，対象とするマルコフ変調流体待ち行列のバッファ容量の定常分布を導出できることが示され，導出された分布が指数行列形式で表現されることに対する説明がなされた．

2003年04月19日

第169回部会報告

日時:

2月15日（土）14:00〜17:00

場所:

東京工業大学西8号館(W) 809号室

出席:

27名

テーマと講師（＊は講演者）:

「定時割り込みのある時間離散型待ち行列と時間連続型への架け橋」
町原文明（東京電機大学）

優先権を持つ客が一定間隔で到着する定時割り込み型待ち行列モデルについて，サーバのアイドル状態時に到着する客のサービスが時間スロット毎に開始される離散時間モデルと，到着と同時にサービスが開始される連続時間モデルを考え，離散時間モデルの解析結果を用いて連続時間モデルの定常状態仮待ち時間分布を導出する手法について報告がなされた．
「サーバ状態を組み込んだマルコフ型待ち行列モデルについて」
小沢利久（駒澤大学）

MAPと同様の構造を持つサービス過程でかつ vacation, setup, exceptional service time などをサーバの状態として表現できる Markovian service process (MSP) について紹介がなされた．次にMAP/MSP/1モデルの公比行列の構造について解説がなされ，stochastic decomposition などの性質がいくつかのMSP で得られることが報告された．
「Regenerative queueing networks: stability analysis and simulation」
Evsey Morozov (会津大客員教授)

弱更新点を持つ更新過程の概要について説明がなされ，次にそれを用いた再生入力を持つ待ち行列網の安定解析，およびシミュレーションにおける信頼区間推定について報告がなされた．

2003年02月15日

第168回部会報告

日時:

12月21日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

23名

テーマと講師（＊は講演者）:

「ピアツーピア(P2P)ネットワークの動向」
川島幸之助（東京農工大学）

従来のサーバ・クライアント通信の概念と異なるピアツーピア通信の概要が紹介され，ピアツーピア通信の測定に基づく統計解析研究，ネットワーク構成の研究，および最近のアプリケーション関連研究について報告がなされた．
「マルコフ的ネットワークにおけるノード到着過程のLaplace-Stieltjes変換の導出とその特性」
加藤憲一（山形大学）

GI/G/1待ち行列の減衰率を導出する解析法を用いて，待ち行列網の一つのノードを取り出して減衰率を解析する取り出し解析法の提案がなされた．次に客が循環しないネットワークには取り出し解析法が適用できることが紹介され，客が循環するネットワークへの適用における問題点について報告がなされた．

2002年12月21日

第167回部会報告

日時:

11月16日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

24名

テーマと講師（＊は講演者）:

「M/D/1待ち行列の定常確率の級数展開について」
中川健治（長岡技術科学大学）

M/D/1待ち行列長の定常確率について，その確率母関数の極と留数を用いた定常確率の級数展開が紹介された．またその結果に基づく定常確率の上界と下界が示され，数値例を基に精度の有効性について議論が行われた．
「Passive 測定／Active 測定を組み合わせた測度変換型品質測定技術 CoMPACT Monitor について」
三好直人（東京工業大学）

インターネット上のトラヒック品質測定手法として，Active測定と Passive 測定を測度変換の概念を用いて組み合わせた品質測定技術について，紹介がなされた．この手法の特徴として，ネットワークに挿入する試験トラヒックの負荷を極力抑えることができること，複数のユーザやアプリケーションのトラヒック品質を同時にかつ個別に測定することができることが示された．また遅延についてのシミュレーション結果が示され，提案手法の有効性について議論が行われた．

2002年11月16日

第166回部会報告

日時:

10月19日（土）14:00〜17:00

場所:

東京工業大学西8号館(W) 809号室

出席:

36名

テーマと講師（＊は講演者）:

「Web C/Sシステムの容量設計のアプローチについて」
＊坂田洋幸（（株）NTTデータ），牧本直樹（筑波大学）

メインフレームや汎用機等の既存資産と連携するWeb Client/Server型システムについて、システムの容量設計問題の観点から紹介がなされた。次に対象システムに対する定量的な評価のためのシミュレーションモデルと実機実験との比較検証について報告がなされ、モデルの妥当性に関する議論が行われた。
「分散システムやネットワークにおける、分散型最適化による逆説的性能劣化のWorst Case」
亀田壽夫 (筑波大学)

分散システムやネットワークの管理者が、自己の管理するジョブのコストを個別に最適化しようとする非協力ゲームのNash均衡問題において、通信容量を増強すると、逆に全ての使用者・管理者のコストが劣化する Braess パラドックス（Nash均衡のPareto inefficiency）について説明がなされた。次に独立な管理者が無数にあり、資源数が有限の場合、かなり一般的なネットワークにおいて、コストの劣化は有界であること、また管理者の数が有限の場合、劣化の程度が限りなく大きい場合があること、さらに、検討した全ての場合において、各管理者やシステムが対称な場合が最悪のケースとなることが紹介された。
「On the Convexity of Loss Probabilities」
Ronald W. Wolff (University of California at Berkeley)

M/G/c 呼損系におけるアーラン損失確率がサーバ数に関して凸である性質について、証明の歴史的な経緯が紹介された。次にその結果が再生到着と指数サービスを持つ場合について拡張できること、また到着過程が更新過程に従う場合にも拡張できること、さらには独立同一なサービス分布を持つ任意の到着過程に対しても、損失確率がサーバ数に関して凸性を持つことが示された。

2002年10月19日

第165回部会報告

日時:

7月27日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

24名

テーマと講師（＊は講演者）:

「Semi-Poisson 過程とその拡張」
岸康人，＊紀一誠 (神奈川大学)

到着時間間隔列は指数分布に従う一方で、これらの確率変数列が独立ではないSemi-Poisson過程についてその構成法が紹介された。次に相型分布を使って到着時間間隔列を任意の分布に拡張した到着過程の構成法について報告が行われ、提案された到着過程の指数分布族の重み付き和としての表現法とその解釈に関する議論が行われた。
「系内仕事量に上限のある単一サーバ待ち行列システムの確率比較概念（ directionally convex ordering）による評価」
塩田茂雄 (千葉大学)

到着したジョブの部分損失を許す有限バッファを持つ単一サーバ待ち行列システムに対し、directionally convex orderingを用いた損失仕事量の上限値解析について報告がなされた。ジョブの到着時間間隔およびジョブの大きさに相関が大きいほど損失仕事量は増大することが証明で与えられ、数値例でも強相関のときにタイトな上限値を与えることが示された。

2002年07月27日

第4回Q/INIジョイントワークショップ報告

日時:: 6月20日（木）13:00〜18:00, 6月21日（金）9:45〜16:05
場所:: 京大会館
出席:: 54名
テーマと講師（＊は講演者）:: 「新しいトラヒックモデルと性能評価」
共催：電子情報通信学会情報ネットワーク (IN) 研究会

平成11年度より始まった電子情報通信学会情報ネットワーク研究会とのジョイントワークショップは今年で4回目を向かえた。進展著しいインターネット技術に対する待ち行列理論の応用を目標にテーマを設定して発表を募ったところ、一般発表18件、招待講演3件の、計21件の発表よりプログラムを構成することができた。一般発表では待ち行列理論による情報通信システムの性能評価の報告が多くなされたが、それ以外にも確定モデルを用いた待ち行列システムの評価法や測定データに基づく評価量の統計的推測法など、情報通信システムの評価に関連する待ち行列以外の手法についても発表が行われた。招待講演では情報ネットワーク研究会からはインターネット技術について、待ち行列部会側からはシミュレーション手法について、それぞれチュートリアル的な講演が行われた。また3件目の招待講演ではデータマイニングによるネットワークの不正アクセス検出法が紹介され、実ネットワークにおける統計的推定法の有用性が報告された。2日間で計54 人の参加者があり、研究発表および懇親会にて両研究会の交流が活発に行われ、大盛況のうちにワークショップを終えることができた。

2002年06月20日

第164回部会報告

日時:

5月18日（土）14:00〜17:30

場所:

東京工業大学西8号館(W) 809号室

出席:

29名

テーマと講師（＊は講演者）:

「ブロック生産システムのモデル化と解析」
山下英明 (東京都立大学)

ブロック生産システムにおいて、スループットおよび平均仕掛品在庫数を最適にするシステム構成要素の決定問題に対し、サンプルパス最適化を用いた解析法について報告がなされた。また平均仕掛品在庫とスループットのパレート解についても数値例が示され、サンプルパス最適化の有効性について議論が行われた。
「TCPへのペイロード廃棄型シグナリング方式の実装実験とモデル化による評価」
高野正次 (NTT)

インターネットのTCPプロトコルにおいて、パケットの損失を明示的に受信端末に伝えるペイロード廃棄型シグナリング方式について説明がなされた。また実装実験および数学モデルによる評価についても報告がなされ、提案方式の有効性について議論が行われた。

2002年05月18日

第163回部会報告

日時:

4月20日（土）14:00〜17:00

場所:

東京工業大学西8号館(W) 809号室

出席:

30名

テーマと講師（＊は講演者）:

「Exact buffer overflow probabilities for queues via martingales」
Soren Asmussen (Lund University, Sweden)

ある時刻からバッファオーバーフローが発生するまでの時間について、optional stopping martingale を用いた解析法が紹介された。また複数サーバ待ち行列やマルコフ到着過程を持つ待ち行列に対し、バッファオーバーフロー到達時間のモーメント公式やラプラス変換形が導出され、数値計算によりその有効性が示された。
「The hitting probabilities in a Markov additive process with linear and upward jump components」
宮沢政清 (東京理科大学)

線形的な増減と上方ジャンプをもつマルコフ加法過程において、稀少事象に到達する確率の decay rate に対し、マルコフ再生定理を用いたアプローチが紹介された。また一般的な状態空間に対するマルコフ再生定理の拡張の可能性や提案手法の待ち行列網への応用についても述べられた。

2002年04月20日

第162回部会報告

日時:

2月16日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

28名

テーマと講師（＊は講演者）:

「待ち行列公式 `W=ZL’ とその周辺について」
松井正之 (電気通信大学)

待ち行列における代表的な公式であるリトルの公式について,生産マネジメントの観点から, いくつかの解釈が考察された.
「M/G/1型マルコフ連鎖の定常分布およびその裾の指数的減少について」
中川健治 (長岡技術科学大学)

M/G/1型マルコフ連鎖の定常分布自身の指数的減少, およびその裾の指数的減少を保証する十分条件について, 定常分布の確率母関数に対する複素関数としての解析的な性質に着目して議論がなされた.

2002年02月16日

第161回部会報告

日時:

12月15日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

26名

テーマと講師（＊は講演者）:

「An alternative formula for the steady-state solution of Markov chains of M/G/1 type and its geometric and subexponential asymptotics」
滝根哲哉 (京都大学)

M/G/1 型マルコフ連鎖の定常状態確率分布について考察された.最初に, ある行列関数の畳み込みの無限和を用いて表現される定常状態確率の新しい表現式が与えられ, この結果に基づいて,定常状態確率分布の裾野が幾何的な漸近分布を持つための十分条件, ならびに劣指数的な漸近分布を持つための十分条件が与えられた．
「Light traffic approach to a cellular system with mobile subscribers」
山崎源治 (東京都立科学技術大学)

移動体通信サービスを行うセルラーシステムについて, 着目するセルにおける定常状態分布に対する軽負荷近似によるアプローチが提案された. さらに, システムに優先権を持つ加入者が存在する場合などに対する軽負荷近似アプローチの適用についても話があった.

2001年12月15日

第160回部会報告

日時:

11月17日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

27名

テーマと講師（＊は講演者）:

「Multiscale variance fitting for self-similar process with Markov-modulated Poisson process」
笠原正治 (奈良先端科学技術大学院大学)

近年の通信トラッヒックの性質として, 長期依存性・自己相似性といった強い相関構造が観察されている. 講演では, 対象とする自己相似過程に有限時間スケールで分散が一致するようなマルコフ変調ポアソン過程を生成する方法について発表があった. また, 得られたマルコフ変調ポアソン過程を到着過程とする待ち行列モデルを解析することにより, 提案手法の有効性について示された.
「Matrix analytic approach to fluid queues」
Guy Latouche (Universit Libre de Bruxelles, 東京工業大学客員)

マルコフ変調型流体待ち行列のシステム内仕事量の定常分布に対して, 数値的に安定で効率の良い計算方法について発表があった.

2001年11月17日

第159回部会報告

日時:

10月20日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

26名

テーマと講師（＊は講演者）:

「通信制御とプロセッサシェアリング待ち行列について」
小沢利久 (駒澤大学)

通信システムにおけるTCPフロー制御を, ネットワーク資源をユーザへ配分する仕組みと捉えると, 均等な資源割当を目標とする場合, プロセッサシェアリング (PS) 待ち行列が理想的な状況を表すモデルとして考えられる. 講演では, データ通信を意識したPS待ち行列モデルに対して, データ転送時間分布の解析法について発表があった.
「A study on multi-server queueing system with Markovian service process」
河西憲一 (群馬大学)

複数サーバを持つ待ち行列系において, サーバが一つの呼のサービスを終えても, しばらくの間 (ラップアップ・タイムと呼ばれる) は次のサービスを開始できないような状況が考えられた.ラップアップ・タイム中のサーバの数を状態とするマルコフ型サービス過程を持つモデルを考えることによって, 呼の待ち時間の解析法が示された.

2001年10月20日

第158回部会報告

日時:

7月14日（土）14:00〜17:30

場所:

東京工業大学西8号館(W) 809号室

出席:

29名

テーマと講師（＊は講演者）:

「The Semi-Regenerative Method of Simulation Output Analysis」
Marvin K. Nakayama (New Jersey Institute of Technology)

確率モデルのシミュレーションにおいて, 対象となる確率過程が複数の再生点列を持っている場合に, それを利用して効果的に推定量を得る手法の一つである準再生法について説明があった. また, この方法によって得られる推定量に対応した中心極限定理が導かれた.
「Effective Local Buffer Sizes in a Flexible Manufacturing System」
山崎源治 (東京都立科学技術大学)

複数の機械と複数のAGV, そして一つの自動倉庫からなるフレキシブル生産システムの設計問題として, 機械とAGVの台数が固定されているときに, 各機械が持つバッファの容量を決定する問題について報告があった. はじめに確定的なモデルに対してバッファ容量の決定規則が導かれ, さらに, その決定規則がある種の確率モデルに対しても有効であることが示された. 結論としては, バッファの容量はとても小さくて良く, 容量１で十分とのことであった.
「揺らぎ発生のメカニズム」
町原文明 (東京電機大学)

パケット通信ネットワークでは, ユーザ端末から発生されるパケットの間隔は揺らぎが十分小さく, 左右対称な密度関数を持つ分布に従っていても, ネットワーク内のノードを通過するたびに揺らぎが増加し, 分散の大きな分布に従うことになる.その際, 密度関数の対称性が崩れ, その峰は徐々に平均より左に移り, 最終的には指数分布のような完全単調な密度関数となる. この完全単調族の中で, 揺らぎの増加により, 到着過程がポアソン過程から断続ポアソン過程, そしてフラクタルポアソン過程へ変貌するメカニズムが考察された.

2001年07月14日

第157回部会報告

日時:

5月19日（土）14:00〜17:00

場所:

東京工業大学西8号館(W) 809号室

出席:

32名

テーマと講師（＊は講演者）:

「バッファ管理の待ち行列モデル」
住田修一 (NTT)

パケット型通信に必須のバッファ管理について, 特に1980年代末から1990年代中頃まで活発に解析された Space priority についての概観があった. さらに, Space priority と Timepriority を mixing したスケジューリングの結果について述べられた.
「待ち行列に期待するもの」
佐藤昭 (富士通)

1970年代〜2000年までのコンピュータシステム性能評価の歴史を振り返り, 待ち行列の成果を応用した手法・実施例などが紹介された. さらに, 未解決な問題・理論上興味のある事例などが述べられた. また, 性能評価担当者の関心の対象が, 待ち行列から他分野へ移りつつある現状も紹介された.

2001年05月19日

第156回部会報告

日時:

3月17日（土）14:00〜17:30

場所:

東京工業大学西8号館(W) 809号室

出席:

25名

テーマと講師（＊は講演者）:

「Mean and variance of the waiting time and its optimization for the alternating traffic systems」
山下英明 (東北大学)

狭い橋や道路工事などのために2車線の道路が部分的に1車線になり, その部分を両方向の交通流が交互に利用するモデルが解析された. 利用している側の交通流が途切れても, 新たにやって来る車のためにしばらくの間 (保留時間) は対向する交通流に通行する権利を与えないような信号機の制御を考え, 車が通行できるまでの待ち時間の平均と標準偏差を最小にする保留時間のパレート最適解が数値的に与えられた．
「CSPS Model: A Look-Ahead Control and Physical Theory とその周辺」
松井正之 (電気通信大学)

約40年にわたって講師自らが行ってきたコンベヤ生産ステーション (CSPS) に関する研究の総まとめが与えられた. 動力コンベヤと連結したステーションが先見型待ち行列モデルとして特徴づけられ, RdSRP と呼ばれる方策が遅れを最小にする最適方策であることが示された. さらに, 遅れと溢れの線形関係を示すことにより, 種々の平均値間の公式系が見出された.
「A Fast Algorithm for Finding the Optimal Change of Measure for Overflow Probabilities in Queueing Networks」
Reuven Y. Rubinstein (Technion, Israel)

待ち行列ネットワークにおけるオーバーフロー等の稀少事象の生起確率をシミュレーションにより推定する手法として, 測度変換によるインポータンスサンプリング(IS) 法が良く知られている. 講演では, まずクロスエントロピー (CE) と呼ばれるアルゴリズムを用いて最適な測度変換をシミュレーションによって推定し, 次に得られた測度変換を用いた IS 法によって稀少事象の生起確率を推定するという 2段階の方法が紹介された.

2001年03月17日

第155回部会報告

日時:

2月17日（土）14:00〜17:00

場所:

東京工業大学西8号館(W) 809号室

出席:

24名

テーマと講師（＊は講演者）:

「待ち行列ネットワークにおける定常分布の裾の減少率: 既存の結果と予想」
宮沢政清 (東京理科大学)

積形式解を持たない待ち行列ネットワークの定常状態における待ち人数の結合分布の裾の減少率について報告された. 最初に多次元分布の裾の減少率の定義が与えられ, その後, 一般化ジャクソンネットワークにおける待ち人数の結合分布についての減少率に関する予想が述べられた. また, この予想によって既知の結果が説明できることが示された.
「決定論的インターネットトラヒック評価」
豊泉洋 (会津大学)

トラヒック理論や待ち行列理論では, ユーザーの振る舞いや入力トラヒックを確率過程としてモデル化することによって, さまざまな通信システムのモデル化を行い, 成功を収めてきた. 講演では, こうした方法論とは異なり, インターネットでの遅延上限値算出法として発達してきた決定論的な性能評価手法が紹介された. また, Block renewal process と組み合わせることによって, 確率的な枠組みとも整合できることが示された.

2001年02月17日

第154回部会報告

日時:

12月16日（土）14:00〜17:30

場所:

東京工業大学西8号館(W) 809号室

出席:

23名

テーマと講師（＊は講演者）:

「Subexponential asymptotics of the waiting time distribution in a single-server queue with multiple Markovian arrival streams」
滝根哲哉 (京都大学)

複数のマルコフ型到着流をもつ定常なFIFO単一サーバ待ち行列において, サービス時間の平衡分布が劣指数的であるとき, 仮待ち時間, 実待ち時間ならびに滞在時間分布が劣指数的であり,サービス時間の平衡分布と漸近的に等価であることが示された.
「待ち行列における分布の線形表現とその応用」
中塚利直 (東京都立大学)

１サーバ待ち行列モデルでも, サーバの休み時間や閉鎖予告時間を加えたり, 客を複数のクラスに分けたりすることによって,従来の方法では解析が面倒であったり, そもそも解けなかったりするような複雑なモデルを考えることができる. 講演では,対象としているモデルの状態確率が, 既によく調べられた基本モデルの状態確率の線形結合で表わせることが示され, この性質を用いることにより, 特にM/G/１系の多くのモデルにおいて,系内客数や仮の待ち時間等の分布が求まることが示された.

2000年12月16日

第153回部会報告

日時:

11月18日（土）14:00〜17:00

場所:

東京工業大学西8号館(W) 809号室

出席:

24名

テーマと講師（＊は講演者）:

「ネットワークの遅延・輻輳が多重化IPトラヒックの自己相似性に与える影響」
古屋裕規 (KDD研究所)

近年, データネットワーク上の多重化IPトラヒックが長期依存性・自己相似性といった, 従来の電話呼トラヒックとは異なる特性を持つことが報告されている. また, 最近の研究によって,比較的短い時間スケールにおいては単純な自己相似と異なった複雑な特性を呈することも報告されている. 今後益々進展するマルチメディアトラヒック網の効率的な計画・運用・管理手法を確立するにあたっては, こうしたデータトラヒック特有の性質を的確に把握し, 活用することが肝要である. 講演では, 計90台の実機で構成されたテストベッド上でネットワークの遅延および輻輳状態を変化させながら実測したトラヒックデータを解析することにより, ネットワークの挙動 (TCP/IPの制御機構)が多重化IPトラヒックの自己相似的な特性に与える影響について考察された.
「分散システムにおける性能劣化パラドックスの解と発生条件」
亀田壽夫 (筑波大学)

複数の処理装置 (server) からなる分散システムがあり, 各処理装置を管理する管理主体が, 自分のところに到着する負荷の一部を転送手段を用いて他の処理装置へ転送し処理委託することができるとする. 各管理主体が自分のところに到着する負荷に対するコスト (平均応答時間) のみを最適化しようとする分散最適化 (Nash均衡に相当) を考えると, 各処理装置の能力も到着負荷も全く同一の完全対称システムの場合でも, 互いに処理委託しあった結果, 全ての主体に対する性能が転送手段がない場合よりかえって悪化するという, 逆説的な現象が起こることがある. 講演では, そのような逆説的な現象が発生するための必要十分条件が示された. さらに, 逆説的な現象が起こる場合, 性能劣化の程度が限りなく大きくなり得ることも示された.

2000年11月18日

第152回部会報告

日時:

10月21日（土）14:00〜17:30

場所:

東京工業大学西8号館(W) 809号室

出席:

27名

テーマと講師（＊は講演者）:

「Proportional relation in discrete-time single-server queues: Review of existing results」
石崎文雄 (南山大学数理情報学部)

ある種の待ち行列システムにおいては, バッファ容量の異なる複数のシステムの定常待ち行列長分布の間に “proportional relation” と呼ばれる簡単な関係式が成立することがよく知られている. この proportional relation は, どのようなクラスのシステム間に成立するかという理論的な興味だけではなく, 効率の良い数値計算アルゴリズムの開発やオンライン並列性能推定といった豊富な応用も有している. 講演では, 離散時間待ち行列システムにおける proportional relation に関して, 現在までに得られている結果がまとめられた.
「インターネットアクセスパターンのモデル化に関する検討」
＊会田雅樹 (NTT-AT), 安部哲哉 (NTT EAST)

インターネットのアクセス宛先 (IPアドレス, URL) の生起が, 一種の定常な確率過程で表されると仮定したとき, 宛先の生起パターンはどのようなモデルになるべきかについて検討され, 擬似的に宛先の生起パターンを再現するアルゴリズムが紹介された. また, 実際のインターネットアクセスパターンの分析で頻出するジップ型分布の再現と定常性を両立させるように, アルゴリズムを拡張した結果が報告された.

2000年10月21日

第151回部会報告

日時:

7月15日（土）14:00〜16:30

場所:

東京工業大学西8号館(W) 809号室

出席:

24名

テーマと講師（＊は講演者）:

「巾級数における係数の漸近的ふるまいについて」
中川健治 (長岡技術科学大学電気系)

すべての係数が非負の巾級数において, その収束半径が１より大きく, かつ巾級数によって定義される複素関数が高々有限個の極を除いて収束円周上で正則であるという条件のもとで, 係数ベクトルの裾が指数的に減少することが示された. また, 収束半径が１より大きいという条件だけでは裾が指数的に減少しない例が挙げられた. こうした結果の待ち行列への応用についても述べられた.
「インターネット電話の品質評価について」
高野正次 (NTT研究所)

インターネットやLANなどのデータ系のネットワーク上で電話などの音声アプリケーションを用いることが広まっているが, この理由は技術的な成熟と経済性にある. 音声通信の品質として, 人間が実際に耳で違和感を覚えないように音声フレームを適切に転送できる必要がある. この目的のために端末間での遅延や揺らぎをトラヒックモデルによって評価し, ネットワーク設計を行った事例について報告された.

2000年07月15日

第150回部会報告

日時:

5月20日（土）14:00〜17:00

場所:

東京工業大学西8W号館809号室

出席:

29名

テーマと講師（＊は講演者）:

「Some comparison results for the decay rates of queues」
牧本直樹 (筑波大学経営システム科学)

待ち行列の減衰率は, 定常分布の裾が幾何的／指数的に減少するときの速さを表す指標である. 講演では, 到着過程がポワソンの場合と MPP (Modulated Poisson Process) の場合について減衰率の比較を行うことにより, 到着過程のバースト性が減衰率に与える影響が示された. また, 直列型や２ノードマルコフ型のネットワークモデルの場合についても検討された.
「定常解析: その可能性と限界」
宮沢政清 (東京理科大学理工学部)
待ち行列システムの性能評価では, モデルを作りその定常分布を求めること (定常解析) が広く行われている. しかし, 理論による定常解析が可能なモデルの範囲は, 数値解析を含めても限られている上, 理論的に興味あるモデルが応用に必要なモデルとずれてしまうことも多い. そこで, 応用に役立ちそうなモデルとして, (1) 行き先のノードの混雑状況により経路を変えるネットワークモデルと (2) 集団サービスで集団が大きくなるとより効率的にサービスできる (１人当たりのサービス時間が短くなる) モデルをあげ,
- 理論的な成果を生かす可能性はあるのか？
- 計算機のパワーをどのように使えばよいか？
の２つの観点から検討がなされた. (1)については近似解の生成アルゴリズムとその誤差評価について, (2)については安定性について述べられた. 最後に, 待ち行列研究の将来について参加者全員でディスカッションを行った.

2000年05月20日

第149回部会報告

日時:

4月15日（土）14:00〜16:30

場所:

東京工業大学本館1-94号室

出席:

26名

テーマと講師（＊は講演者）:

「確率過程を用いたエレベータ稼働指標のモデル化について」
島川陽一 (中央大学)

本研究ではフロア間の平均移動人数をもとにエレベータの稼働指標を算出するモデルを構築した. 稼働指標にはエレベータの稼働率, 基準階で待機中のエレベータがサービスを開始し, 要求されたすべてのサービスを完了して再び基準階で待機状態になるまでに含まれるサービス回数の分布, フロアに現れた客がエレベータに搭乗するまでの待ち時間分布などがある. エレベータのサービス基準にFIFOを仮定した場合,エレベータ搭乗待ち時間分布は稼働率が高くなると実際の数値とモデルから得られる数値とが乖離してくる. これは, エレベータに収容された客はコールの順に処理されるのではなく, エレベータが通過する階の順番に客を処理するからである. したがって, 搭乗待ち時間については処理の順番を考慮することはモデル化に際して本質的な問題である. 発表ではこれらの稼働指標についてコンピュータシュミレーションから得られた結果とモデルから予想される数値を比較し, モデルの妥当性を検証した.
「２層型待ち行列網モデルとその近似解析手法」
蔵杉俊康 (NEC), 紀一誠 (神奈川大学)

２層型待ち行列網モデルは, 資源競合が階層的に生じるシステムを表現するためのモデルである. クリティカル・セクションを持つシステムなどは, 資源競合が階層的に生じるシステムの典型的な例である. システムを２層型待ち行列網モデルとしてモデル化し, 解析することで, このようなシステムの性能を予測することが可能となる. しかし, ２層型待ち行列網モデルの厳密な理論解析では, 一般には状態数の大きなマルコフ連鎖を解く必要が生じるため, 実行が困難となるケースが多い. そこで, 厳密な理論解析にかわり, 近似計算法を用いてモデルを解析する手法を開発した. 本手法を用いることで, 実用的なコストと精度でシステム性能の予測が可能となる. 本報告では,この近似計算法を紹介した.

2000年04月15日