どうも！初めましての方は初めまして、初心者のWebサイト勉強のとみーです！
確率論の応用としてよく取り上げられるのが、待ち行列です。
応用範囲の広い強力な理論です！
今回は待ち行列理論のイントロダクションとして、
待ち行列とは何か？
ということに焦点を当ててわかりやすく解説します。
確率の基本的な知識がある方（高校数学〜大学入門）
待ち行列理論の待ち行列とは？
待ち行列理論で取り上げる待ち行列は、
サービスを受けるために顧客が行列を作って並ぶ
様子をモデル化したものです。
ここでいう「モデル化」は、特定の確率分布に当てはめるような形で確率的な議論を行うという意味です。
待ち行列の具体例
待ち行列は日常生活の至るところに存在するので、具体例もイメージしやすいものがたくさんあります。
例えば、店舗で買い物をする場合にレジできる会計待ちの列は待ち行列です。
この場合、「会計を行い商品の購入を終える」というのがサービスで、このサービスのために顧客は列を作っています。
そのほかにも次のような例があります。
コールセンターの場合は物理的に列を作って待つわけではありませんが、サービス待ちをしている人が順番に案内される様子は列そのものですよね。
待ち行列の構成要素
ここまでで待ち行列のイメージはできたでしょうか？
ここからは待ち行列をもう少し正確に見ていきましょう。
待ち行列には、次の３つの要素があります。
- 列を作るもの
- サービスを提供するもの
- 列そのもの
１つずつ見ていきましょう。
待ち行列の顧客
待ち行列の構成要素の１つ目は
サービスを受けようと列を作っているもの
です。
多くの場合は人なので一般的には顧客と呼ばれますが、列を作るのが人ではないケースというのも存在します。
例えばコンピューター内では色々な処理が動いており、ある処理が終わったら次の処理、という具合に「処理待ちの列」ができています。
こうした場合に顧客と呼ぶのは不自然ですよね。。。
そのため、必ずしも顧客と呼ばれるわけではなく、文脈や考察の対象に応じて呼び名が変わることに注意しましょう。
コンピュータで処理を待っているものはジョブと呼ばれます。
待ち行列のサーバー
待ち行列の構成要素の２つ目は
サービスを提供するもの
で、一般的にはサーバーと呼ばれます。
言い換えれば、顧客がどこから／誰からサービスを受け取るかということです。
上で挙げた待ち行列の例のそれぞれについて、サーバーは次の通りです。
待ち行列の列
待ち行列の構成要素の３つ目は
顧客が作る列そのもの
です。
レジ待ちのように物理的な列もあれば、コールセンターの電話待ちのように存在しないものの仮想的に考えられる列もあります。
ただし、待ち行列として考えるにはいずれの場合も FIFO というルールに従う必要があります。
確率や統計の専門性は理系の就活でかなり優位に働きます。
そのため、エンジニア就活特化のプラットフォームを使えば他では見られない高待遇な就職先が見つかります！
| 特徴 | リンク | |
|---|---|---|
| UZUZ理系 |
|
|
| エンジニア就活 |
|
|
| レバテックルーキー |
|
経験不足で大丈夫かな…という方はプログラミングスクールでスキルアップしておくとバッチリです。
| 特徴 | リンク | |
|---|---|---|
| エンジニアズゲート |
|
|
| TechAcademy |
|
エンジニアズゲート
FIFO (First In First Out) とは？
FIFO (First In First Out) は日本語に直すと「先入れ先出し」、つまり
早く並び始めた人から早くサービスを受けられる
というルールです。
日常生活で目にする列は基本的に FIFO となっていますが、例外的に列の順番が変わることもありますよね。
このような場合は FIFO が成り立たなくなってしまうので、待ち行列として扱うことができません。
１度列に並んだら最後まで待ち続ける！途中入りはしない！そんな列なら大丈夫です。
待ち行列モデルの分類
待ち行列は応用範囲が広いため、待ち行列と一口に言っても色々な種類、モデルがあります。
全部を一緒くたに扱うのは限界があるのです。。。
そのため、一定の基準にしたがって待ち行列モデルを分類し、分類されたモデルごとに分析するのが一般的です。
ここからはどのように待ち行列モデルを分類し、それぞれのモデルがどのように表されるかを見ていきましょう。
待ち行列モデルの分類基準
モデルの分類は、以下の３つの要素をもとにして行われます。
- 到着の確率分布・確率過程：顧客はどのように列に到着するか
- サービス時間の確率分布：サービスはどのくらいの時間で提供されるか
- サーバー数：サーバーはいくつあるか
１つずつ順番に見ていきましょう。
到着の確率分布・確率過程
待ち行列理論では、顧客の到着を確率分布でモデル化します。
より正確には、
到着間隔を確率分布でモデル化
します。
実際は「到着間隔は指数分布にしたがう」と仮定することが多いです。
ちなみに、到着間隔が指数分布にしがたう場合、到着数はポアソン過程にしがたいます。
指数分布はマルコフ性を持つという特徴があります。
マルコフ性は過去の到着やサービスの情報を考慮しないという性質なので、マルコフ性を使うと時間的な依存関係を簡略化してモデル化できるというメリットがあります。
現在の状態に基づいて次の状態への遷移確率を定義するため、顧客の到着やサービス終了などのイベントの発生確率をモデル化するのに適しています。
また、到着数はポアソン過程に従いますが、ポアソン分布は平均発生回数が一定の事象がランダムに発生するシステムをモデル化するのが得意です。
したがって、ランダムに発生する事象をモデル化するために、多くの場合発生間隔に指数分布を仮定します。
その上、マルコフ性を持つ唯一の連続型確率分布は指数分布という性質もあるため、連続時間においてマルコフ性を使って解析を行う上で、指数分布以外を採用することが少ないのです。
サービス時間の確率分布
待ち行列理論では、
サービスにかかる時間も確率分布でモデル化
します。
ここでも「サービス時間は指数分布にしたがう」と仮定することが多いです。
到着間隔と同様に、サービス時間が指数分布にしがたう場合、サービス数はポアソン過程にしがたいます。
サーバー数
待ち行列モデルを決定付ける３つ目の要素はサーバー数です。
これは単純に
サービスを提供できるサーバーがいくつあるか
という数です。
到着の確率分布・確率過程やサービス時間の確率分布とは異なり、サーバー数は設定によって様々です。
また、サーバーが十分多く存在する場合は∞として扱うこともあります。
待ち行列モデルを表すケンドールの記号
以上の３要素
- 到着の確率分布・確率過程
- サービス時間の確率分布
- サーバー数
で待ち行列モデルは分類されますが、それぞれのモデルを表すためにはケンドールの記号という表現方法が使用されます。
ケンドールの記号は、列を
到着の確率分布/サービス時間の確率分布/サーバー数
のように表します。
それぞれのフィールドは、記号を使って例えば「M/M/1」のように表現します。
以下ではどの分布がどの記号で表されるかを見ていきましょう。
到着の確率分布を表す記号
到着の確率分布は、次の表にしたがって表します。
| 記号 | 到着間隔の確率分布 | 到着数の確率過程 | 説明 |
|---|---|---|---|
| M | 指数分布 | ポアソン過程 | M は Markovian（マルコフ連鎖）を表す |
| G | 一般分布 | – | G は General（一般）を表す |
指数分布は、連続型確率分布の中で唯一マルコフ性を持っています。
そのため、M（Markovchain）と書けば指数分布を表します。
サービス時間の確率分布を表す記号
サービス時間の確率分布は、次の表にしたがって表します。
| 記号 | サービス時間の確率分布 | サービス数の確率過程 | 説明 |
|---|---|---|---|
| M | 指数分布 | ポアソン過程 | M は Markovian（マルコフ連鎖）を表す |
| G | 一般分布 | – | G は General（一般）を表す |
到着の確率分布・確率過程もサービス時間の確率分布も他の記号がありますが、ほとんどの場合 M と G だけを押さえておけば十分です。
サーバー数を表す記号
サーバー数は数字をそのまま使います。
サーバー数が１なら１，十分多くあるなら∞です。
ケンドールの記号を使った待ち行列モデルの表記例
以上が整理できたら、いくつか例を確認しておきましょう。
M/M/1 待ち行列は、待ち行列理論における最も基本的なモデルとして扱われています。
まとめ
今回は、待ち行列理論のイントロダクションとして待ち行列とケンドールの記号についてご紹介しました。
待ち行列理論の記事は今後追加していく予定です！
コメント