「《待ち行列の各種モデル》」の版間の差分

2008年8月5日 (火) 15:40時点における最新版

【まちぎょうれつのかくしゅもでる (extended queueing models) 】

　待ち行列モデル (queueing model)は, 標準型モデルの到着過程, サービス規律, 行列への並び方, 系に入れない場合の客の行動, などを変えることによって各種の拡張モデルが考えられる.

系内客数に依存する到着過程　到着過程としては, ポアソン到着(Poisson arrivals) のような系の状態に独立な到着過程 (arrival process) に対して, 系内客数に依存するものが考えられ, 有限呼源待ち行列 (finite source queues) がその代表例である. このモデルは, ケンドールの記号 (Kendall's notation) を拡張して, 呼源数が $m\,$ のとき ${\mbox{A}}(m)/{\mbox{B}}/c\,$ と記述される. 各呼源は, 要求を発生するまでの空き状態, 系内における待ち合わせ状態, およびサービス中の状態を順番に繰り返す. これは現実の電話交換や機械修理によく見られるモデルである. 電話交換では, 交換機に接続された入回線数が比較的少ないとき, 交換機に加わる接続要求は空いている各入回線から指数分布間隔で発生すると近似される. 出回線数 $c\,$ が入回線数 $m\,$ より少ない場合に交換接続は損失系 ${\mbox{M}}(m)/{\mbox{M}}/c/c\,$ モデルとなる[4]. 機械修理工モデル (machine repairman's model) は, 有限呼源待ち行列の一種であり, 機械の稼働中が’空き’に, 故障中で修理待ちが’待ち合わせ’に, また修理中が’サービス中’に相当する. 機械の数が $m\,$ 個, 修理工が $c\,$ 人で, 機械の稼働時間分布および修理時間分布が指数分布のとき, ${\mbox{M}}(m)/{\mbox{M}}/c\,$ モデルとなる. この場合の評価尺度は機械の稼働率や修理工の稼働率である. また, このモデルの平均系内時間は, 会話型計算機システムでの平均応答時間に相当する.

集団到着・集団サービス　到着過程の変形として, 客が団体として到着し個別にサービスされる集団到着 (batch arrival) がある. この場合は, 集団の到着過程と集団サイズの分布が問題となる. 待ち時間を考える場合は, 同一集団内でのサービス順も問題となるが, 通常ランダム順サービス (random order service) が用いられる. 計算機システムや交換機処理系では, 1つのジョブが複数個のタスクに分解されて独立に処理され, 同一集団の全タスクが処理されてから初めてジョブの処理が終了するような処理が行われる. すなわち, 集団到着・個別処理であるが, 同一集団の全ての客の処理終了に同期して系を去るようなモデルであり, このような処理系はフォークジョイン待ち行列 (fork-join queue) モデル[2]となる.

　サービス規律としては, 複数の客をまとめて集団でサービスする集団サービス(bulk service)がある. 一回のサービスで処理できる最大客数やサービス開始する最小客数が重要なパラメタとなる. 集団到着あるいは集団サービスのある待ち行列をまとめて集団待ち行列 (bulk queue) という. 集団待ち行列は, ケンドールの記号を拡張して, ${\mbox{A}}^{[X]}/{\mbox{B}}^{[Y]}/c\,$ で表わされる.

優先権　優先権 (priority) によりサービスの順番を定める優先権待ち行列 (priority queues) では, 高い優先権の客が低い優先権の客のサービスに割り込む割込優先権 (preemptive priority) と割り込まない非割込優先権(nonpreemptive priority)がある. 割込優先権の場合, 割り込まれた客のサービスに関し, 損失とする損失形 (lost), 中断点からサービスを再開する継続形 (resume), 中断点に関係なく最初からサービスをやり直す反復形 (repeat) などがある. 一般に, 計算機システムでのジョブの処理では割込優先権が用いられ, メッセージ伝送では非割込優先権が用いられる. 客のクラスの優先権が定まっていない場合, 各クラスに優先権を割り当てる問題がある. クラス $i\,$ の客の平均サービス時間を $1/\mu _{i}\,$ , 系内時間当たりのコストを $c_{i}\,$ とするとき, 系内時間による総合期待コストを最小にする割当て方法として, ある条件の待ち行列モデルでは, 「 $c_{i}\mu _{i}\,$ が大きい順に高い優先権を与えればよい」という $c\mu \,$ ルールが成立する[3].

