排隊系統(tǒng)的基本構成

排隊論排隊論(queuingtheory)是一門應用十分廣泛的運籌學分支，它在各種存在等待情形的環(huán)境中都有非常成功的應用。盡管人們有時可能并不太在意等待時間的長短，但在許多商務活動中我們必須給顧客的等待時間以充分的重視。絕大多數(shù)大型零售店的設計其實就是平衡顧客方便度和企業(yè)運營效率的產(chǎn)物，這很好地解釋了為什么一個超級市場可能會有十幾個收銀通道，盡管在大多數(shù)時間里可能只有兩三個在運作。零售商不敢讓顧客在隊伍中等待太長的時間，因為時間對顧客來說可能是十分寶貴的，如果等待時間過長，他們完全有可能轉向自己的競爭者。在管理科學或運籌學中，等待的隊伍被稱為隊列(queue),排隊論作為運籌學的一個重要分支在過去的幾十年里得到了長足的發(fā)展，代表特定環(huán)境的模型的數(shù)量穩(wěn)步增加。作為最早的定量優(yōu)化方法之一，排隊論的起源可以追溯到1909年愛爾朗(A.K.Erlang,aDanishtelephoneengineer)發(fā)表的一篇論文，從那時起愛爾朗的名字就與概率排隊模型緊密聯(lián)系了在一起，該論文的發(fā)表為后來排隊論的發(fā)展奠定了堅實的基礎。排隊模型的目的就是要規(guī)劃一種為顧客提供服務的方式以實現(xiàn)一定的運營效率，它并不象前面已經(jīng)遇到的一些模型(如線性規(guī)劃模型、存貯模型)那樣追逐一個最小成本或最大收益目標。具體來講，排隊模型的目的就是要確定排隊系統(tǒng)的各項特征，如平均等待時間、平均隊長等；或者是構建一個服務系統(tǒng)以滿足特定的顧客服務水平。這些平均值是系統(tǒng)對顧客服務水平的標志，在后續(xù)的成本分析中將發(fā)揮重要的作用?！?排隊系統(tǒng)綜述在日常生活和生產(chǎn)中，人們會經(jīng)常碰到各種各樣的排隊系統(tǒng)，如道路紅綠燈系統(tǒng)、超市的收銀系統(tǒng)、電話通訊系統(tǒng)等。一些排隊系統(tǒng)的構成十分明顯，而另一些排隊系統(tǒng)的構成可能很模糊。如從廣州往北京打電話，由于受廣州與北京之間信道通過能力的限制，同一時間通話的人數(shù)是有限的；因此，當要求通話人數(shù)超過這一限制時，就不得不等待，雖然打電話的人分散在全市的各個角落，彼此互不見面，但他們與長話臺一起構成一個服務系統(tǒng)，他們在長話臺前形成一個無形的隊伍，其實這種無形的隊伍與超市收銀系統(tǒng)中的有形隊伍都可以構成排隊系統(tǒng)中的隊列。在排隊系統(tǒng)中總是存在一組服務設施(servicefacility)，有許多顧客(customer)隨機地來到該系統(tǒng)要求得到服務，服務完畢后即自動離去。如果顧客到達時有服務設施空閑，則到達的顧客即刻得到服務，否則顧客將排隊等待或離去。通常我們會自然地認為顧客就是來到服務系統(tǒng)準備接受服務的人，然而在排隊系統(tǒng)中顧客不該受到任何限制，可以是人，也可以是物。汽車修理廠等待維修的汽車、機場等待降落的飛機都可以構成排隊系統(tǒng)中的顧客。在排隊系統(tǒng)中，服務設施同樣可以是人、物或者人和物的集合。如果顧客按固定的時間間隔到達服務系統(tǒng)，服務設施用在每個顧客身上的服務時間也是固定的，就象工廠流水線的生產(chǎn)那樣有固定的節(jié)拍，那么這類服務系統(tǒng)的設計是十分簡便的。但在絕大多數(shù)的服務系統(tǒng)中，顧客的到達是隨機的，顧客的服務時間也是隨機的，這就意味著排隊論有著廣泛的應用前景。排隊系統(tǒng)的基本構成一個排隊系統(tǒng)由輸入、隊列、服務臺和輸出四部分構成，可以用圖10-1來加以描述。圖10-1排隊系統(tǒng)構成示意圖1．輸入輸入描述的是顧客出現(xiàn)在排隊系統(tǒng)中的方式，人們通常用某種帶有任意參數(shù)和適當簡化假設的隨機過程來表示它。輸入過程又由如下一些元素構成：（1）顧客總體顧客總體可以是一個有限的集合，也可以是一個無限的集合；但只要顧客總體所包含的元素數(shù)量充分大，就可以把顧客總體有限的情況近似看成是顧客總體無限的情況來處理。上游河水流入水庫可以認為顧客總體是無限的，而工廠里等待修理的機器設備顯然是有限的顧客總體。（2）顧客到達的時點雖然顧客的到達可能是單個發(fā)生的，也可以是成批發(fā)生的，但在排隊系統(tǒng)中總是假設在同一時點上只能有一個顧客到達，同時到達的一批顧客只能看成是一個顧客。（3）顧客到達的相關性顧客到達可以是相互獨立的，也可以是相關聯(lián)的。所謂獨立即先前顧客的到達對后續(xù)顧客的到達沒有影響，否則就是相關的。（4）顧客到達的時間間隔顧客到達的時間間隔可以是確定的，也可以是隨機的。如在流水線上裝配的各部件必須按確定的時間間隔到達裝配點，定點運行的列車、班機的到達也都是確定的；但商場購物的顧客、醫(yī)院診病的病人、通過路口的車輛的到達都是隨機的。對于隨機的情形，我們必須了解單位時間的顧客到達數(shù)或相繼到達的時間間隔的概率分布。（5）顧客到達的平穩(wěn)性平穩(wěn)性是指顧客到達的時間間隔分布及其特征參數(shù)（數(shù)學期望、方差等）不隨時間的變化而變化。最簡單的到達過程是符合泊松（Poisson）分布的隨機過程，在這種情況下，顧客到達的時間間隔是一系列相互獨立并具有負指數(shù)分布的隨機變量。2．隊列顧客到達時，如果所有服務臺都正在被占用，顧客可能選擇隨即離去或排隊等待。隨即離去的系統(tǒng)稱為即時制系統(tǒng)或損失制系統(tǒng)，排隊等待的系統(tǒng)稱為等待系統(tǒng)。普通電話的呼叫屬于損失制。系統(tǒng)如果有多個服務臺，各服務臺可以有各自獨立的隊列，也可以有一個公共的隊列。隊列可以是具體的也可以是抽象的，可以是有限的也可以是無限的。在實際排隊系統(tǒng)中，有時顧客會因等待時間過長而中途離去，或因某些隊列服務較快而更換隊列，但在排隊論中假設這些復雜情況不發(fā)生。3．服務臺一個排隊系統(tǒng)中可以有一個服務臺，也可以有多個服務臺。對于多服務臺來講，各服務臺可以串聯(lián)、并聯(lián)也可以混聯(lián)。（1）服務方式服務可針對單一顧客來進行，也可以針對一批顧客來進行。公共汽車對等候的顧客就是成批進行服務的。（2）服務時間服務時間同到達時間一樣，也可以分為確定和隨機兩種類型。自動沖洗汽車的裝置、紅綠燈系統(tǒng)屬于確定服務時間，而其他更常見的排隊系統(tǒng)大多屬于隨機服務時間。（3）服務的平穩(wěn)性服務的平穩(wěn)性是指服務時間分布及其特征參數(shù)不隨時間的變化而變化。服務的平穩(wěn)性排除了工作時間長短（疲勞程度）以及對列長短（服務員有意加快各種速度）對服務時間分布的影響。（4）服務規(guī)則按對等待顧客的服務順序,服務規(guī)則可分為先到先服務（FIFO,firstin,firstout）、后到先服務（LIFO,lastin,firstout）、有優(yōu)先權的服務（SWP,servicewithpriority）和隨機服務（SIRO,serviceinrandomorder）。先到先服務對一般排隊系統(tǒng)是最符合常理的，但當顧客是一些待加工的工件時，就不存在明顯的誘因去遵守先到先服務的規(guī)則，事實上，如果工件是一一堆起來的，那么服務規(guī)則自然是后到先服務；如果工件是無規(guī)則零散存放的，那么隨機服務規(guī)則可能是最合適的。有優(yōu)先權的服務即服務臺對具有某種特性的顧客給予有限服務，如醫(yī)院會優(yōu)先搶救危重病人。最簡單的服務時間分布是負指數(shù)分布，在這種情況下，平均服務率一個參數(shù)就完全描述了整個服務過程。4．輸出輸出是指顧客從得到服務到離開服務系統(tǒng)的情況，由于一結束服務顧客即刻離開服務系統(tǒng)，所以輸出是通過服務時間來加以描述的。排隊系統(tǒng)的分類描述根據(jù)排隊系統(tǒng)的基本構成，肯達爾（Kendall）于1953年提出了排隊系統(tǒng)的分類描述法。這種方法是通過由斜線分割開的6項代碼來表示一個特定排隊模型的。前兩項為字符碼，分別表示到達過程和服務過程的分布形式，通常用M代表泊松輸入（相繼到達間隔時間服從負指數(shù)分布）或服務時間服從負指數(shù)分布；D代表確定的相繼到達間隔時間或服務時間；EK代表k階愛爾朗（Erlang）分布的相繼到達間隔時間或服務時間；GI代表相互獨立的相繼到達間隔時間；G代表一般的服務時間。第三、四、五三項可以是數(shù)字型代碼，分別代表服務臺數(shù)目、系統(tǒng)的容量和顧客總量。最后一項表示排隊規(guī)則，即顧客接受服務的順序。此記法的前三項為必選項必須明確寫出，而后三項為選擇項，在系統(tǒng)容量無限、顧客總量無限和先到先服務的情況下，它們可以被省略。按照肯達爾排隊模型的記法，MIMIn代表顧客輸入為泊松分布，服務時間為負指數(shù)分布，有n個并聯(lián)服務臺的排隊系統(tǒng)；MID/2IN代表泊松分布的顧客到達，確定的服務時間，有2個并聯(lián)服務臺，系統(tǒng)容量為N的排隊系統(tǒng)；DIGI1代表定長輸入，一般服務時間，單個服務臺的排隊系統(tǒng)；GI/E3/c/10/10/LIFO代表相互獨立的相繼到達間隔時間，三階愛爾朗分布的服務時間，c個并聯(lián)服務臺，系統(tǒng)容量為10，顧客總量為10，后到先服務的排隊系統(tǒng)。排隊系統(tǒng)的數(shù)量指標一個特定的模型可能會有多種假設，同時也需要通過多種數(shù)量指標來加以描述。由于受所處環(huán)境的影響，我們只需要選擇那些起關鍵作用的指標作為模型求解的對象。環(huán)境不同，選擇的指標也會不同；例如，我們有時關心的是顧客平均等待的時間，有時關心的是服務臺的利用率。盡管人們希望得到關于系統(tǒng)行為的詳細信息，但研究中所能夠給出的一切結果都只能是一個穩(wěn)定指標。穩(wěn)定指標并不意味著系統(tǒng)以某種固定的方式有規(guī)律地運轉，它們所提供的僅僅是這個系統(tǒng)經(jīng)歷長期運轉所反映出的數(shù)學期望值。系統(tǒng)中顧客數(shù)量的概率分布（Pn）無論什么樣的排隊模型，都以Pn代表穩(wěn)定狀態(tài)下系統(tǒng)中包含n個顧客的概率，n的取值可以從0—直到系統(tǒng)容量N。系統(tǒng)中顧客數(shù)量期望值（系統(tǒng)狀態(tài)，L）系統(tǒng)中顧客數(shù)量既包括正在接受服務的顧客，也包括排隊等待的顧客。隊列中顧客數(shù)量期望值（對長，Lq）q系統(tǒng)中等待服務的顧客數(shù)量，它等于系統(tǒng)狀態(tài)減去正在接受服務的顧客數(shù)。顧客在系統(tǒng)中的平均逗留時間（W）顧客在系統(tǒng)中的平均逗留時間包括顧客接受服務的時間，也包括顧客排隊等待的時間。

