待ち行列理論

待ち行列理論は、待ち行列、つまりキューの数学的研究です。^{[ 1 ]}待ち行列モデルは、待ち行列の長さと待ち時間を予測できるように構築されます。^{[ 1 ]}待ち行列理論は、サービスの提供に必要なリソースに関するビジネス上の意思決定を行う際に結果がよく使用されるため、一般的にオペレーションズリサーチの一分野と考えられています。

待ち行列理論は、コペンハーゲン電話交換会社の着信通話システムを記述するモデルを作成したアグナー・クラルプ・エルランの研究に端を発しています。 ^{[ 1 ]}これらのアイデアはテレトラフィック工学の分野にとって重要なものであり、その後、電気通信、交通工学、コンピューティング^{[ 2 ]} 、プロジェクト管理、そして特に産業工学に応用され、工場、店舗、オフィス、病院の設計に利用されています。^{[ 3 ] [ 4 ]}

待ち行列理論は、経営科学の分野における主要な研究領域の 1 つです。経営科学を通じて、企業はさまざまな科学的および数学的手法を使用してさまざまな問題を解決できます。待ち行列分析は待ち行列の確率的分析であり、したがって、運用特性とも呼ばれる結果は、決定論的ではなく確率的です。^{[ 5 ]}待ち行列システムに n 人の顧客がいる確率、待ち行列システム内の顧客の平均数、待ち行列内の顧客の平均数、待ち行列システム全体で顧客が費やす平均時間、待ち行列で顧客が費やす平均時間、そして最後に、サーバーがビジーまたはアイドルである確率は、これらの待ち行列モデルが計算するさまざまな運用特性です。^{[ 5 ]}待ち行列分析の全体的な目標は、現在のシステムについてこれらの特性を計算し、改善につながる可能性のあるいくつかの代替案をテストすることです。現在のシステムの運用特性を計算し、その値を代替システムの特性と比較することで、管理者は各潜在的なオプションの長所と短所を確認できます。これらのシステムは、節約を増やす方法、待ち時間を短縮する方法、効率を向上させる方法などを示すことで、最終的な意思決定プロセスを支援します。使用できる主な待ち行列モデルは、単一サーバー待ち行列システムと複数サーバー待ち行列システムであり、これらについては後述します。これらのモデルは、サービス時間が一定か不定か、待ち行列の長さが有限か、呼び出し母集団が有限かなどに応じてさらに区別できます。^{[ 5 ]}

キューまたはキューイングノードは、ほぼブラックボックスと考えることができます。ジョブ（分野によっては顧客またはリクエストとも呼ばれます）はキューに到着し、場合によってはしばらく待機し、処理に時間がかかり、その後キューから出ていきます。

しかし、キューイングノードは完全なブラックボックスではなく、その内部に関する情報が必要となります。キューには1つ以上のサーバーがあり、それぞれが到着するジョブとペアリングされます。ジョブが完了してキューから出ると、そのサーバーは再び別の到着ジョブとペアリングできるようになります。

よく用いられる例えは、スーパーマーケットのレジ係です。顧客が到着し、レジ係が処理し、そして退店します。各レジ係は一度に1人の顧客を処理するため、これはサーバーが1つしかないキューイングノードです。顧客が到着したときにレジ係が忙しい場合、顧客はすぐに退店する設定は、バッファのないキュー（または待機エリアのないキュー）と呼ばれます。最大n人の顧客のための待機ゾーンがある設定は、サイズnのバッファを持つキューと呼ばれます。

出生・死亡過程

単一のキュー（キューイングノードとも呼ばれる）の挙動は、キューへの到着と出発、およびシステム内に現在存在するジョブの数を表す出生・死亡プロセスによって記述できます。kをシステム内のジョブ数（処理中またはキューに待機ジョブのバッファがある場合は待機中）とすると、到着によってk が1増加し、出発によってkが 1 減少します。