　系内の状態により定まる内部優先権としては, 他の客のクラスとの相互関係により定まるものや, 待ち時間や経過サービス時間等の客の系内での状態により定まるものが考えられる. 後者の例としては, サービス時間が最短の客からサービスする最短サービス時間順待ち行列 (shortest-service-time-first queue) がある. 最短サービス時間順サービス規律は, 最初, 機械修理問題で修理時間が短い故障の修理を優先するモデルとして解析され, その後計算機システムのOSでのジョブ・スケジューリングにおいて, 処理時間が最短のジョブから処理する最短処理時間順 (SPT, shortest-processing-time-first) 規律として研究された.

並列待ち行列　各サーバの前にそれぞれ待ち行列が出来る並列待ち行列 (parallel queues) では, 到着した客を行列へ割り付ける方法が問題となる. 通常は, 新たに到着する客は最短の行列に加わり, このような割り付けを最短待ち行列 (shortest queues) 割り付けという. このモデルは古くから研究が行われてきたが, 途中で行列を変わる鞍替えがない場合でも解析が複雑である. 最短待ち行列は, 各待ち行列が ${\mbox{M}}/{\mbox{M}}/1\,$ モデルの場合, 総合系内客数の期待値を最小にするという意味で最適な方法である. この他, 客を並列待ち行列へ割り付ける方法としてラウドロビン(round-robin)割り付けがある. これは, 到着する客を順番に並列待ち行列に割り付けていく方法であり, 待ち行列長の観測が不可能な場合には, 総合系内客数の期待値を最小にするという意味で最適な方法である.

再試行モデル　到着した客が系内に入れないときの客の振る舞いは, 去ったまま戻ってこない損失モデルとある時間をおいて再びサービスを受けに来る再試行 (retrial) モデルに分かれる. 電話交換における用語に基づき, 再び到着する客を再呼 (repeated call) といい, 再呼のある待ち行列モデルは再呼モデル (repeated call model) あるいは再試行モデル (retrial model) [1]と呼ばれる. 再呼の到着過程は, 系を去って再び到着するまでの状態にある客数を呼源とする有限呼源となる. このモデルは, 損失系で全サーバがサービス中のとき系内に入れない損失モデルと, 有限待合室モデル (finite-buffer model) で待合室が満杯のとき系内に入れない待ち合わせモデルに分かれる. 損失モデルは, 新しい呼の到着がポアソン到着で, サービス時間分布が指数分布, 再呼間隔が指数分布の場合は, ${\mbox{M}}/{\mbox{M}}/c/c\,$ モデルに有限呼源の再呼が加わるモデルとなる. このモデルは, 電話交換において話中に遭遇した呼の再呼を考慮した呼損率 (loss probability) などのサービス品質を評価するのに用いられてきた.

タクシー乗り場モデル　これまでは, 客がサービスをする場所に到着し, サービスを受けてその場所を去る系のみを考えてきた. 問題によってはサーバが移動する場合も考えられ, その例としてタクシー乗り場モデル (taxi stand model)がある. タクシー乗り場には, 乗客の行列とタクシーの行列ができるが, どちらがサーバでどちらが客であるかは評価尺度を考えることにより相対的に定まる. 通常はいずれか一方の行列のみができるか, または両方とも空であるが, 乗車時間がかかる場合は両方に行列ができる.

参考文献

[1] G. I. Falin and J. G. C. Templeton, Retrial Queues, Chapman & Hall, 1997.

[2] R. Nelson, Probability, Stochastic Processes, and Queueing Theory, Springer-Verlag, 1995.

[3] R. W. Wolff, Stochastic Mopdeling and the Theory of Queues, Prentice-Hall, 1989.

[4] 高橋敬隆, 『わかりやすい待ち行列システム』, コロナ社, 2003.