顧客的平均等待時間（W）Q

顧客的平均等待時間等于其系統(tǒng)逗留時間減去服務時間。若用c表示并聯(lián)服務臺的數(shù)量，因此p+p+p+代表所有服務臺均被c c+1 c+2占用的概率或顧客被迫排隊的概率。被占用服務臺的個數(shù)是一個與系統(tǒng)狀態(tài)密切相關的隨機變量，當n<c時有n個服務臺被占用，當n>c時有c個服務臺被占用。這也就是說，在全部的服務臺被占滿之前，n個服務臺被占用同系統(tǒng)中有n個顧客是等價的。如果用q代表有i個顧客在隊列中的概率，那么iq二p(i>0)i c+i系統(tǒng)狀態(tài)L是系統(tǒng)中顧客數(shù)量期望值，因此與系統(tǒng)顧客數(shù)量的概率分布P具有n如下關系：10-1)用B表示被占用服務臺數(shù)量的期望值，則:10-2)10-3)B-工i-p+藝c10-2)10-3)iii=0 i=c+1L是對長，代表隊列中顧客數(shù)量的期望值，則:q ,y.L=i-qqii于是：L=L+B （10-4）q即系統(tǒng)中顧客數(shù)量期望值等于隊列中顧客數(shù)量期望值與被占用服務臺數(shù)量的期望值之和。如果用代表服務時間期望值，與式（10-4）類似有:10-5)用U代表服務臺利用率期望值，由于各服務臺的利用率不盡相同，所以U是所有服務臺綜合的利用率期望值。服務臺利用率期望值應該等于被占用服務臺數(shù)量的期望值與總服務臺數(shù)之比，即:U=Bc （10-6）如果c=1，式(10-6)可簡化為U=B=1-p。0§2排隊系統(tǒng)的數(shù)學模型最簡單流在排隊論中經(jīng)常用到最簡單流這一概念。所謂最簡單流就是指在t這一時間段里有k個顧客到達服務系統(tǒng)的概率v(t)服從泊松分布，即：kv(t)=e小3 (k=0,1,2,) (10-7)k k!由于最簡單流與實際顧客到達流的近似性，更是由于最簡單流假設極大地簡化了問題的分析與計算，因此排隊論所研究的問題普遍是最簡單流問題。???什么樣的排隊系統(tǒng)才能具有最簡單流呢？我們可以通過如下三個標準來加以判斷：1．平穩(wěn)性平穩(wěn)性是指在一定的時間間隔內(nèi)，來到服務系統(tǒng)的顧客數(shù)量只與這段時間間隔的長短有關，而與這段時間間隔的起始時刻無關。2．獨立性獨立性是指顧客的到達率與系統(tǒng)的狀態(tài)無關，無論系統(tǒng)中有多少顧客，顧客的到達率不變。3．唯一性在一個充分小的時間間隔里不可能有兩個或兩個以上的顧客到達，只能有一個顧客到達。式(10-7)中的參數(shù)九代表單位時間里到達顧客的平均數(shù)，即平均到達率。我們可以通過令t=1求v(t)的數(shù)學期望來加以證明：k藝k-v(1)=藝ke-九妙=九藝xk-1e—九=九k k! (k-1)!k=0 k=o k=0既然九代表單位時間里到達顧客的平均數(shù)，那么￡自然代表平均的顧客到達時間間隔。負指數(shù)分布的服務時間負指數(shù)分布具有如下的概率密度函數(shù)和分布函數(shù)：f(x)=xe-xx，F(xiàn)(x)=1-e-xx假設服務臺對顧客的服務時間t服從負指數(shù)分布，即f(t)二卩e-戌；則對于每一顧客的平均服務時間為，而卩自然代表服務率。這一點可以通過如下式子加以證明：E(t)=Jtf(t)dt=Jt卩e-wdt=-Jtd(e-w)000=—十Je-wd(―卩t)=十0生死過程一個顧客的到達將使系統(tǒng)狀態(tài)從n到n+1，這一過程成為生；一個顧客的離開將使系統(tǒng)狀態(tài)從n到n-1，這一過程成為死。系統(tǒng)狀態(tài)的轉移可以用狀態(tài)轉移圖(圖10-2)來加以描述，圖中結點代表狀態(tài)，箭線代表狀態(tài)轉移。由于在同一時間不可能有兩個事件發(fā)生，所以不存在跨狀態(tài)的狀態(tài)轉移。利用圖10-2所示的狀態(tài)轉移形式，根據(jù)流的平衡原理可以建立起穩(wěn)定狀態(tài)的狀態(tài)轉移方程組。所謂流的平衡原理就是在穩(wěn)定狀態(tài)下，流入任意一個結點的流量等于流出該結點的流量。流量的概念是這樣定義的，如果從狀態(tài)i到狀態(tài)j轉移弧上的轉移率為r..，那么這條轉移弧所發(fā)生的流量就是r..p.。流的平衡原理具有鮮明的ijiji直觀性和廣泛的適用性。將流的平衡原理應用于轉移圖的各個狀態(tài)，每一狀態(tài)都可給出一個以p.為變量的線性方程。這些線性方程組成的線性方程組無條件地決定了p.的分布。'九p=pp01九p+pp=Xp+pp1102Xp+pp=Xp+pp2213流的平衡方程具有一種特別易于手工求解的形式，第一個方程是根據(jù)狀態(tài)“0”的流平衡條件建立的，因為與狀態(tài)“0”相鄰的狀態(tài)只有狀態(tài)“1”，所以此方程只含有p0和p1兩個未知量。雖然p0和p1都隨模型的變化而變化，但利用此方程用p0表示p1總是可以實現(xiàn)的。第二個方程是根據(jù)狀態(tài)“1”的流平衡條件建立的，它涉及p0、p1和p2三個未知量。通過以p0表示Pj，可以把未知量減少為p0和p2兩個，進而實現(xiàn)用p0表示p2。依次類推，每一個方程均可以把一個新的未知量表示為p0的函數(shù)，直到將所有的未知量都用p0表示出來。因為此時每一個pi都已表示為p0的函數(shù)，所以正規(guī)方程工P.=1可表示為只i含p0一個未知量的形式，進而求的p0和其他所有的狀態(tài)概率P廣如果模型含有無限個狀態(tài)，正規(guī)方程工P=1可表示為只含p0一個未知量的無窮序列。i對于系統(tǒng)容量無限的排隊系統(tǒng)，按照上述求解過程可以得到如下結果：P=（先）P1卩0P=（亠）2P2卩0P=（亠）iPi卩0引入正規(guī)方程工P=1有：iiP[1+（鼻）+（亠）2+ +（篦）n+ ]=10□卩卩出現(xiàn)在方括號中的無窮序列是一個簡單的等比序列，倘若殆是一個小于1的數(shù)，那??? ???么該等比序列將收斂于一個有限的和廠丄。解該正規(guī)方程有：-（篦）P=1一興0卩進而有：P=（人）i（1一人）i卩卩從上述的概率分布解可以看出，九和卩兩個參數(shù)總是以比值的形式出現(xiàn)在一起，所以我們可以用一個小寫的希臘字母P來代替先，即p=%。將P代入上述解中去可使其更具簡明的形式：