システムは、到着率で発生する出生と死亡によってkの値の間を遷移します。$\displaystyle \lambda _{i}}$出発率$\displaystyle \mu _{i}}$各仕事について${\displaystyle i}$キューの場合、これらのレートは一般的にキュー内のジョブ数によって変化しないと考えられているため、単位時間あたりの到着/出発の平均レートが1つだけ仮定されます。この仮定の下では、このプロセスの到着レートは次のようになります。${\displaystyle \lambda ={\text{avg}}(\lambda _{1},\lambda _{2},\dots ,\lambda _{k})}$出発率は${\displaystyle \mu ={\text{avg}}(\mu _{1},\mu _{2},\dots ,\mu _{k})}$。

バランス方程式

出生と死亡過程の定常状態方程式（平衡方程式として知られる）は以下のとおりである。${\displaystyle P_{n}}$状態nにある定常状態確率を表す。

${\displaystyle \mu _{1}P_{1}=\lambda _{0}P_{0}}$

${\displaystyle \lambda _{0}P_{0}+\mu _{2}P_{2}=(\lambda _{1}+\mu _{1})P_{1}}$

${\displaystyle \lambda _{n-1}P_{n-1}+\mu _{n+1}P_{n+1}=(\lambda _{n}+\mu _{n})P_{n}}$

最初の2つの式は、

${\displaystyle P_{1}={\frac {\lambda _{0}}{\mu _{1}}}P_{0}}$

そして

${\displaystyle P_{2}={\frac {\lambda _{1}}{\mu _{2}}}P_{1}+{\frac {1}{\mu _{2}}}(\mu _{1}P_{1}-\lambda _{0}P_{0})={\frac {\lambda _{1}}{\mu _{2}}}P_{1}={\frac {\lambda _{1}\lambda _{0}}{\mu _{2}\mu _{1}}}P_{0}}$。

数学的帰納法により、

${\displaystyle P_{n}={\frac {\lambda _{n-1}\lambda _{n-2}\cdots \lambda _{0}}{\mu _{n}\mu _{n-1}\cdots \mu _{1}}}P_{0}=P_{0}\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}$。

状態${\displaystyle \sum _{n=0}^{\infty }P_{n}=P_{0}+P_{0}\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}=1}$につながる

${\displaystyle P_{0}={\frac {1}{1+\sum _{n=1}^{\infty }\prod _{i=0}^{n-1}{\frac {\lambda _{i}}{\mu _{i+1}}}}}}$

これは、以下の式と合わせて${\displaystyle P_{n}}$${\displaystyle (n\geq 1)}$必要な定常状態確率を完全に記述します。

1909年、コペンハーゲン電話交換局に勤務していたデンマーク人エンジニア、アグナー・クララップ・エルランは、現在では待ち行列理論と呼ばれるものに関する最初の論文を発表した。 ^{[ 9 ] [ 10 ] [ 11 ]}彼は交換局に到着する電話の件数をポアソン過程によってモデル化し、1917年にM/D/1待ち行列、1920年にM/D/ k待ち行列モデルを解いた。 ^{[ 12 ]}ケンドールの記法では次のようになる。

• Mはマルコフ過程または無記憶過程を表し、到着がポアソン過程に従って発生することを意味します。
• Dは決定論的を意味し、キューに到着するジョブには一定量のサービスが必要であることを意味します。
• kはキューイングノードにあるサーバーの数を表します（k = 1、2、3、...）。

ノード内のジョブ数がサーバーの数より多い場合、ジョブはキューに格納され、処理待ちの状態になります。

M /G/1待ち行列は1930年にフェリックス・ポラチェックによって解決され^{[ 13 ]} 、その解は後にアレクサンドル・ヒンチンによって確率論的に再定式化され、現在ではポラチェック・ヒンチン公式として知られている^{[ 12 ] [ 14 ]}。

1940年代以降、待ち行列理論は数学者にとって研究対象となった。^{[ 14 ]} 1953年、デイビッド・ジョージ・ケンドールはGI/M/ k待ち行列を解き^{[ 15 ]} 、現在ケンドール記法として知られる待ち行列の現代的な記法を導入した。1957年、ポラチェックは積分方程式を用いてGI/G/1を研究した。^{[ 16 ]}ジョン・キングマンはG/G/1待ち行列の平均待ち時間の公式を与え、現在キングマンの公式として知られている。^{[ 17 ]}

