「《待ち行列のバケーションサーバモデル》」の版間の差分
ナビゲーションに移動
検索に移動
Sakasegawa (トーク | 投稿記録) |
|||
| (4人の利用者による、間の4版が非表示) | |||
| 1行目: | 1行目: | ||
'''【まちぎょうれつのばけーしょんさーばもでる (queueing model with a vacationing server) 】''' | '''【まちぎょうれつのばけーしょんさーばもでる (queueing model with a vacationing server) 】''' | ||
| − | 基本的な待ち行列の数多くの変形モデルのうちの1つとして, 客がいるといないとに拘らず, サービスが行なわれない期間 (これをサーバの[[バケーション]] (vacation) という) のあるモデルがある. サーバのバケーションがあるモデルは, 伝統的 (1960年代) には, サーバの始動毎に発生する費用と客の待ち時間に対する費用の釣合いを取る最適制御問題として研究された. | + | こちらを参照してください： |
| + | [[待ち行列のバケーションサーバモデル|サーバのバケーションがある待ち行列]] | ||
| + | |||
| + | <!-- 基本的な待ち行列の数多くの変形モデルのうちの1つとして, 客がいるといないとに拘らず, サービスが行なわれない期間 (これをサーバの[[バケーション]] (vacation) という) のあるモデルがある. サーバのバケーションがあるモデルは, 伝統的 (1960年代) には, サーバの始動毎に発生する費用と客の待ち時間に対する費用の釣合いを取る最適制御問題として研究された. 1980年以降は, 確率分解定理と呼ばれる興味深い理論的性質と, 通信や生産システムの性能評価のための基礎的理論モデルとしての応用性が注目された. 特に, M/G/1待ち行列のバケーションモデルと, 複数のM/G/ <math>\cdot\, </math> 待ち行列を1つのサーバが巡回的にサービスするポーリングモデルが活発に研究された [1]. 近年は, 波長分割多元接続光通信方式のモデルに触発されて, サーバがバケーション中にも (稼動期間中とは異なる速さで) サービスを行うというワーキングバケーションモデルが解析されている [2]. | ||
| 17行目: | 20行目: | ||
'''確率的分解定理''' [[待ち行列モデル M/G/1|M/G/1待ち行列]] のバケーションモデルにおける興味深い理論的性質として, [[確率的分解定理]] (stochastic decomposition theorem)について述べる. これは, 適当な条件の下で, バケーションモデルの[[平衡状態]] (equilibrium state)における客数 <math>N\, </math> の確率分布が, 対応するバケーションのないモデルの平衡状態における客数 <math>N _0\, </math> の確率分布と, バケーション期間のみに依存する客数<math> N _1\, </math> の確率分布の畳み込みに分割できるという定理である. 例えば, 多重バケーションモデルの平衡状態における任意時刻の客数について, 分解定理が成り立ち, このとき <math>N _1\, </math> はバケーション開始時の客数とバケーション中の任意時刻までに到着する客数の和である. ある場合においては, G/G/1待ち行列のバケーションモデルにおいても分解定理が成り立つ. | '''確率的分解定理''' [[待ち行列モデル M/G/1|M/G/1待ち行列]] のバケーションモデルにおける興味深い理論的性質として, [[確率的分解定理]] (stochastic decomposition theorem)について述べる. これは, 適当な条件の下で, バケーションモデルの[[平衡状態]] (equilibrium state)における客数 <math>N\, </math> の確率分布が, 対応するバケーションのないモデルの平衡状態における客数 <math>N _0\, </math> の確率分布と, バケーション期間のみに依存する客数<math> N _1\, </math> の確率分布の畳み込みに分割できるという定理である. 例えば, 多重バケーションモデルの平衡状態における任意時刻の客数について, 分解定理が成り立ち, このとき <math>N _1\, </math> はバケーション開始時の客数とバケーション中の任意時刻までに到着する客数の和である. ある場合においては, G/G/1待ち行列のバケーションモデルにおいても分解定理が成り立つ. | ||
| − | さらに, サービスが[[先着順サービス|先着順]]に行なわれ, バケーションが将来の到着過程に依存しない場合には, 客の待ち時間の分布関数の[[ラプラス変換|ラプラス・スチルチェス変換]]に対する同様の分解定理も成り立つ. 例えば, M/G/1待ち行列の全処理式多重バケーションモデルにおいて, 客の平均待ち時間は, [[ポラチェック・ヒンチンの公式]] (Pollaczek-Khintchine formula) として知られるバケーションのない場合の平均待ち時間と, 1回のバケーション時間<math> V\, </math> の平均前方再生時間 <math>\mbox{E} [ V ^2 ] / ( 2 \mbox{E}[V] )\, </math> の和で与えられる. 従って, <math>V\, </math> の分散が大きいシステムでは, <math>V\, </math> を一定長だけ延ばすと平均待ち時間が減少するというパラドクスが生じる [ | + | さらに, サービスが[[先着順サービス|先着順]]に行なわれ, バケーションが将来の到着過程に依存しない場合には, 客の待ち時間の分布関数の[[ラプラス変換|ラプラス・スチルチェス変換]]に対する同様の分解定理も成り立つ. 例えば, M/G/1待ち行列の全処理式多重バケーションモデルにおいて, 客の平均待ち時間は, [[ポラチェック・ヒンチンの公式]] (Pollaczek-Khintchine formula) として知られるバケーションのない場合の平均待ち時間と, 1回のバケーション時間<math> V\, </math> の平均前方再生時間 <math>\mbox{E} [ V ^2 ] / ( 2 \mbox{E}[V] )\, </math> の和で与えられる. 従って, <math>V\, </math> の分散が大きいシステムでは, <math>V\, </math> を一定長だけ延ばすと平均待ち時間が減少するというパラドクスが生じる [3]. |
| − | '''ポーリングモデル''' | + | '''ポーリングモデル''' [[ポーリングモデル]] (polling model) とは, 複数の待ち行列を1つのサーバが巡回的にサービスするシステムのことである. サーバが1つの待ち行列から次の待ち行列に移るための移動時間を仮定してもよい. 各待ち行列にとって, 他の待ち行列のサービス時間と移動時間は, サーバのバケーションとみなされる. M/G/ <math>\cdot\, </math> 待ち行列のポーリングモデルについても, 確率的分解定理が成り立つ. これを利用して, すべての待ち行列が同等な場合に, 平均待ち時間の公式が得られる. 各待ち行列のパラメタが異なる一般の場合に, 平均待ち時間を表す公式は得られていない(数値的には計算できる)が, それらにトラヒック強度の重みを付けて加えた量に対する疑似保存則 (quasi-conservation law) が導かれている [4, 5]. |
| 30行目: | 33行目: | ||
[1] H. Takagi, ''Queueing Analisis: A Foundation of Performance Evaluation'', Vols. 1-3, Elsevier, 1991, 1993, 1993. | [1] H. Takagi, ''Queueing Analisis: A Foundation of Performance Evaluation'', Vols. 1-3, Elsevier, 1991, 1993, 1993. | ||
| − | [2] R. B. Cooper, S. -C. Niu and M. M. Srinivasan, "Some Reflections on the Renewal-Theory Paradox in Queueing Theory," ''Journal of Applied Mathematics and Stochastic Analysis'', '''11''' (1998), 355-368. | + | [2] D.-A.Wu and H.Takagi, "M/G/1 Queue with Multiple Working Vacations," ''Performance Evaluation'', '''63''' (2006), 654-681. |
| + | |||
| + | [3] R. B. Cooper, S. -C. Niu and M. M. Srinivasan, "Some Reflections on the Renewal-Theory Paradox in Queueing Theory," ''Journal of Applied Mathematics and Stochastic Analysis'', '''11''' (1998), 355-368. | ||
| + | |||
| + | [4] H. Takagi, ''Analysis of Polling Systems'', MIT Press, 1986. | ||
| − | [ | + | [5] 高木英明, 「ポーリングモデル：巡回サービス多重待ち行列」, 『オペレーションズ・リサーチ』, ''41'' (1996), 108-118. |
| + | --> | ||
| − | [ | + | [[category:待ち行列|まちぎょうれつのばけーしょんさーばもでる]] |
2008年11月6日 (木) 18:10時点における最新版
【まちぎょうれつのばけーしょんさーばもでる (queueing model with a vacationing server) 】
こちらを参照してください： サーバのバケーションがある待ち行列