p二pi（1—p）i新的參數(shù)p是到達率與服務率之比，被稱為繁忙率。p也可以有其他的表現(xiàn)形式，如P二，此時p的含義是平均服務時間與相繼到達平均間隔時間之比；P二九?十，此時p的含義是到達率與平均服務時間的積，即在一個平均服務時間里到達的平均顧客數(shù)量。p的所有這些含義，均給出了要求p<1的邏輯解釋；簡言之，如果顧客的平均到達率大于平均服務率，那么系統(tǒng)的隊長將無限增加，從而造成系統(tǒng)永遠也達不到穩(wěn)定狀態(tài)。基本模型由于系統(tǒng)中顧客的數(shù)量越多，顧客在系統(tǒng)中逗留的時間也就會越長，所以可以希望在W和L之間建立起某種關系。李特爾（Little）公式給出了L、W和九三者之間的關系L二九?W，即系統(tǒng)中平均顧客數(shù)等于顧客平均到達率與平均逗留時間的積。根據(jù)李特爾公式，自然可以得到關系式L二九?W。qq有了李特爾公式，即可得到如下排隊系統(tǒng)的基本模型10-8)L=i?p=(1—p)[p+2p2+3p310-8)ii=010-9)藝(n一1)pn藝(n一1)pnn=1nnp2=L一(1p2=L一(1一p0)=L—p=匚？10-10)10-11)需要強調(diào)的是，本節(jié)所涉及的所有模型均是基于M/M/1排隊系統(tǒng)構建的，對于其他排隊系統(tǒng)，應根據(jù)系統(tǒng)的具體情況對某些模型進行適當?shù)恼{(diào)整。L—L=p=B，即p代表了平均被占用的服務臺數(shù)或服務臺利用率。從式q（10-8）和式（10-10）可以顯示出一個令人關心的問題，為了限制平均隊長為一個

適度小的數(shù)值，那么就不得不犧牲一定的服務臺利用率。例如，要保持L<9，那么服務臺利用率P就一定不會超過90%。也就是說為了確保系統(tǒng)中的顧客數(shù)不超過9人，必須容忍服務臺有10%的空閑時間?！?排隊模型的應用［例10-1］某醫(yī)院的一個診室根據(jù)病人來診和診治的時間記錄，任意抽查100個工作小時，每小時來就診的病人數(shù)n的出現(xiàn)次數(shù)，以及任意抽查100個完成診治的病人病歷，所用時間v出現(xiàn)的次數(shù)如表10-1所示，試分析該排隊系統(tǒng)。表10-1病人到達數(shù)n出現(xiàn)次數(shù)f診治時間v出現(xiàn)次數(shù)fv0100.0?0.2381280.2?0.4252290.4?0.6173160.6?0.894100.8?1.06561.0?1.25611.2?1.40合計100合計100計算每小時病人的平均到達數(shù)，即到達率九解：將此排隊系統(tǒng)抽象為M/M/1計算每小時病人的平均到達數(shù)，即到達率九（1）九=幕￡二2.1（人/小時）2）2）計算每次診治的平均時間（v值取區(qū)間中值）丫vf每次診治的平均時間二］00v二0.4（小時/人）3)3)每小時平均完成的診治人數(shù)（服務率）卩卩=+=2.5（人/小時）0.44)4)2.1的泊松分布，診治時間服從參數(shù)為2.5負指數(shù)分布。具體檢驗過程可參見數(shù)理統(tǒng)計學。（5）計算繁忙率PP=亠=當=0.84卩2.5說明該診室有84%的時間在為病人服務，有16%的時間是空閑的。6）計算各排隊系統(tǒng)指標L-L-去-25^21-5.25人）L=L=pL=0.84x5.25=4.41q人）1 =2.5卩1 =2.5卩一九2.5—2.1P-0.84H—九2.5—2.1小時）=2.1小時）[例10-2]顧客到達只有一名理發(fā)師的理發(fā)部，顧客平均每20分鐘到達一位，每位顧客的處理時間為15分鐘。假設以上兩種時間均服從負指數(shù)分布，若該理發(fā)部希望90%的顧客都能有座位，則應設置多少個等待席位。解：將此排隊系統(tǒng)抽象為M/M/1模型并設等待席位為N90%的顧客都能有座位，相當于該理發(fā)部內(nèi)的顧客總數(shù)不多于N+1的概率不小于0.9，即：因p-（1—p）因pi—1—pN+2>0.9ii-0 i-0-0.754N+2>葺-器-8N>6[例10-3]某一大型客運公司，機車大修率服從泊松分布，平均每天2臺。機修廠對每臺大修機車的修理時間服從負指數(shù)分布，平均每臺天。卩是一個與修理廠年度運行費用K有關的函數(shù)，嘰K）-0.1+10-5xK（其中K>1.9x105元）。又已知機車大修平均每天損失1000元，試決定該客運公司機修廠最佳的年度運行費用。解：將此排隊系統(tǒng)抽象為M/M/1模型（1）計算每月機車發(fā)生故障造成的損失S1S]=（系統(tǒng)中的機車數(shù)）x（每輛每天損失）x（月工作日數(shù)）=Lx1000x21.5=21500(—)|LX—九=21500(=21500(0.1+10—5K—X)=4300010-5K—1.9（2）計算每月機修廠的運行費用S2s=K212(3)計算每月總費用STOC\o"1-5"\h\zSS,S43000 ‘KS=S+S= + -1 2 10-5K—1.9 124)求最佳的年度運行費用dS 43000x10—5 1=—+=0dK (10-5K—1.9)212Ku41.8(萬元)卩(K)=0.1+10-5x41.8x104=4.28(輛/天)[例10-4]某一個只有一名理發(fā)師的理發(fā)部，有3個座位供顧客排隊等待，當3個等待座位都被占用時，后來的顧客會自動離開。顧客的平均到達率為每小時3人理發(fā)的平均時間為15分鐘，試分析該排隊系統(tǒng)的運行情況。解：將此排隊系統(tǒng)抽象為M/M/1/4模型，其狀態(tài)轉移模型如圖10-3利用流平衡方程組可以得到與M/M/1模型具有相同形式的狀態(tài)概率分布:P=（①》-p=Pi-p（i=0丄2,3,4）i卩0 0再利用正規(guī)方程即可求得系統(tǒng)空閑的概率耳：1—P1—PP= =0 1—P4+1 1—P5計算顧客一到達即刻就能得到服務的概率p=r3=0p=r3=0兀i-p1-p5I"沁0.33理發(fā)部內(nèi)的平均顧客數(shù)和隊列中等待的平均顧客數(shù)L=￡i-p=p+2p+3p+4pi1 2 3 4i=0=pp(1+2p+3p2+4p3)0=0.75x0.33(1+2x0.75+3x0.752+4x0.753)沁1.45L=L-(1-p)=1.45-(1-0.33)=0.78q0有效的到達率九e在隊長受到限制的情況下，當系統(tǒng)滿員時，新來的顧客會自動離開；雖然顧客以九的速率來到服務系統(tǒng)，但由于一部分顧客的自動離開，真正進入系統(tǒng)的顧客輸入率應該是比九小的九。因為服務系統(tǒng)的利用率可以從兩個不同的角度表達為e九 尢1—p或一^,即1—p=~e，所以應有九=卩(1—p)。0卩 0卩 e 0九=卩(1—p)=4(1—0.33)=2.68(人/小時)e0顧客在理發(fā)部的平均逗留時間和平均等待時間L1.45W=一= ?0.54(小時)-32(分鐘)九e2.68L0.78W=y= =0.29(小時)-17(分鐘)q九2.68e顧客的損失率p=p4p=0.754x0.33~0.1044=10.44%40[例10-5]某醫(yī)院門前有一個出租車?？空?，因場地的限制只有5個停車位，在沒有停車位時新來的出租車會自動離開。當?？空居熊嚂r，從醫(yī)院出來的病人就租車；當停靠站無車時，病人就向出租公司要車。設出租車以平均每小時8輛(九=8)的泊松分布到達停靠站，從醫(yī)院出來病人的間隔時間為負指數(shù)分布，平均間隔時間為6分鐘。試求(1)出租車來到醫(yī)院門前，?？空居锌瘴坏母怕剩?2)進入?？空镜某鲎廛嚨钠骄却龝r間；(3)從醫(yī)院出來的病人直接租到車的概率。解：將?？空九c到達的出租車作為一個排隊系統(tǒng)，1號車位相當于正在接受服務的位置，2、3、4、5號車位相當于隊列，這樣就構建了一個M/M/1/5排隊模型。在該排隊系統(tǒng)中有效的服務率：卩二10(1-P)e01-p同上例：p=0 1-p6九 8 0.8(1-p6)p=—= =—卩 10(1-p)P-P6e0pq0.97，p沁0.18，卩=8.20e將系統(tǒng)狀態(tài)i、P和i-P列于表10-2，便可十分方便地回答本例的各個問題。ii表10-2ip=pipi 0i-pi00.180010.1740.17420.1690.33830.1640.49240.1590.63650.1540.770合計1.0002.410出租車來到醫(yī)院門前，?？空居锌瘴坏母怕蕄=￡p=1一p=0.846i5i=0進入停靠站的出租車的平均等待時間九=九(1-p)=8(1-0.154)=6.768e5L=fi-p=2.410ii=0L2.410W=一= =0.356（小時）q21（分鐘）九6.768e3）從醫(yī)院出來的病人直接租到車的概率P二1-P二1-°」8二°82[例10-6]設一名工人負責照管6臺自動機床，當機床需要加料或發(fā)生故障時就自動停機，等待工人處理。設機床平均的停機間隔為1小時（九二1）,工人處理的平均時間為0.1小時（R=1°），以上兩個時間均服從負指數(shù)分布。試計算系統(tǒng)的各項指標。解：該例屬于顧客總體有限的排隊系統(tǒng)，記為M/M/1/6/6，可用圖10-4加以描述。這種模型同前面討論過的模型的主要區(qū)別就在于到達率的不同。通過直覺的分析，我們可以得到這樣的結論：顧客源中的潛在顧客越多，顧客的到達率越大；而系統(tǒng)中的顧客越多，顧客的到達率越小。在顧客源變空（所有顧客均在系統(tǒng)中）的極限狀態(tài)，顧客的到達率自然減少到“0”。令九代表每一個顧客的平均到達率，它可以通過觀測每一個顧客在顧客源中所逗留的時間來加以統(tǒng)計。顧客在顧客源中所逗留的時間是指從某一顧客接受完服務回到顧客源到他再次進入排隊系統(tǒng)所經(jīng)歷的時間。假設此時間服從具有共同數(shù)學期望的負指數(shù)分布，那么九將是平均逗留時間的倒數(shù)。需要注意的是，此時的九不能象以往一樣通過觀測顧客到達系統(tǒng)的時間間隔來推算，因為此時的時間間隔與系統(tǒng)中的顧客數(shù)之間存在相關關系，這樣得到的到達率僅僅是整個系統(tǒng)的平均到達率而不是每一個顧客的平均到達率。