レナード・クラインロックは、1960年代初頭にメッセージ交換への待ち行列理論の応用、 1970年代初頭にはパケット交換への応用に取り組んだ。この分野における彼の最初の貢献は、1962年にマサチューセッツ工科大学で提出した博士論文であり、1964年に書籍として出版された。1970年代初頭に発表された彼の理論的研究は、インターネットの前身であるARPANETにおけるパケット交換の利用を支えた。

行列幾何学的方法と行列解析的方法により、位相型分布の到着間隔とサービス時間分布を持つ待ち行列を考慮することが可能になった。 ^{[ 18 ]}

結合軌道を持つシステムは、無線ネットワークや信号処理への応用における待ち行列理論の重要な部分である。^{[ 19 ]}

現代における待ち行列理論の応用は、とりわけ製品開発に関わるものであり、製品には一定の量と一定の期間があるという意味で、（物質的な）製品には時空間的な存在がある。^{[ 20 ]}

M/G/ kキューのパフォーマンス指標などの問題は未解決の問題として残っている。^{[ 12 ] [ 14 ]}

キューイングノードでは、さまざまなスケジューリングポリシーを使用できます。

先入れ先出し

先着順（FCFS）^とも呼ばれるこの原則は、顧客は一度に一人ずつサービスを受け、最も長く待っている顧客が最初にサービスを受けるというものです。^{[ 21 ] [ 22 ]}

後から入庫、先出

この原則では、一度に一人ずつ顧客にサービスを提供しますが、待ち時間が最も短い顧客が最初にサービスを受けます。^{[ 22 ]}スタックとも呼ばれます。

プロセッサ共有

サービス容量は顧客間で均等に共有されます。^{[ 22 ]}

ランダムな順序でのサービス (SIRO)

ランダム順序サービス（ROS）とも呼ばれるこの方式では、次に処理されるジョブは、キューで待機しているジョブの中からランダムに選択されます。

優先度

優先度の高い顧客が最初にサービスを受けます。^{[ 22 ]}優先度キューには、非プリエンプティブ（処理中のジョブは中断できない）とプリエンプティブ（処理中のジョブは優先度の高いジョブによって中断される可能性がある）の2種類があります。どちらのモデルでも作業が失われることはありません。^{[ 23 ]}

一番短い仕事から始めよう

次に処理される仕事は、最も小さいサイズのものです。^{[ 24 ]}

先手を打って最短の仕事から始める

次に処理されるジョブは、元のサイズが最も小さいものです。^{[ 25 ]}

最短の残り処理時間

次に処理されるジョブは、残りの処理要件が最も少ないものです。^{[ 26 ]}

サービス施設

• シングルサーバー：顧客が列を作っているが、サーバーは1台しかない。
• 複数の並列サーバー（単一キュー）：顧客が列を作り、複数のサーバーが稼働している。
• 複数の並列サーバー（複数のキュー）：カウンターが多数あり、顧客はどのキューに並ぶかを選択できる。

信頼性の低いサーバー

サーバー障害は確率的（ランダム）プロセス（通常はポアソン分布）に従って発生し、その後、サーバーが利用できないセットアップ期間が発生します。中断された顧客は、サーバーが修復されるまでサービスエリアに留まります。^{[ 27 ]}

顧客の待ち時間行動

• 躊躇：列が長すぎる場合、顧客は列に並ばないことを決める。
• ジョッキング行為：顧客は、そうすることでより早くサービスを受けられると判断すれば、列の間を移動する。
• キャンセル：サービスを受けるまでに時間がかかりすぎた場合、顧客が列を離れる。

到着したものの、サービスを受けられなかった顧客（待ち行列に余裕がない場合、または顧客が拒否したりキャンセルしたりした場合）は、ドロップアウトと呼ばれます。ドロップアウトの平均率は、待ち行列の状態を表す重要な指標です。