@@ 4行目: / 4行目: @@
-'''系内客数に依存する到着過程'''　到着過程としては, [[ポアソン到着]](Poisson arrivals) のような系の状態に独立な[[到着過程]] (arrival process) に対して, 系内客数に依存するものが考えられ, [[有限呼源待ち行列]] (finite source queues) がその代表例である. このモデルは, [[ケンドールの記号]] (Kendall's notation) を拡張して, 呼源数が$m$のとき$\mbox{A}(m)/\mbox{B}/c$と記述される. 各呼源は, 要求を発生するまでの空き状態, 系内における待ち合わせ状態, およびサービス中の状態を順番に繰り返す. これは現実の電話交換や機械修理によく見られるモデルである. 電話交換では, 交換機に接続された入回線数が比較的少ないとき, 交換機に加わる接続要求は空いている各入回線から指数分布間隔で発生すると近似される. 出回線数$c$が入回線数$m$より少ない場合に交換接続は損失系$\mbox{M}(m)/\mbox{M}/c/c$モデルとなる. [[機械修理工モデル]] (machine repairman's model) は, 有限呼源待ち行列の一種であり, 機械の稼働中が’空き’に, 故障中で修理待ちが’待ち合わせ’に, また修理中が’サービス中’に相当する. 機械の数が$m$個, 修理工が$c$人で, 機械の稼働時間分布および修理時間分布が指数分布のとき, $\mbox{M}(m)/\mbox{M}/c$モデルとなる. この場合の評価尺度は機械の稼働率や修理工の稼働率である. また, このモデルの平均系内時間は, 会話型計算機システムでの平均応答時間に相当する.
+'''系内客数に依存する到着過程'''　到着過程としては, [[ポアソン到着]](Poisson arrivals) のような系の状態に独立な[[到着過程]] (arrival process) に対して, 系内客数に依存するものが考えられ, [[有限呼源待ち行列]] (finite source queues) がその代表例である. このモデルは, [[ケンドールの記号]] (Kendall's notation) を拡張して, 呼源数が<math>m\, </math>のとき<math>\mbox{A}(m)/\mbox{B}/c\, </math>と記述される. 各呼源は, 要求を発生するまでの空き状態, 系内における待ち合わせ状態, およびサービス中の状態を順番に繰り返す. これは現実の電話交換や機械修理によく見られるモデルである. 電話交換では, 交換機に接続された入回線数が比較的少ないとき, 交換機に加わる接続要求は空いている各入回線から指数分布間隔で発生すると近似される. 出回線数<math>c\, </math>が入回線数<math>m\, </math>より少ない場合に交換接続は損失系<math>\mbox{M}(m)/\mbox{M}/c/c\, </math>モデルとなる[4]. [[機械修理工モデル]] (machine repairman's model) は, 有限呼源待ち行列の一種であり, 機械の稼働中が’空き’に, 故障中で修理待ちが’待ち合わせ’に, また修理中が’サービス中’に相当する. 機械の数が<math>m\, </math>個, 修理工が<math>c\, </math>人で, 機械の稼働時間分布および修理時間分布が指数分布のとき, <math>\mbox{M}(m)/\mbox{M}/c\, </math>モデルとなる. この場合の評価尺度は機械の稼働率や修理工の稼働率である. また, このモデルの平均系内時間は, 会話型計算機システムでの平均応答時間に相当する.
-'''集団到着・集団サービス'''　到着過程の変形として, 客が団体として到着し個別にサービスされる集団到着 (batch aarival) がある. この場合は, 集団の到着過程と集団サイズの分布が問題となる. 待ち時間を考える場合は, 同一集団内でのサービス順も問題となるが, 通常[[ランダム順サービス]] (random order service) が用いられる. 計算機システムや交換機処理系では, 1つのジョブが複数個のタスクに分解されて独立に処理され, 同一集団の全タスクが処理されてから初めてジョブの処理が終了するような処理が行われる. すなわち, 集団到着・個別処理であるが, 同一集団の全ての客の処理終了に同期して系を去るようなモデルであり, このような処理系は[[フォークジョイン待ち行列]] (fork-join queue) モデルとなる.
+'''集団到着・集団サービス'''　到着過程の変形として, 客が団体として到着し個別にサービスされる集団到着 (batch arrival) がある. この場合は, 集団の到着過程と集団サイズの分布が問題となる. 待ち時間を考える場合は, 同一集団内でのサービス順も問題となるが, 通常[[ランダム順サービス]] (random order service) が用いられる. 計算機システムや交換機処理系では, 1つのジョブが複数個のタスクに分解されて独立に処理され, 同一集団の全タスクが処理されてから初めてジョブの処理が終了するような処理が行われる. すなわち, 集団到着・個別処理であるが, 同一集団の全ての客の処理終了に同期して系を去るようなモデルであり, このような処理系は[[フォークジョイン待ち行列]] (fork-join queue) モデル[2]となる.
-　サービス規律としては, 複数の客をまとめて集団でサービスする集団サービス(bulk service)がある. 一回のサービスで処理できる最大客数やサービス開始する最小客数が重要なパラメタとなる. 集団到着あるいは集団サービスのある待ち行列をまとめて[[集団待ち行列]] (bulk queue) という. 集団待ち行列は, [[ケンドールの記号]]を拡張して, $\mbox{A}^{[X]}/\mbox{B}^{[Y]}/c$で表わされる.
+　サービス規律としては, 複数の客をまとめて集団でサービスする集団サービス(bulk service)がある. 一回のサービスで処理できる最大客数やサービス開始する最小客数が重要なパラメタとなる. 集団到着あるいは集団サービスのある待ち行列をまとめて[[集団待ち行列]] (bulk queue) という. 集団待ち行列は, [[ケンドールの記号]]を拡張して, <math>\mbox{A}^{[X]}/\mbox{B}^{[Y]}/c\, </math>で表わされる.
-'''優先権'''　[[優先権]] (priority) によりサービスの順番を定める[[優先権待ち行列]] (priority queues) [4] では, 高い優先権の客が低い優先権の客のサービスに割り込む割込優先権 (preemptive priority) と割り込まない非割込優先権(nonpreemptive priority)がある. 割込優先権の場合, 割り込まれた客のサービスに関し, 損失とする損失形 (lost), 中断点からサービスを再開する継続形 (resume), 中断点に関係なく最初からサービスをやり直す反復形 (repeat) などがある. 一般に, 計算機システムでのジョブの処理では割込優先権が用いられ, メッセージ伝送では非割込優先権が用いられる. 客のクラスの優先権が定まっていない場合, 各クラスに優先権を割り当てる問題がある. クラス$i$の客の平均サービス時間を$1/\mu_i$, 系内時間当たりのコストを$c_i$とするとき, 系内時間による総合期待コストを最小にする割当て方法として, ある条件の待ち行列モデルでは, 「$c_i\mu_i$が大きい順に高い優先権を与えればよい」という$c\mu$ルールが成立する.
+'''優先権'''　[[優先権]] (priority) によりサービスの順番を定める[[優先権待ち行列]] (priority queues)  では, 高い優先権の客が低い優先権の客のサービスに割り込む割込優先権 (preemptive priority) と割り込まない非割込優先権(nonpreemptive priority)がある. 割込優先権の場合, 割り込まれた客のサービスに関し, 損失とする損失形 (lost), 中断点からサービスを再開する継続形 (resume), 中断点に関係なく最初からサービスをやり直す反復形 (repeat) などがある. 一般に, 計算機システムでのジョブの処理では割込優先権が用いられ, メッセージ伝送では非割込優先権が用いられる. 客のクラスの優先権が定まっていない場合, 各クラスに優先権を割り当てる問題がある. クラス<math>i\, </math>の客の平均サービス時間を<math>1/\mu_i\, </math>, 系内時間当たりのコストを<math>c_i\, </math>とするとき, 系内時間による総合期待コストを最小にする割当て方法として, ある条件の待ち行列モデルでは, 「<math>c_i\mu_i\, </math>が大きい順に高い優先権を与えればよい」という<math>c\mu\, </math>ルールが成立する[3].
-　系内の状態により定まる内部優先権としては, 他の客のクラスとの相互関係により定まるものや, 待ち時間や経過サービス時間等の客の系内での状態により定まるものが考えられる. 後者の例としては, サービス時間が最短の客からサービスする[[最短サービス時間順待ち行列]] (shortest-service-time-first queue) がある. 最短サービス時間順サービス規律は, 最初, 機械修理問題で修理時間が短い故障の修理を優先するモデルとして解析され, その後計算機システムのOSでのジョブ・スケジューリングにおいて, 処理時間が最短のジョブから処理する最短処理時間順 (SPT, shortest-processing-time-first) 規律として研究された.
+　系内の状態により定まる内部優先権としては, 他の客のクラスとの相互関係により定まるものや, 待ち時間や経過サービス時間等の客の系内での状態により定まるものが考えられる. 後者の例としては, サービス時間が最短の客からサービスする[[最短サービス時間順規律|最短サービス時間順待ち行列]] (shortest-service-time-first queue) がある. 最短サービス時間順サービス規律は, 最初, 機械修理問題で修理時間が短い故障の修理を優先するモデルとして解析され, その後計算機システムのOSでのジョブ・スケジューリングにおいて, 処理時間が最短のジョブから処理する最短処理時間順 (SPT, shortest-processing-time-first) 規律として研究された.
-'''並列待ち行列'''　各サーバの前にそれぞれ待ち行列が出来る[[並列待ち行列]] (parallel queues) では, 到着した客を行列へ割り付ける方法が問題となる. 通常は, 新たに到着する客は最短の行列に加わり, このような割り付けを最短待ち行列 (shortest queues) 割り付けという. このモデルは古くから研究が行われてきたが, 途中で行列を変わる鞍替えがない場合でも解析が複雑である. 最短待ち行列は, 各待ち行列が$\mbox{M}/\mbox{M}/1$モデルの場合, 総合系内客数の期待値を最小にするという意味で最適な方法である. この他, 客を並列待ち行列へ割り付ける方法としてラウドロビン(round-robin)割り付けがある. これは, 到着する客を順番に並列待ち行列に割り付けていく方法であり, 待ち行列長の観測が不可能な場合には, 総合系内客数の期待値を最小にするという意味で最適な方法である.
+'''並列待ち行列'''　各サーバの前にそれぞれ待ち行列が出来る[[並列待ち行列]] (parallel queues) では, 到着した客を行列へ割り付ける方法が問題となる. 通常は, 新たに到着する客は最短の行列に加わり, このような割り付けを最短待ち行列 (shortest queues) 割り付けという. このモデルは古くから研究が行われてきたが, 途中で行列を変わる鞍替えがない場合でも解析が複雑である. 最短待ち行列は, 各待ち行列が<math>\mbox{M}/\mbox{M}/1\, </math>モデルの場合, 総合系内客数の期待値を最小にするという意味で最適な方法である. この他, 客を並列待ち行列へ割り付ける方法としてラウドロビン(round-robin)割り付けがある. これは, 到着する客を順番に並列待ち行列に割り付けていく方法であり, 待ち行列長の観測が不可能な場合には, 総合系内客数の期待値を最小にするという意味で最適な方法である.
-'''再試行モデル'''　到着した客が系内に入れないときの客の振る舞いは, 去ったまま戻ってこない損失モデルとある時間をおいて再びサービスを受けに来る再試行 (retrial) モデルに分かれる. 電話交換における用語に基づき, 再び到着する客を再呼 (repeated call) といい, 再呼のある待ち行列モデルは[[再呼モデル]] (repeated call model) と呼ばれる [2]. 再呼の到着過程は, 系を去って再び到着するまでの状態にある客数を呼源とする有限呼源となる. このモデルは, 損失系で全サーバがサービス中のとき系内に入れない損失モデルと, [[有限待合室モデル]] (finite-buffer model) で待合室が満杯のとき系内に入れない待ち合わせモデルに分かれる. 損失モデルは, 新しい呼の到着がポアソン到着で, サービス時間分布が指数分布, 再呼間隔が指数分布の場合は, $\mbox{M}/\mbox{M}/c/c$モデルに有限呼源の再呼が加わるモデルとなる. このモデルは, 電話交換において話中に遭遇した呼の再呼を考慮した呼損率}{呼損率} (loss probability) などのサービス品質を評価するのに用いられてきた.
+'''再試行モデル'''　到着した客が系内に入れないときの客の振る舞いは, 去ったまま戻ってこない損失モデルとある時間をおいて再びサービスを受けに来る再試行 (retrial) モデルに分かれる. 電話交換における用語に基づき, 再び到着する客を再呼 (repeated call) といい, 再呼のある待ち行列モデルは[[再呼モデル]] (repeated call model) あるいは再試行モデル (retrial model) [1]と呼ばれる. 再呼の到着過程は, 系を去って再び到着するまでの状態にある客数を呼源とする有限呼源となる. このモデルは, 損失系で全サーバがサービス中のとき系内に入れない損失モデルと, [[有限待合室モデル]] (finite-buffer model) で待合室が満杯のとき系内に入れない待ち合わせモデルに分かれる. 損失モデルは, 新しい呼の到着がポアソン到着で, サービス時間分布が指数分布, 再呼間隔が指数分布の場合は, <math>\mbox{M}/\mbox{M}/c/c\, </math>モデルに有限呼源の再呼が加わるモデルとなる. このモデルは, 電話交換において話中に遭遇した呼の再呼を考慮した[[呼損率]] (loss probability) などのサービス品質を評価するのに用いられてきた.
-'''タクシー乗り場モデル'''　これまでは, 客がサービスをする場所に到着し, サービスを受けてその場所を去る系のみを考えてきた. 問題によってはサーバが異動する場合も考えられ, その例として[[タクシー乗り場モデル]] (taxi stand model)がある. タクシー乗り場には, 乗客の行列とタクシーの行列ができるが, どちらがサーバでどちらが客であるかは評価尺度を考えることにより相対的に定まる. 通常はいずれか一方の行列のみができるか, または両方とも空であるが, 乗車時間がかかる場合は両方に行列ができる.
+'''タクシー乗り場モデル'''　これまでは, 客がサービスをする場所に到着し, サービスを受けてその場所を去る系のみを考えてきた. 問題によってはサーバが移動する場合も考えられ, その例として[[タクシー乗り場モデル]] (taxi stand model)がある. タクシー乗り場には, 乗客の行列とタクシーの行列ができるが, どちらがサーバでどちらが客であるかは評価尺度を考えることにより相対的に定まる. 通常はいずれか一方の行列のみができるか, または両方とも空であるが, 乗車時間がかかる場合は両方に行列ができる.
@@ 31行目: / 31行目: @@
 '''参考文献'''
