応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

待ち行列(M/M/1)

 

1.待ち行列とは

 銀行の窓口やスーパーのレジなど、処理の順番を待つための行列ができることがあります。このときの、平均待ち時間を計算するのが待ち行列の理論です。待ち行列の計算は、窓口の要員数を決定することなどに活用されます。
 以下の図を見て下さい。銀行に一つの窓口があり、窓口でサービスを受けている人と、順番を待っている人がいます。窓口で口座開設などの手続きを受けたりするなどのサービスを受けます。この時間をサービス時間と言います。また、待っている時間を待ち時間、サービス時間と待ち時間を合わせて応答時間と言います。

f:id:mamori_yuto:20181028044125j:plain

2.待ち行列で覚えるべき公式

M/M/1の問題は難しいと思う人、簡単と思う人の両方がいるでしょう。ポアソン分布であったり、指数分布であったり難しい言葉が並びます。難しいと感じる人も多いと思います。
しかし、以下の公式を1つ覚えるだけで解けます。

【公式】
平均待ち時間=ρ÷(1-ρ)X T
・ρは窓口の利用率
・Tはサービス時間

今回、平均待ち時間=Tであるため
T=ρ÷(1-ρ)X T

これを解くと
ρ=0.5が導き出せます。
問題文を読み解くとという重要な力は必要ですが、内容そのものは単純な問題です。

3.【参考】M/M/1の説明

・M:単位時間に到着する客の数はポアソン分布に従う(つまりランダム)
・M:サービス時間は指数分布に従う(長いサービス時間になるほど量は減る)
・1:窓口は一つである。
※平成16年 問8参照

4.待ち行列の過去問

(1)H28春AP問3
問3 多数のクライアントが,LANに接続された1台のプリンタを共同利用するときの印刷要求から印刷完了までの所要時間を,待ち行列理論を適用して見積もる場合について考える。プリンタの運用方法や利用状況に関する記述のうち,M/M/1の待ち行列モデルの条件に反しないものはどれか。
ア 一部のクライアントは,プリンタの空き具合を見ながら印刷要求をする。
イ 印刷の緊急性や印刷量の多少にかかわらず,先着順に印刷する。
ウ 印刷待ち文書の総量がプリンタのバッファサイズを超えるときは,一時的に受付を中断する。
エ 一つの印刷要求から印刷完了までの所要時間は,印刷の準備に要する一定時間と,印刷量に比例する時間の合計である。




【正解】イ

(2)H27春
問1 ATM(現金自動預払機)が1台ずつ設置してある二つの支店を統合し,統合後の支店にはATMを1台設置する。統合後のATMの平均待ち時間を求める式はどれか。ここで,待ち時間はM/M/1の待ち行列モデルに従い,平均待ち時間にはサービス時間を含まず,ATMを1台に統合しても十分に処理できるものとする。
〔条件〕
(1)統合後の平均サービス時間:Ts
(2)統合前のATMの利用率:両支店ともρ
(3)統合後の利用者数:統合前の両支店の利用者数の合計
H27h-1


【正解】エ

(3)H26秋AP問3
問3 コンピュータによる伝票処理システムがある。このシステムは,伝票データをためる待ち行列をもち, M/M/1の待ち行列モデルが適用できるものとする。平均待ち時間がT秒以上となるのは,処理装置の利用率が少なくとも何%以上となったときか。ここで,伝票データをためる待ち行列の特徴は次のとおりである。
  ・伝票データは,ポアソン分布に従って発生する。
  ・伝票データのたまる数に制限はない。
  ・1件の伝票データの処理時間は,平均T秒の指数分布に従う。
ア 33   イ 50   ウ 67   エ 80


【正解】イ

(4)H25秋AP問5
問5 通信回線を使用したデータ伝送システムにM/M/1の待ち行列モデルを適用すると,平均回線待ち時間,平均伝送時間,回線利用率の関係は,次の式で表すことができる。
h25a-5
 回線利用率が0%から徐々に上がっていく場合,平均回線待ち時間が平均伝送時間よりも最初に長くなるのは,回線利用率が何%を超えたときか。
ア 40   イ 50   ウ 60   エ 70




【正解】イ

(5)H20問秋AD午前問13
問13 待ち行列モデルの適用事例として,適切なものはどれか。
ア 1回当たりの発注コスト, 1個当たりの在庫維持コストなどを基に,在庫商品の発注量を決定する。
イ 過去何年か分の売上データを時系列に並べ,推移状況を比較することによって,次年度の売上を予測する。
ウ 画像情報の密度,大きさ,平均圧縮率,通信速度などを基に,必要な通信時間を計算する。
エ 電話の平均受付回数,平均対応時間などを基に,問合せに対応するサービスデスクの要員数を決定する。



正解は、エです。