如果只有一個顧客在顧客源中而其他顧客均在系統(tǒng)中，很顯然此時的顧客到達率就是九；如果顧客源中有兩個顧客，那么此時的顧客到達率將是2九，這樣依次類推可以得到圖10-5所示的系統(tǒng)狀態(tài)轉移圖。根據(jù)圖10-5可得穩(wěn)定狀態(tài)流平衡方程：0二一6九P+卩P(i=0)

010二(6-i+1)P-[(6—浪+卩]P+卩P (i=1,2,3,4,5)i一i i i+i0二九P-卩P (i=6)56求解這些方程可得一般形式的解：(i=123,4,5,6)此例?=1=0.1，所以有:卩10P=6!P=6!(0.1)P=0.6P,15!00P= (0.1)3P=0.12P，3 3! 0 06!(0.1)5P=0.0072P,1!006!P= (0.1)2P=0.3P24!006!P= (0.1)4P=0.036P4 2! 0 06!P= (0.1)6P=0.00072P60!0又由于藝P=1，所以有P=0.4845，進而有：i0i=0工人的忙期1-P=1-0.4845=0.51550系統(tǒng)內(nèi)的平均機床數(shù)和隊列中等待的平均機床數(shù)L=工i-P沁0.8454ii=0L=L-(1-P)=0.8454-0.5155=0.3299q0機床每次停機的平均時間和等待處理的平均時間九=6九P+5九P+4九P+3九P+2九P+九P

e 0 1 2 3 4 5=6P+5P+4P+3P+2P+P0 1 2 3 4 5

二6P+5P+4P+3P+2P+P0 1 2 3 4 5二10.6392P沁5.16070L0.8454W二一二 沁0.164（小時）二9.84（分鐘）九5.1607eW=W--=0.164-丄=0.064（小時）二3.84（分鐘）q卩 104）機床停機時間占總時間的比率L4）機床停機時間占總時間的比率L_0.8454N6沁0.141_14.1%[例10-7]如果將上例改為三名工人聯(lián)合負責看管20臺自動機床，其他各項數(shù)據(jù)不變，試分析系統(tǒng)的各項指標。解：該例屬于顧客總體有限并聯(lián)服務臺的排隊系統(tǒng)，記為M/M/3/20/20,九即九即S_3，N_20， _0.1；系統(tǒng)狀態(tài)轉移如圖10-6所示。根據(jù)圖10-6可得穩(wěn)定狀態(tài)流平衡方程，從而計算出系統(tǒng)狀態(tài)的概率分布。計算數(shù)據(jù)列于表10-3中，由于當i>12時，P<0.5x10-5，故忽略不計。i(1)工人的平均空閑時間121r(3-i)P_—(3P+2P+P)_0.40423 i3 0 1 2i_0(2)工人的忙期1-0.4042_0.5958系統(tǒng)內(nèi)的平均機床數(shù)和隊列中等待的平均機床數(shù)L仝i-P沁2.12677i_0

L二藝（i—3）P沁0.33863qii=44)5)機床停機時間占總時間的比率4)5)機床停機時間占總時間的比率L_2.12677N20沁0.106_10.6%機床每次停機的平均時間和等待處理的平均時間九_藝（20—i）九P沁17.8746eii_0T C1CAWW_—_ 沁0.119（小時）_7.14（分鐘）九17.8746eL0.33863W_—_ 沁0.019（小時）_1.14（分鐘）q九17.8746e表10-3狀態(tài)i處理數(shù)等待數(shù)空閑人數(shù)Pi/PoP.1（i-3）PiiP.100031.00000.13626——11022.00000.27250 0.2725022011.90000.25888—0.5177633001.14000.15533——0.4659943100.64600.088020.088020.3520853200.34450.046940.093880.2347063300.17220.023470.070410.1408273400.08040.010950.043800.0766583500.03480.004750.023750.0388093600.01390.001900.011400.01710103700.00510.000700.004900.00700113800.00170.000230.001840.00253123900.00050.000070.000630.00084比較上述二例，可以看出當三名工人聯(lián)合看管20臺機床時，雖然每一名工人平均看管的機床數(shù)增加了，但機床的利用率反而卻提高了，這是三名工人相互協(xié)作的結果。[例10-8]某自餐廳有三個服務窗口，假設顧客的到達服從泊松分布，平均到達率X_0.6人/分鐘，服務時間服從負指數(shù)分布，平均服務率R_0.4人/分鐘。現(xiàn)假

