Try   HackMD

Queueing Theory - Chapter 1 Introduction

contributed by <kaeteyaruyo>

1.1 Measures of System Performance

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Figure 1.1 一個 queueing system

  • 一個排隊系統 (queueing system) 如 Figure 1.1 所示,使用者從入口進去,進入隊伍 (queue) 排隊,等到有服務員 (server) 空閒時就可以被服務,被服務完之後就會從出口離開隊伍
  • 如果一個排隊系統有很多個 server,則可以根據他們的排列的方式分成平行的 server(每個 server 的功能都一樣)和序列的 server(要被一個 server 服務完才能進下一個)兩種。如果沒有特別講都是指平行的那種
  • 使用者有時候會有不耐煩的排隊行為 (impatient behavior)
    • Balking: 沒有進入口就離開了(沒有進入系統)
    • Reneging: 從隊伍中離開(已經進入系統)
  • 我們常用以下幾個指標來評估一個排隊系統的效能
    • 等待時間
      • Waiting time (=
        t1t0
        )
      • System time (=
        t2t0
        )
      • 上面這兩者的平均和機率分佈
    • 在系統 / 隊伍中的顧客人數
      • 一樣可以算平均跟機率分佈
    • 工作狀況
      • Idle time: 沒有顧客在系統 / server 中的時間長
      • Busy period: 有顧客在系統 / server 中的時間長
      • 上面這兩者的平均和機率分佈

1.2 Characteristics of Queueing Systems

  • 每次都要畫圖說明一個排隊系統很麻煩,我們只要可以清楚說明一個排隊系統的幾個關鍵特色,其實別人就可以理解我們腦中想的排隊系統長怎樣了。這些特色包含
    • 顧客抵達的 pattern
    • server 服務顧客的 pattern
    • server 的數量
    • 系統的容量
    • 排隊的準則(誰排前面誰排後面)
    • 如果是序列型的 server 的話,要額外描述 number of service stage(server 有幾關)

1.2.1 Arrival Pattern of Customers

  • interarrival times 的機率分佈
  • 有時候一次的 arrival 會帶來很多個顧客,這種狀況叫作 Bulk arrival 或是 Batch arrival
    • 此時我們會看到來顧客數量的機率分佈
    • 也會看 batches 之間的 interarrival time 的機率分佈
  • 是否允許不耐煩的排隊行為
    • Balking, reneging and jockeying(有多個隊伍的時候換隊伍)
  • Arrival pattern 是否會隨時間而改變
    • 如果不會,稱作 stationary arrival pattern
    • 如果會,則稱作 nonstationary arrival pattern

1.2.2 Service Patterns

  • service times 的機率分佈
  • 如果一個 server 一次可以服務好多個顧客,那稱作 batch service
  • 服務速率是否會跟當下系統的狀態有關
  • Service pattern 是否會隨時間而改變
    • 同樣分做 stationary 和 nonstationary

1.2.3 Number of Services

  • 一個 server
  • 很多個 server
    • 整個系統只有一個隊伍
    • 每個 server 前都有一個隊伍(只有這種狀況才會發生 jockeying)

1.2.4 Queue Discipline

  • 指的是 server 用什麼標準決定下一個要服務哪個顧客
  • 常見的 queue discipline
    • First come first serve (FCFS):先來先服務
    • First come last serve (FCLS):先來後服務
    • Random selection for service (RSS):隨機挑選
    • Priority schemes:優先度高的先服務
      • Preemptive: 服務可以被中斷,先切去優先度更高的
      • Nonpreemptive: 服務不能被中斷

1.2.5 System Capacity

  • 有些系統的隊伍只有有限的空間(等待區的位子有限),這種系統稱作 finite queueing
  • 當下一個顧客來到系統的時候,等待區已經滿了,那這個顧客就會被迫 balking (例如:路由器的 buffer 滿的時候會掉包)