-[1] R. B. Cooper, ''Introduction to Queueing Theory, Second Edition'', North-Holland, 1981.
+[1] G. I. Falin and J. G. C. Templeton, ''Retrial Queues'', Chapman & Hall, 1997.
-[2] G. I. Falin and J. G. C. Templeton, ''Retrial Queues'', Chapman & Hall, 1997.
+[2] R. Nelson, ''Probability, Stochastic Processes, and Queueing Theory'', Springer-Verlag, 1995.
-[3] 藤木正也, 願部頴一, 『通信トラヒック理論』, 丸善, 1980.
+[3] R. W. Wolff, ''Stochastic Mopdeling and the Theory of Queues'', Prentice-Hall, 1989.
-[4] N. K. aiswal, ''Priority Queues'', Academic Press, 1968.
+[4] 高橋敬隆, 『わかりやすい待ち行列システム』, コロナ社, 2003.
-[5] L. Kleinrock, ''Queueing Systems Volume II: Computer Applications'', John Wiley & Sons, 1976.
+[[category:待ち行列|まちぎょうれつのかくしゅもでる]]
-[6] T. L. Saaty, ''Elements of Queueing Theory with Applications'', Dover, 1961.

「《待ち行列の各種モデル》」の版間の差分

2008年8月5日 (火) 15:40時点における最新版

案内メニュー

検索