日常生活中存在大量有形和無形的排隊(duì)或擁擠現(xiàn)象，如旅客購票排隊(duì)，市內(nèi)電話占線等現(xiàn)象。排隊(duì)論的基本思想是1910年丹麥電話工程師A.K.埃爾朗在解決自動(dòng)電話設(shè)計(jì)問題時(shí)開始形成的，當(dāng)時(shí)稱為話務(wù)理論。他在熱力學(xué)統(tǒng)計(jì)平衡理論的啟發(fā)下，成功地建立了電話統(tǒng)計(jì)平衡模型，并由此得到一組遞推狀態(tài)方程，從而導(dǎo)出著名的埃爾朗電話損失率公式。
自20世紀(jì)初以來，電話系統(tǒng)的設(shè)計(jì)一直在應(yīng)用這個(gè)公式。30年代蘇聯(lián)數(shù)學(xué)家А.Я.欣欽把處于統(tǒng)計(jì)平衡的電話呼叫流稱為最簡單流。瑞典數(shù)學(xué)家巴爾姆又引入有限后效流等概念和定義。他們用數(shù)學(xué)方法深入地分析了電話呼叫的本征特性，促進(jìn)了排隊(duì)論的研究。50年代初，美國數(shù)學(xué)家關(guān)于生滅過程的研究、英國數(shù)學(xué)家D.G.肯德爾提出嵌入馬爾可夫鏈理論，以及對(duì)排隊(duì)隊(duì)型的分類方法，為排隊(duì)論奠定了理論基礎(chǔ)。在這以后，L.塔卡奇等人又將組合方法引進(jìn)排隊(duì)論，使它更能適應(yīng)各種類型的排隊(duì)問題。70年代以來，人們開始研究排隊(duì)網(wǎng)絡(luò)和復(fù)雜排隊(duì)問題的漸近解等，成為研究現(xiàn)代排隊(duì)論的新趨勢(shì)。
排隊(duì)系統(tǒng)又稱服務(wù)系統(tǒng)。服務(wù)系統(tǒng)由服務(wù)機(jī)構(gòu)和服務(wù)對(duì)象（顧客）構(gòu)成。服務(wù)對(duì)象到來的時(shí)刻和對(duì)他服務(wù)的時(shí)間（即占用服務(wù)系統(tǒng)的時(shí)間）都是隨機(jī)的。圖1為一最簡單的排隊(duì)系統(tǒng)模型。排隊(duì)系統(tǒng)包括三個(gè)組成部分：輸入過程、排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)。
輸入過程
輸入過程考察的是顧客到達(dá)服務(wù)系統(tǒng)的規(guī)律。它可以用一定時(shí)間內(nèi)顧客到達(dá)數(shù)或前后兩個(gè)顧客相繼到達(dá)的間隔時(shí)間來描述，一般分為確定型和隨機(jī)型兩種。例如，在生產(chǎn)線上加工的零件按規(guī)定的間隔時(shí)間依次到達(dá)加工地點(diǎn)，定期運(yùn)行的班車、班機(jī)等都屬于確定型輸入。隨機(jī)型的輸入是指在時(shí)間t內(nèi)顧客到達(dá)數(shù) n（t）服從一定的隨機(jī)分布。如服從泊松分布,則在時(shí)間t內(nèi)到達(dá)n個(gè)顧客的概率為
或相繼到達(dá)的顧客的間隔時(shí)間T 服從負(fù)指數(shù)分布，即
式中λ為單位時(shí)間顧客期望到達(dá)數(shù)，稱為平均到達(dá)率；1/λ為平均間隔時(shí)間。在排隊(duì)論中，討論的輸入過程主要是隨機(jī)型的。
排隊(duì)規(guī)則
排隊(duì)規(guī)則分為等待制、損失制和混合制三種。當(dāng)顧客到達(dá)時(shí)，所有服務(wù)機(jī)構(gòu)都被占用，則顧客排隊(duì)等候，即為等待制。在等待制中，為顧客進(jìn)行服務(wù)的次序可以是先到先服務(wù)，或后到先服務(wù)，或是隨機(jī)服務(wù)和有優(yōu)先權(quán)服務(wù)（如醫(yī)院接待急救病人）。如果顧客來到后看到服務(wù)機(jī)構(gòu)沒有空閑立即離去，則為損失制。有些系統(tǒng)因留給顧客排隊(duì)等待的空間有限，因此超過所能容納人數(shù)的顧客必須離開系統(tǒng)，這種排隊(duì)規(guī)則就是混合制。
服務(wù)機(jī)構(gòu)
可以是一個(gè)或多個(gè)服務(wù)臺(tái)。多個(gè)服務(wù)臺(tái)可以是平行排列的，也可以是串連排列的。服務(wù)時(shí)間一般也分成確定型和隨機(jī)型兩種。例如，自動(dòng)沖洗汽車的裝置對(duì)每輛汽車沖洗（服務(wù)）時(shí)間是相同的，因而是確定型的。而隨機(jī)型服務(wù)時(shí)間v 則服從一定的隨機(jī)分布。如果服從負(fù)指數(shù)分布，則其分布函數(shù)是
式中μ為平均服務(wù)率，1/μ為平均服務(wù)時(shí)間。
如果按照排隊(duì)系統(tǒng)三個(gè)組成部分的特征的各種可能情形來分類，則排隊(duì)系統(tǒng)可分成無窮多種類型。因此只能按主要特征進(jìn)行分類。一般是以相繼顧客到達(dá)系統(tǒng)的間隔時(shí)間分布、服務(wù)時(shí)間的分布和服務(wù)臺(tái)數(shù)目為分類標(biāo)志�，F(xiàn)代常用的分類方法是英國數(shù)學(xué)家D.G.肯德爾提出的分類方法，即用肯德爾記號(hào) X/Y/Z進(jìn)行分類。
X處填寫相繼到達(dá)間隔時(shí)間的分布；
Y處填寫服務(wù)時(shí)間分布;
Z處填寫并列的服務(wù)臺(tái)數(shù)目。
各種分布符號(hào)有：M-負(fù)指數(shù)分布;D-確定型; Ek-k階埃爾朗分布；GI-一般相互獨(dú)立分布；G-一般隨機(jī)分布等。這里k階埃爾朗分布是指
為相互獨(dú)立且服從相同指數(shù)分布的隨機(jī)變量時(shí)，
服從自由度為 2k的χ2分布。例如,M/M/1表示顧客相繼到達(dá)的間隔時(shí)間為負(fù)指數(shù)分布、服務(wù)時(shí)間為負(fù)指數(shù)分布和單個(gè)服務(wù)臺(tái)的模型。D/M/C表示顧客按確定的間隔時(shí)間到達(dá)、服務(wù)時(shí)間為負(fù)指數(shù)分布和C個(gè)服務(wù)臺(tái)的模型。至于其他一些特征,如顧客為無限源或有限源等，可在基本分類的基礎(chǔ)上另加說明。
研究排隊(duì)系統(tǒng)問題的主要目的是研究其運(yùn)行效率,考核服務(wù)質(zhì)量,以便據(jù)此提出改進(jìn)措施。通常評(píng)價(jià)排隊(duì)系統(tǒng)優(yōu)劣有 6項(xiàng)數(shù)量指標(biāo)。
�、傧到y(tǒng)負(fù)荷水平ρ ：它是衡量服務(wù)臺(tái)在承擔(dān)服務(wù)和滿足需要方面能力的尺度；
�、谙到y(tǒng)空閑概率P0：系統(tǒng)處于沒有顧客來到要求服務(wù)的概率；
③隊(duì)長：系統(tǒng)中排隊(duì)等待服務(wù)和正在服務(wù)的顧客總數(shù)，其平均值記為LS；
�、荜�(duì)列長：系統(tǒng)中排隊(duì)等待服務(wù)的顧客數(shù)，其平均值記為Lg；
�、荻毫魰r(shí)間：一個(gè)顧客在系統(tǒng)中停留時(shí)間，包括等待時(shí)間和服務(wù)時(shí)間，其平均值記為WS；
⑥等待時(shí)間：一個(gè)顧客在系統(tǒng)中排隊(duì)等待時(shí)間,其平均值記為Wg。M/M/1排隊(duì)系統(tǒng)是一種最簡單的排隊(duì)系統(tǒng)。系統(tǒng)的各項(xiàng)指標(biāo)可由圖2中狀態(tài)轉(zhuǎn)移速度圖推算出來（表1）。其他類型的排隊(duì)系統(tǒng)的各種指標(biāo)計(jì)算公式則復(fù)雜得多，可專門列出計(jì)算公式圖表備查�，F(xiàn)已開始應(yīng)用計(jì)算機(jī)仿真來求解排隊(duì)系統(tǒng)問題。
排隊(duì)論已廣泛應(yīng)用于交通系統(tǒng)、港口泊位設(shè)計(jì)、機(jī)器維修、庫存控制和其他服務(wù)系統(tǒng)。表2中列出排隊(duì)論的應(yīng)用。