1.2.6 Stages of Service

  • 有些系統會有很多個關卡 (stage of service)。例如:醫院的健康檢查。顧客必須先在某個 server 被服務,結束後再去下一個 server,直到所有關卡都完成後才能離開系統
  • 有些有多個關卡的系統會有重新回到前面關卡的情況,如下圖所示。例如:工廠的產品在進入品管關卡時如果沒有過關,可能會被送回前面的流程重新製作
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

    Figure 1.3 Multistage queueing system with feedback.

1.2.7 Notation

  • 我們通常使用
    A/B/X/Y/Z
    這樣的格式來簡單表達一個排隊系統的上述特色。這種表記法叫作 5 tuples notation
  • A
    : Interarrival-time distribution
  • B
    : Service-time distribution
  • X
    : Parallel servers (的個數)
    • 可能的值:
      1,2,...,
  • Y
    : System capacity,不一定要描述
    • 可能的值:
      1,2,...,
    • 預設是
  • Z
    : Queue discipline,不一定要描述
    • 可能的值
      • FCFS: 先到先服務,沒特別講就是這個
      • LCFS: 後到先服務
      • RSS: 隨機選擇下一個客戶
      • PR: Priority
      • GD: 沒有特定的選擇規則
  • A
    ,
    B
    ,
    X
    必須描述,
    Y
    ,
    Z
    則有預設值。例如:
    M/M/1
    ,就是
    A
    M
    B
    M
    X
    1
    的意思

Phase type distribution

  • 基本上就是有
    1,...,k
    個 state (又叫作 phase)的馬可夫鍊,然後有一個描述狀態間轉移機率的轉移矩陣
    P
    • P
      的長相如下,其中
      pi,j
      的意思是「轉移一次後從 state
      i
      跑到 state
      j
      的機率」
      [p1,1p1,kpk,1pk,k]
    • P
      描述的機率轉移
      n
      次,就相當於轉移了
      Pn
      次,矩陣的長相如下,其中
      pi,jn
      的意思是「轉移
      n
      次後從 state
      i
      跑到 state
      j
      的機率」
      [p1,1(n)p1,k(n)pk,1(n)pk,k(n)]
    • P
      必須是一個 transient,也就是當
      n
      時,
      Pn0
  • 在單一個 state
    i
    裏面待的時間必須要呈 exponential distribution with parameter
    1μi
  • 舉例
    • Coxian distribution
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More →
    • Mixed Erlang distribution
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More →

1.3 The Experience of Waiting

  • Unoccupied time 感覺上比 occupied time 還要久
    • Unoccupied time:等的時候沒事情做
    • Occupied time:等的時候有事情做
  • Pre-process wait 感覺上比 in-process wait 還要久
    • Pre-process wait:還沒被服務,在店門口外面等
    • In-process wait:服務到一半,在等下一個服務步驟
  • 焦慮會讓等待時間感覺更長
  • 不確定要等多久感覺上比知道要等多久(有限等待時間)還要久
  • 沒有人來說明要等多久,感覺上比有人來說明要等多久還要久
  • 不公平的排隊感覺上比公平的排隊還要久
    • 但如果服務品質更好/更有價值,那等更久就還可以忍受
  • 一個人等感覺上比一群人一起等還要久

