1台のネットワーク・プリンタに複数の要求が並んで順番を待っています。このとき，要求を送信してから印刷が完了するまでの時間は「（プリンタが使用可能になるのを）待っている時間」，「プリンタを使用している時間」，「その他の時間（通信時間など）」の合計になります。ここで待っている時間と，使用している時間，および要求が到着する間隔に着目して，これらの関係を理論式で推測していくのが待ち行列問題です。
今回は最も基本的なＭ／Ｍ／１のモデルを見てみることにしましょう。Ｍ／Ｍ／１というのはケンドールの記法で表記された待ち行列のモデルで，以下の三つの条件が成り立っている状態を指します。
(1)サービス要求の到着間隔がランダム（ポアゾン分布に従う）
(2)窓口を使用する時間は要求ごとにランダム（指数分布に従う）
(3)待ち行列のサービス窓口は1個
 |
| 図1●Ｍ／Ｍ／１の待ち行列モデル |
また，窓口数の後ろに行列の長さの制限を記入する場合もありますが，省略されているときは制限がないということになります。
ほかにケンドールの記法で待ち行列を考える場合の約束としては，次のものがあります。
●行列へ割り込んだり，列の途中で抜け出すことは考えない
●サービス要求は到着順に受け付ける
利用率と到着率とサービス率
利用率をρ（ロー），到着率をλ（ラムダ），サービス率をμ（ミュー）とした場合，次の式が成り立ちます。
 |
| 図2●利用率，到着率，サービス率 |
到着率は単位時間当たりに到着するサービス要求の数，サービス率は単位時間当たりにサーバーが処理できる要求数です。
式を利用するときは，それぞれの単位時間を統一します。例えば，単位時間を1時間にした場合で，到着するサービス要求が12件，サーバーが処理できる要求数が20件だった場合の利用率は，12÷20＝0.6ということになります。
Ｍ／Ｍ／１の公式
Ｍ／Ｍ／１の待ち行列において，待ち時間をTw，平均サービス時間をTsとしたとき，次の式が成り立ちます。
 |
| 図3●Ｍ／Ｍ／１の公式 |
利用率が0.6で平均サービス時間が3分の場合，上記の式に当てはめると，
0.6÷（1－0.6）×3（分）＝4.5（分）
となります。
このＭ／Ｍ／１モデルは，公式を使用して比較的簡単に待ち時間を求めることができるため，多くの試験で出題されています。
|