キューネットワークとは、顧客ルーティングによって複数のキューが接続されたシステムです。顧客は、あるノードでサービスを受けた後、別のノードに移動してサービスを待つか、ネットワークから離脱することができます。

m個のノードからなるネットワークの場合、システムの状態はm次元ベクトル( x ₁ , x ₂ , ..., x _m )で表すことができ、x _iは各ノードの顧客数を表します。

最も単純な非自明な待ち行列ネットワークは、タンデム待ち行列と呼ばれます^。 [ 28 ^{]この分野}における最初の重要な成果は、効率的な積形式定常分布が存在し、平均値分析^{[ 31 ]（}スループットや滞在時間などの平均メトリックを計算できる）が可能なジャクソンネットワークでした。^[ 32 ^{]ネットワーク内}の顧客の総数が一定である場合、そのネットワークは閉じたネットワークと呼ばれ、ゴードン・ニューウェル定理によって積形式定常分布を持つことも示されています。^{[ 33 ]}この結果は、非常に一般的なサービス時間、レジーム、および顧客ルーティングを持つネットワークが積形式定常分布を示すことが示されたBCMPネットワークに拡張されました^。 [ ^{34 ]}正規化^定数は、 1973年に提案されたブゼンのアルゴリズムで計算できます。 ^{[ 35 ]}

ケリーネットワークのように、異なるクラスの顧客が異なるサービスノードで異なる優先順位レベルを経験する顧客ネットワークも調査されています。^{[ 36 ]}別のタイプのネットワークは、 1993年にエロル・ゲレンベによって最初に提案されたGネットワ​​ークです。 ^{[ 37 ]}これらのネットワークは、古典的なジャクソンネットワークのように指数時間分布を仮定しません。

• グロス、ドナルド、カール・M・ハリス（1998）。待ち行列理論の基礎。ワイリー。ISBN 978-0-471-32812-4。オンライン
• Zukerman, Moshe (2013).待ち行列理論と確率的テレトラフィックモデル入門(PDF) . arXiv : 1307.2968 .
• Deitel, Harvey M. (1984) [1982].オペレーティングシステム入門（改訂版 ）。Addison-Wesley。p . 673。ISBN  978-0-201-14502-1。第15章、 380～412ページ
• ゲレンベ、エロル、イシ・ミトラニ（2010）。コンピュータシステムの解析と合成。ワールドサイエンティフィック第2版。ISBN 978-1-908978-42-4。
• ニューウェル、ゴードロン F. (1971年6月1日).待ち行列理論の応用. チャップマン・アンド・ホール.
• レナード・クラインロック、「大規模通信ネットワークにおける情報フロー」（MIT、ケンブリッジ、1961年5月31日）博士論文提案書
• レナード・クラインロック著「大規模通信ネットワークにおける情報フロー」（RLE四半期進捗報告、1961年7月）
• レナード・クラインロック著『通信ネットワーク：確率的メッセージフローと遅延』（マグロウヒル社、ニューヨーク、1964年）
• クラインロック、レナード（1975年1月2日）。待ち行列システム：第1巻 ― 理論。ニューヨーク：ワイリー・インターサイエンス。417ページ。ISBN  978-0-471-49110-1。
• クラインロック、レナード（ 1976年4月22日）。キューイングシステム：第II巻 – コンピュータ応用。ニューヨーク：ワイリー・インターサイエンス。576ページ。ISBN  978-0-471-49111-8。
• Lazowska, Edward D.; John Zahorjan; G. Scott Graham; Kenneth C. Sevcik (1984). Quantitative System Performance: Computer System Analysis Using Queueing Network Models . Prentice-Hall, Inc. ISBN 978-0-13-746975-8。
• ジョン・クラインバーグ。エヴァ・タルドス（2013年6月30日）。アルゴリズム設計。ピアソン。ISBN 978-1-292-02394-6。

• Teknomoの待ち行列理論チュートリアルと計算ツール
• Virtamoの待ち行列理論コース
• マイロン・フリンカの待ち行列理論ページ
• LINE：キューイングモデルを解くための汎用エンジン