1.4 Little's Law

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  • Little's Law 提供以下三個排隊系統中常見的基本物理量之間的等式關係:
    L=λW
    • λ
      : 顧客抵達系統的平均抵達率
    • W
      : 每個顧客待在系統中的平均時間
    • L
      : 長期來看系統當中的平均人數
  • 有了 Little's Law, 我們只要知道這三個物理量中的其中兩個,就可以算出第三個
    • 例如:我們可以站在一間店的門口數出來的人數,然後問問每個出來的人他們在裏面待了多久,有以上兩者對時間的平均,我們就可以大概推估出這間店當中的平均人數
  • Example 1.1
    • 有一間小學,每年都有 30 個人入學,每個學生讀滿六年後就會離開
    • 在這個系統中,
      λ=30
      W=6
      。 根據 Little's Law,這個學校平均每年會有
      30×6=180
      人就讀
    • 這例子聽起來很顯而易見,用膝蓋想也知道每年有 30 人入學、總共有六個年級的學校當然是總共 180 個學生。但是如果今天系統的參數不是這麼穩定,那人數的估計就不是那麼簡單,例如:
      • 如果有學生在唸到一半時轉入 / 轉出呢?
      • 如果有學生跳級或留級呢?
      • 如果每年的入學人數其實是隨機變化的呢?
      • 如果入學人數是逐年增加的呢?
  • 我們需要更精確的用數學語言定義 Little's Law 當中的物理量,才可以清楚的描述這些問題
    • 考慮一個會有顧客抵達和離開的系統,如上圖 Figure 1.4 ,令
      • A(k)
        :第
        k
        個顧客進入系統的時間點,照大小順序排好,使得
        A(k+1)A(k)
      • A(t)
        到時間點
        t
        為止
        累積的進入系統的人數
      • W(k)
        :第
        k
        個顧客在系統中待的時長。顧客不可能在抵達前就離開,所以
        W(k)0
      • N(t)
        在時間點
        t
        的當下
        系統中的人數。也就是符合
        A(k)tA(k)+W(k)t
        k
        的數量
    • 則上述三個物理量可以用以下極限值來定義
      (1.1)λlimtA(t)t,Wlimk1ki=1kW(k),LlimT1T0TN(t)dt.
    • 在此定義下,
      λ
      是長期下來的 (long-run) 平均顧客抵達率、
      W
      是長期下來的平均系統時間、
      L
      是長期下來的平均系統人數

Theorem 1.1 [Little’s law] If the limits

λ and
W
in
(1.1)
exist and are finite, then the limit
L
exists and
L=λW.

  • Theorem 1.1 在討論的是一個長期平均 (long-run averages) 的關係。也就是說,在
    (1.1)
    中這三個物理量都是以趨近無限大的極限值來定義的
  • 因為這些物理量是以極限值來定義,所以他們的極限值必須要先存在,這條式子才會有意義,這樣的定義幫我們排除掉了那些等待時間會無限增長的系統。換句話說,我們討論的排隊系統必須是一個有進有出的系統 (Conservative System),才能夠使用 Little's Law
  • 基於這樣的定義,其實 Theorem 1.1 技術上來說並不是只能用在一個「排隊」系統上,只要是一個「會有人進出」的系統就可以了。系統中間可以當作是一個黑盒子,不管 arrival pattern 和 service pattern 到底是什麼挖割分佈、是先進先服務還是隨便抽人來服務,Little's Law 通通都不在意。只要上述的極限值存在、顧客的抵達時間一定小於離開時間,就可以使用 Little's Law 了

  • 基於不同的「系統」定義, Little’s Law 可能會導出稍微長得不太一樣的關係式。下列幾個範例會讓我們看到, Little’s Law 其實比較像是一個法則,而不是一條確定的式子。更準確的說,當我們關注的「系統」不一樣的時候,
    λ
    ,
    W
    L
    可能會分別指稱到不同的對象
  • Example 1.2
    • Figure 1.5 描述了一個完整的排隊系統。在這樣的觀點下,
      L
      指的是整個排隊系統中的人數(隊伍中的人數 + 正在被服務的人數);
      W
      指的是顧客在整個系統當中所花的時間(排隊的時間 + 被服務的時間)。而這兩者之間的關係是
      L=λW
    • 雖然上圖中只有畫出一個 server 跟一個 queue,但其實上述的等式關係在多個 server 或是多個 queue 的情況下也會成立
  • Example 1.3
    • Figure 1.6 中描述的「系統」是整個排隊系統中的隊伍的部份。在這樣的觀點下,
      Lq
      指的是隊伍中的人數;
      Wq
      指的是顧客排隊所花的時間。此時隊伍的抵達率跟整個系統的抵達率是一樣的(都是
      λ
      )。而這三者之間的關係是
      Lq=λWq
  • Example 1.4
    • Figure 1.7 中描述的「系統」是一個只有一個 server 的排隊系統中,那個 single server 的部份。在這樣的觀點下,
      • 這 server 中要嘛就有一個人,要嘛就沒有人。如果令
        p0
        為 server 停擺的時間比例,則長期平均下來隊伍中的人數
        L=0p0+1(1p0)=1p0
      • S
        代表顧客服務時間的隨機變數,則長期平均下來顧客待在 server 中的時間就會是
        S
        的期望值,也就是
        W=E[S]
      • 假設離開這個 server 的離開率跟抵達率差不多,那 server 的抵達率就會是整個排隊系統的抵達率
        λ
      • 因此,整個 Little's Law 就可以改寫為
        L=λW1p0=λE[S]
    • 用這條式子來計算一個排隊系統的效能是很方便的,因為他不依靠任何對於排隊系統的假設(像是服務模式是泊松分佈、先到先服務之類的),只要是 single server 就可以用了
  • Example 1.5

