站線

[拼音]：paiduilun

[英文]：queuing theory

研究系統隨機聚散現象和隨機服務系統工作過程的數學理論和方法，又稱隨機服務系統理論，為運籌學的一個分支。

發展簡史

日常生活中存在大量有形和無形的排隊或擁擠現象，如旅客購票排隊，市內電話佔線等現象。排隊論的基本思想是1910年丹麥電話工程師A.K.埃爾朗在解決自動電話設計問題時開始形成的，當時稱為話務理論。他在熱力學統計平衡理論的啟發下，成功地建立了電話統計平衡模型，並由此得到一組遞推狀態方程，從而匯出著名的埃爾朗電話損失率公式。自20世紀初以來，電話系統的設計一直在應用這個公式。30年代蘇聯數學家А.Я.欣欽把處於統計平衡的電話呼叫流稱為最簡單流。瑞典數學家巴爾姆又引入有限後效流等概念和定義。他們用數學方法深入地分析了電話呼叫的本徵特性，促進了排隊論的研究。50年代初，美國數學家關於生滅過程的研究、英國數學家D.G.肯德爾提出嵌入馬爾可夫鏈理論，以及對排隊隊型的分類方法，為排隊論奠定了理論基礎。在這以後，L.塔卡奇等人又將組合方法引進排隊論，使它更能適應各種型別的排隊問題。70年代以來，人們開始研究排隊網路和複雜排隊問題的漸近解等，成為研究現代排隊論的新趨勢。

排隊系統模型

排隊系統又稱服務系統。服務系統由服務機構和服務物件（顧客）構成。服務物件到來的時刻和對他服務的時間（即佔用服務系統的時間）都是隨機的。圖1為一最簡單的排隊系統模型。排隊系統包括三個組成部分：輸入過程、排隊規則和服務機構。

輸入過程

輸入過程考察的是顧客到達服務系統的規律。它可以用一定時間內顧客到達數或前後兩個顧客相繼到達的間隔時間來描述，一般分為確定型和隨機型兩種。例如，在生產線上加工的零件按規定的間隔時間依次到達加工地點，定期執行的班車、班機等都屬於確定型輸入。隨機型的輸入是指在時間t內顧客到達數 n（t）服從一定的隨機分佈。如服從泊松分佈,則在時間t內到達n個顧客的概率為

或相繼到達的顧客的間隔時間T 服從負指數分佈，即

式中λ 為單位時間顧客期望到達數，稱為平均到達率；1/λ 為平均間隔時間。在排隊論中，討論的輸入過程主要是隨機型的。

排隊規則

分為等待制、損失制和混合制三種。當顧客到達時，所有服務機構都被佔用，則顧客排隊等候，即為等待制。在等待制中，為顧客進行服務的次序可以是先到先服務，或後到先服務，或是隨機服務和有優先權服務（如醫院接待急救病人）。如果顧客來到後看到服務機構沒有空閒立即離去，則為損失制。有些系統因留給顧客排隊等待的空間有限，因此超過所能容納人數的顧客必須離開系統，這種排隊規則就是混合制。

服務機構

可以是一個或多個服務檯。多個服務檯可以是平行排列的，也可以是串連排列的。服務時間一般也分成確定型和隨機型兩種。例如，自動沖洗汽車的裝置對每輛汽車沖洗（服務）時間是相同的，因而是確定型的。而隨機型服務時間v 則服從一定的隨機分佈。如果服從負指數分佈，則其分佈函式是

式中μ 為平均服務率，1/μ 為平均服務時間。

排隊系統的分類

如果按照排隊系統三個組成部分的特徵的各種可能情形來分類，則排隊系統可分成無窮多種型別。因此只能按主要特徵進行分類。一般是以相繼顧客到達系統的間隔時間分佈、服務時間的分佈和服務檯數目為分類標誌。現代常用的分類方法是英國數學家D.G.肯德爾提出的分類方法，即用肯德爾記號 X/Y/Z進行分類。X處填寫相繼到達間隔時間的分佈；Y處填寫服務時間分佈;Z處填寫並列的服務檯數目。各種分佈符號有：M-負指數分佈;D-確定型;Ek-k階埃爾朗分佈；GI-一般相互獨立分佈；G-一般隨機分佈等。這裡k階埃爾朗分佈是指