タクシー乗り場モデル

提供: ORWiki
2008年8月5日 (火) 15:50時点におけるSakasegawa (トーク | 投稿記録)による版
ナビゲーションに移動 検索に移動

【たくしーのりばもでる (taxi stand model)】

説明1: タクシー乗り場で, 乗客の到着と空のタクシーの到着があり, タクシーを待つ乗客の待ち行列と, 乗客を待つタクシーの待ち行列がそれぞれできるような待ち行列システム. 1つの場所から2つの待ち行列ができるため, 双端待ち行列(double ended queues)ともいわれる. 少なくともどちらかの行列ができているときに一方の到着があればサービスが行われ, 乗客とタクシーがそれぞれ1つずつ減少する.

説明2: 客がサーバの待つサービス窓口にランダムに到着する通常の待ち行列モデルに対して、サーバがサービス窓口に常駐せず、サーバもランダムに到着するとしたモデル。客は、到着したときに(客待ち)サーバがいなければ客の待ち行列の最後に並び、さもなければ、直ちにサービスを受け、サービスが終了すると、サービスを受けていたサーバと一緒にシステムを退去する。サーバは、到着したときに(サーバ待ち)客がいなければサーバ用の待ち行列の最後に並び、さもなければ、先頭の客に対してサービスを行い、サービス終了と同時に、その客と一緒にシステムを退去する、という動きを繰り返す。

タクシーをサーバ、タクシーの利用者を客と考えると、タクシー乗り場のタクシー待ち客の行列と客待ちタクシーの行列の動きの単純なモデル化になっているので、タクシー乗り場モデルという名前が付いた。

二通りの待ち行列を想定するので、双端型待ち行列モデル(double-ended queue)とも呼ばれ、あるいは、サーバの動きに注目して移動サーバモデルとも呼ばれる。

最初のモデルは、サービス時間が0を仮定している。その場合は、少なくともどちらか一方の待ち行列は空になっている。