1.4.1 Geometric Illustration of Little’s Law

  • A(t)
    : 到時間點
    t
    為止累積的抵達人數,上圖的粗實線
  • D(t)
    : 到時間點
    t
    為止累積的離開系統人數,上圖的點狀虛線
  • 每一個圍出來的矩型分別代表每一個顧客的系統時間
    • 0T(A(t)D(t))dt
      = 矩型面積總和 =
      k=1NW(k)

      1T0T(A(t)D(t))dt=NT(1Nk=1NW(k))
      • 等號左邊代表平均系統長度
        L
      • NT=λ
      • 等號右邊的大括號內部代表平均系統時間
        W

1.5 General Results

  • Summary of notation
    • 注意
      ρ
      r
      的差異=

1.6 Simple Bookkeeping for Queues

  • 系統假設
    • 是個先來先服務 (FCFS) 的系統
    • 只有一個服務器 (single server)
  • 用到的變數
    • A(n)
      : 第
      n
      個客戶的抵達時間 (arrival time)
    • S(n)
      : 第
      n
      個客戶被服務的時長 (service time)
    • T(n)
      : 第
      n
      個客戶和第
      n+1
      個客戶抵達的時間差 (interarrival time)
    • U(n)
      : 第
      n
      個客戶開始被服務的時間 (time starts service)
    • D(n)
      : 第
      n
      個客戶的離開時間 (departure time)
    • Wq(n)
      : 第
      n
      個客戶在隊伍裡的時間長 (time in queue / waiting time)
    • W(n)
      : 第
      n
      個客戶在系統裡的時間長 (time in system / system time)
  • 這些變數的關係
    • T(n)=A(n+1)A(n)
    • U(n+1)=max{D(n),A(n+1)}
      (重要,第
      n+1
      個客戶會在第
      n
      個客戶離開時開始被服務,前題是當時第
      n+1
      個客戶已經在系統中)
    • D(n)=U(n)+S(n)
    • Wq(n)=U(n)A(n)
    • W(n)=Wqn+S(n)
  • 示意圖
    • 第一種狀況
      • T(n)+Wq(n+1)=Wq(n)+S(n)Wq(n+1)=Wq(n)+S(n)T(n)
      • 下一個人要等多久,可以透過上一個人等多久以及被服務多久算出來
    • 第二種狀況
      • Wq(n+1)=0
      • 有時候客戶抵達時系統是空的,那就不用等
    • 綜合兩種狀況,等待時間長可以用以下算式 (Lindley’s equation) 計算
      Wq(n+1)=max{Wq(n)+S(n)T(n),0}