設顧客到達后排成一個統(tǒng)一的隊列，從前依次向空閑的窗口購餐，試分析該排隊系統(tǒng)的各項指標。解：該例屬于顧客總體無限、系統(tǒng)容量無限的并聯(lián)服務系統(tǒng)，記為M/M/S,即S=3；系統(tǒng)狀態(tài)轉移如圖10-7所示。根據(jù)圖10-7可得穩(wěn)定狀態(tài)流平衡方程卩P二九P10(i+1)pP+九P二(九+ip)P (1<i<S)TOC\o"1-5"\h\zi+1 i-1 iSpP+九P二(九+Sp)P (i〉S)i+1 i-1 i這里藝P=1，且p=-^<1。用遞推法可求解出系統(tǒng)各狀態(tài)的概率:i Sp11i+ ?—S11i+ ?—S!1-pS]-1二龍1?-)i!pi=0PTFPo(i<S)P=丘（純（i>S）利用各狀態(tài)概率，可求得系統(tǒng)的運行指標九L=L+—qpi=S+1(Sp)Sp

S!(1i=S+1此例~=06=此例~=06=1.5，P=卩0.41）餐廳的空閑率LW=—q九S^=3X0.40.6=0.5；因此:P=[150+匕+竺+丄?旦]-1=0.210 0! 1! 2!引1—0.52）2）隊列中的平均顧客數(shù)1.53X0.5Lq=31(1—WX021?0236(人3）3）系統(tǒng)中的平均顧客數(shù)L=L+—=0.236+1.5=1.736(人)q卩4）4）顧客在隊列中的平均等待時間Wq= =囂?0393（分鐘）5）5）L1.736W=—= ?2.893（分鐘）九0.6顧客到達需要等待的概率P(i>3)=1-(P+P+P)沁0.23012[例10-9]在黑龍江省的大慶市有一座糧庫，由于該市處于高寒的平原地帶，小麥是其最主要的農(nóng)作物。在收獲的季節(jié)里，卡車載著小麥從田地運往糧庫并盡可能快地返回再運下一車。在卡車將小麥傾入烘干爐之前，要抽樣檢查小麥的質量，當然還有稱重等其他一些驗收細節(jié)。因小麥一旦成熟很容易受到風雨的侵蝕，任何耽擱都會給農(nóng)場帶來巨大的損失，所以農(nóng)場總是想盡快收完田里的小麥并運往糧庫。由于該市的所有小麥幾乎是在同一時間成熟的，因此在糧庫產(chǎn)生車輛排隊問題并不令人驚奇。為方便起見，假設卡車相繼到達的時間間隔是6.67分鐘，平均服務時間為6分鐘，這樣利用M/M/1模型的標準公式就能計算出每輛卡車在糧庫的平均逗留時間。這一時間應與實際消耗的時間相匹配，如有耽擱農(nóng)場會認為是無法忍受的。在農(nóng)場合作大會上，提出了三種完善糧庫收糧系統(tǒng)的方案：1．增加卡車負荷，這樣卡車相繼到達的時間間隔將增至10分鐘；同時增加驗收人員，使平均服務時間減少為4分鐘。這種相對較小的系統(tǒng)調(diào)整，預計需要花費3萬元。2．一些農(nóng)場認為，盡管第一個方案能在一定程度上緩解矛盾，但并不能從根本上解決問題。他們相信進行較大的改造是必要的，主張對糧庫進行擴建，使服務能力提高一倍。到達的卡車排成一個統(tǒng)一的隊列，最前面的車將進入最早可利用的驗收站接受驗收。這一改造大約需要40萬元。3．一些農(nóng)場認為應該在城市的另一處再單獨建一座與現(xiàn)有糧庫完全相同的新糧庫。這一方案除了把整個服務能力提高一倍外，還把車輛的到達分為兩等份，其預算投資為100萬元。經(jīng)過初步分析，大家普遍認為：第一個方案雖然從費用角度具有一定的吸引力，但如此小的調(diào)整對于解決如此嚴重的問題其效果不會理想；第三個方案似乎提供了一種根本的解決問題的方法，但所需的費用將成為巨大的經(jīng)濟負擔；第二個方案才是權衡的最佳選擇?；谏鲜稣J識，你將做出怎樣的選擇呢？用排隊論的術語來講，第一個方案只改變了模型的參數(shù)而沒有改變模型的結構；第二個方案形成一個單隊列雙服務臺服務系統(tǒng)；第三個方案形成一個雙隊列雙服務臺系統(tǒng)。假設卡車到達服從泊松分布，服務時間服從負指數(shù)分布，可利用簡單的馬爾科夫排隊模型進行分析。方案一和方案二的分析可以直接利用前例中的相應模型來進行，而方案三需要分解為兩個獨立的M/M/1系統(tǒng)。由于這兩個獨立的M/M/1系統(tǒng)具有相同的系統(tǒng)參數(shù)；因此，在分析個別車輛時，只研究其中一個系統(tǒng)就足夠了。表10-4給出了各方案車輛在系統(tǒng)中的平均逗留時間，這一結果足以使你大吃一驚，花錢最少的方案（方案一）卻產(chǎn)生了最佳的系統(tǒng)完善效果，這是每一個農(nóng)場單憑直覺無法想象的。表10-4方 案模 型到達率服務率逗留時間現(xiàn)方案M/M/19（人/小時）10（人/小時）60（分鐘）1M/M/16156.672M/M/29107.523M/M/14.51010.91§4非馬爾科夫排隊模型上述的一切排隊模型都是以馬爾科夫模型（最簡單流）為基礎的，系統(tǒng)的概率分布處于負指數(shù)分布這一基本假設的約束之下。雖然這一假設為我們帶來了許多方便，但有時它確實與實際情況具有相當大的差距。因此，特別需要那些不嚴格依靠馬爾科夫假設的排隊模型。鑒于此，本節(jié)將對幾種典型的非馬爾科夫排隊模型進行簡單的介紹。依據(jù)前面的分析，下述關系式無論在什么情況下都應該是成立的：

L二L+L W二W+E(T)qcqL二九W L二九Weqeq其中：L為服務臺中顧客數(shù)量期望值，E(T)為服務時間期望值。c4.1M/G/1模型對于M/G/1模型，服務時間T是一般分布(但要求期望值E(T)和方差Var(T)都存在)，其他條件與M/M/1相同。為了達到穩(wěn)定狀態(tài)，P<1這一條件九C還是必要的，這里P= =1E(T)。在上述條件下有:E(T)p2+九2?Var(T)

2(1-P)此式被稱為Pollaczek-Khintchine(P-K)公式，只要知道九、E(T)和Var(T)，不管T是什么分布，都可以求出系統(tǒng)中的平均顧客數(shù)L,進而通過一定的關系式求出W、W和L。qq[例10-10]顧客按平均2分30秒的時間間隔的負指數(shù)分布到達某一排隊系統(tǒng)，平均服務時間為2分鐘。(1)若服務時間也服從負指數(shù)分布，求顧客的平均逗留時間和等待時間；(2)若服務時間至少需要1分鐘且服從如下分布：TOC\o"1-5"\h\zf(T)=ei-T， T>1f(T)=0， T<1再求顧客的平均逗留時間和等待時間。亠 1 「 1c「 九0.4解：(1)九= =0.4，卩= =0.5，p= = =0.82.5 2 卩0.5W=戸=0.5-0.4W=戸=0.5-0.4=10分鐘)W=0.80.5-0.4分鐘)(2)令T為服務時間，那么T=1+x,其中x是服從均值為1的負指數(shù)分布;于是E(T)=2，Var(T)=Var(1+x)=Var(x)=1，p=X-E(T)=0.4x2=0.8。代入P-K公式得:L=0.8+L=0.8+0.82+0.42x12(1-0.8)二2.8，L=L—p=2.8—0.8=2.0q分鐘）W=-=28=7(分鐘)，W=匕=20=5

九0.4 q九0.4分鐘）4.2M/D/1模型對于服務時間是確定常數(shù)的情形，由于有T= 和Var（T）=0，所以P-K公式將簡化為:p+p+P22(1—P)[例10-11]一自動汽車清洗機，清洗每輛汽車的時間均為6分鐘，汽車按泊松分布到達，平均每15分鐘來一輛。試求L、L、W和W。qq解：此系統(tǒng)是M/D/1排隊系統(tǒng)，其中：九二4，E（T）=卩=10，p=-=0.4，Var（T）=0L二0.4L二0.4+0.422(1—0.4)沁0.533(輛)L=0.533—0.4=0.133（輛）q0.533W=沁0.133（小時）沁8（分鐘）40.133W=沁0.033（小時）?2（分鐘）q4通過P-K公式可以證明，在一般分布的服務時間中，定長服務時間的L、L、qW和W最小。這完全符合人們通常的理解，即服務時間越有規(guī)律，等候的時間也q就越短。

[例10-12]一裝卸隊專為來到碼頭倉庫的貨車裝卸貨物，設貨車的到達服從泊松分布，平均每10分鐘一輛，而裝卸時間與裝卸隊的人數(shù)x成反比。又設該裝卸隊每班(8小時)的生產(chǎn)費用為(20+4x)元，汽車在碼頭裝卸貨物時每小時的損失是15元。若(1)裝卸時間為常數(shù)，一名裝卸工人裝卸一輛汽車需要30分鐘，(2)裝卸時間為負指數(shù)分布，一名裝卸工人裝卸一輛汽車需要30分鐘；試分別確定該裝卸隊應配備的裝卸工人數(shù)。解：計算一小時的費用，該費用包括裝卸隊費用和汽車在系統(tǒng)中逗留的損失，即：20+20+4x8)+15L1)裝卸時間為常數(shù)九二6九二6，于是P=3代入L的表達式有:P22(1-P)3,GO_3「2x-3]x2(1-P22(1-P)x所以：c—2.5+0.5x+45[2x-3]x(x一3)令?！?.5+經(jīng)亠-旦土]-0，可得:dx 2x(x一3)x2(x一3)20.5x4-3x3-40.5x2+135x-202.5—0經(jīng)過試算，該方程在11和12之間有一個根，分別比較二者所對應的費用值因有c(11)—12.858、c(12)—13.422，故裝卸隊應配備11名裝卸工人。2)裝卸時間為負指數(shù)分布c—20+4x+15』)—2.5+0.5x+15(6)8 jlx-A 2x—6令dc—0.5—90x1 —0，可得:dx 2 (x-3)2 1(x—3)2—90,從而xu12.5比較c(⑵和c(13)，由于c(12)—c(13)—13.5，故裝卸隊配備12或13名裝卸工人均可。4.3M/E/1模型k當服務時間為定長時，均方差b=0;當服務時間為負指數(shù)分布時，均方差

◎=丄；而均方差介于這二者之間的一種理論分布稱為愛爾朗(Erlang)分布。假

設T、T、…、T為k個具有相同分布而又相互獨立的負指數(shù)分布，其概率密度分1 2 k別為：f(t)=k卩e-k旳 (t>0)ii其中卩、k是取正值的參數(shù)，而且k取整數(shù)。如果服務臺對顧客的服務不是一項，而是按順序進行的k項，又假設其中每一

項服務的服務時間都具有相同的負指數(shù)分布,則總的服務時間服從k階愛爾朗分布。

實際上愛爾朗分布是Gamma分布的一個特例，愛爾朗分布的數(shù)學期望和方差分別

為E(t)=、Var(t)=。這里有兩個參數(shù)卩和k，有于k值的不同，可以得卩 k卩2到不同的愛爾朗分布，見圖10-8。當k=1時是負指數(shù)分布，當k=+8時是定長分布。圖10-8圖10-8概率密度函數(shù)將Var(t)=擊代入P-K公式得:

L二pL二p+—2k(1-p)(k+1)p2/二 q 2k(1-p)W=一q九如上所述，k階愛爾朗分布的服務時間可用來描述k個服務臺串聯(lián)的排隊系統(tǒng)。當然，這里要求每個服務臺的服務時間相互獨立且服從相同的負指數(shù)分布，各服務臺前的隊列容量無限。[例10-13]某產(chǎn)品的生產(chǎn)需要經(jīng)過4道工序，每一工序的工序時間均服從期望值為2（小時）的負指數(shù)分布。該產(chǎn)品的毛坯按泊松分布到達，平均到達率為每小時0.1件，問計算毛坯經(jīng)過4道工序的期望時間。11解：設卩為平均服務率，那么一就是每件產(chǎn)品的平均服務時間，而廠即是平卩 4卩均每道工序所需要的時間。依題意可知：九二0.1，丄=2（即卩=0.125），2x4(1-0.8)W=-=28=28(小時)九0.1即毛坯經(jīng)過4道工序的期望時間為28小時。§5具有優(yōu)先級的排隊模型在具有優(yōu)先級的排隊模型中，服務對象的選擇并不嚴格按照先到先服務的規(guī)則，如醫(yī)院優(yōu)先搶救急重病人，列車運行客車優(yōu)先貨車、快車優(yōu)先慢車等等。可見在這類模型中，顧客是有等級區(qū)別的，較高等級的顧客比較低等級的顧客具有優(yōu)先接受服務的權力。假設顧客可以分為N個等級，第一級享有至高的優(yōu)先權，第N級享有最低的優(yōu)先權，對同屬一級別的顧客仍然按先到先服務的規(guī)則選擇服務對象。又假設系統(tǒng)中每一級別顧客的輸入均服從泊松分布，用九.（i=1,2,,N）代表具有第i優(yōu)先

級顧客的平均到達率；每一級別顧客的服務時間均服從負指數(shù)分布，且不管級別的1差異都具有相同的服務率卩（一表示每名顧客的服務時間）。再假設當一個具有較高級別顧客到達時，正在接受服務的較低級顧客將被中斷服務，回到排隊系統(tǒng)等待重新得到服務。根據(jù)以上假設，對具有最高級別優(yōu)先級的顧客來講，只有當系統(tǒng)中正在接受服務的顧客也具有最高級別優(yōu)先級的時候，他才需要等待，其他情況均可以立刻得到服務。因此，對于具有最高級別優(yōu)先級的顧客在排隊系統(tǒng)中得到服務的情況就如同沒有其他級別的顧客一樣。所以，對最高級別優(yōu)先級的顧客只要將輸入率九換以九，1此章較前推導的公式是完全適用的?，F(xiàn)在一并考慮第一、第二優(yōu)先級的顧客，設W表示一、二兩級綜合在一起的1-2每個顧客在系統(tǒng)中的平均逗留時間；根據(jù)負指數(shù)分布的性質，對由于高級別顧客到達而中斷服務回到隊列中的顧客，無論他被中斷幾次，他所接受服務的總時間不會有所改變。因此，對W只要將一、二兩級顧客的輸入率簡單相加即可，所以有：1-2（九+九）W二九W+九W121-2 1122其中W和W分別表示具有第一、第二優(yōu)先級的顧客在系統(tǒng)中的平均逗留時間。將12九?W-尹W九?W-尹W1-2 九12同理有：（九+九+九）W123 1-2-3二九W+九W+九W112233即：依次類推有：?W1即：依次類推有：?W1-N藝九Wii-i=h 九?W-—W—1-2-3九133￡九i其中P— <1。cp［例10-14］某醫(yī)院門診部的患者按泊松分布到達，平均到達率九二2人/小時,醫(yī)生對患者的服務時間服從負指數(shù)分布，服務率卩=3人/小時。假設患者中有60%屬于一般患者，30%屬于重病患者，10%屬于病?；颊?，分別就該門診部有一名醫(yī)生和兩名醫(yī)生的情況，計算各類患者等待醫(yī)治的平均等待時間。解：依題可知卩=3、九=0.2、九=0.6、九=1.2123（1）一名醫(yī)生11W二二二0.3571卩―九3-0.211-21_1R-(九+九)-3-(0.2+0.6)12二0.454W=0.2+0.6x0.454-02x0.357=0.48620.60.60.2+0.6+1.212X1- X0357-ifX0454=1379所以：W=W-丄=0.357-0.333=0.024(小時)二1.44(分鐘)1q1卩W=W-丄=0.486-0.333=0.153(小時)二9.18(分鐘)2q 2卩W=W-丄=1.379-0.333=1.046(小時)二62.76(分鐘)3q 3卩2）兩名醫(yī)生利用M/M/2模型的P、L公式，可推得W二?+丄。(*)2(張) 九、+(%)2 1W= 中-［1+(―)+汁］｝+2入(1—)2 |LX1— |LX2p 2p九2p(2p-X)2十［1+-+p竺］｝+丄p(2p-X) p0.223(6—0.2)2［1+°2+令］｝+3二03337W1-廣｛3^“08+缶滬3二03391TOC\o"1-5"\h\z22 2 22 1W二｛ 十[1++ ]｝+—二0.375一2-3 2）2? 6一2） 3 ?W=06+02x0.3391-02x0.3337=0.34100.60.6W=1.2+0.6+0.2x0.375-02x0.3337-06x0.3410=0.39891.2 1.2 1.2所以：W二0.0004（小時）二0.024（分鐘）1qW二0.0077（小時）二0.462（分鐘）2qW=0.0656（小時）二3.936（分鐘）3q§6排隊系統(tǒng)的最優(yōu)化排隊系統(tǒng)的最優(yōu)化問題可分為兩類，即系統(tǒng)設計的最優(yōu)化和系統(tǒng)控制的最優(yōu)化。前者稱為靜態(tài)問題，從排隊論一誕生起就成為人們研究的內(nèi)容，目的在于使新構建的系統(tǒng)有最大的效益；后者稱為動態(tài)問題，是指一個給定的系統(tǒng)如何根據(jù)環(huán)境的變化做出適當?shù)恼{(diào)整，以使某些系統(tǒng)指標得到優(yōu)化。進入80年代以來，動態(tài)問題成為了排隊論研究的重點之一。動態(tài)分析是建立在靜態(tài)分析的基礎之上的，本教材只討論靜態(tài)最優(yōu)化問題。排隊系統(tǒng)存在兩類費用，即與服務設施相關的服務費用和與顧客等待時間長短相關的等待費用。費用模型的出發(fā)點就是要使這兩類費用的總和最小，各種費用在穩(wěn)定狀態(tài)下都是按單位時間來考慮的。一般情況下，服務費用是可以較精確計算或估計的，而顧客的等待費用較為復雜。如機械故障問題中的等待費用可以較精確地估計，但象患者就診或由于隊列太長而失掉顧客所造成的損失，就只能根據(jù)統(tǒng)計經(jīng)驗來加以估計了。6.1M/M/1模型中最優(yōu)服務率y的確定設系統(tǒng)單位時間的服務費用與卩值成正比，比例系數(shù)為C；每一個顧客在系統(tǒng)1中逗留（包括接受服務的時間）的等待費用與等待時間成正比，比例系數(shù)為C，如2果用tc（）表示在給定卩值時的系統(tǒng)總費用，貝y：九

卩一九

卩一九TC(p)=cp+cL=cp+c-1212當J「定時’最佳服務率卩*只與顧客的到達率率有關’根號前取“+”號是因為P=-<1的緣故。

y對于M/M/1/N排隊系統(tǒng)，P為顧客被拒絕的概率，1-P就是顧客被接受NN的概率，所以-(1-P)就是單位時間實際進入系統(tǒng)的平均顧客數(shù)。在穩(wěn)定狀態(tài)下,N-(1-P)也等于單位時間完成服務的平均顧客數(shù)。設每服務1人可收入r元，于是N單位時間收入的期望值是-(1-P)r，純利潤是-(1-P)r-cy。用Z代表純利N N 1潤，于是：1-PNZ=-(1-P)r-cy=-r?一-N1 1-PN+1

yN--N-cy=-yr? -cy1 yN+1--N+11dzdy可得PN+1?N-(N+1)P+PN+1(1-PN+1)2九即最佳服務率比應滿足此式，雖然此式中的C、r、九（P=）和N都是1卩已知數(shù)，但要通過此式求解出V卻不是一件容易的事。對該問題的處理，我們經(jīng)常將式子的左側（對一定的N）作為p的函數(shù)繪制出圖形（如圖10-9），對于給定的rc根據(jù)圖形可直接求出卩:彳，從而求出比。/1對于M/M1llN/N排隊系統(tǒng)，我們?nèi)匀话凑赵O備故障問題來加以考慮。設共有m臺設備，設備連續(xù)運轉的時間服從負指數(shù)分布；有一名維修人員，其處理故障的時間服從負指數(shù)分布。c的含義同上，r為單位時間每臺運轉設備可得的收益,1設備的平均運轉臺數(shù)為m-L，所以單位時間的純收益為：z=(m-L)r-c|H=1mrE (m)—m-1——cuE(m) 1mPmXk.e—x式中的E(x)=y ，稱為泊松部分和,m k!k=0m九P=，而

udEm(x)=E(x)—E(x)

dx m-1 m=0，E可得?(m)E(m)+m[E(m)E (m)—E2(m)] c九m—1p mp p mp m—2p m—1pE2(m)當給定m、c、r、九，要由上式求解出a也是很困難的。對此問題的處理,1我們經(jīng)常將式子的左側（對一定的m）作為P的函數(shù)繪制出圖形（如圖10-10）,對