運(yùn)籌學(xué)課件第十二講

運(yùn)籌學(xué)課程上海交通大學(xué)管理學(xué)院于長(zhǎng)銳電話：28516057E-mail：第十二章排隊(duì)論排隊(duì)現(xiàn)象火車站的售票口理發(fā)店客戶服務(wù)電話乘校車港口食堂吃飯生產(chǎn)流水線這類現(xiàn)象的特點(diǎn)：顧客到來(lái)是隨機(jī)的，服務(wù)機(jī)構(gòu)對(duì)顧客的服務(wù)時(shí)間也是隨機(jī)的。排隊(duì)論也成為隨機(jī)服務(wù)系統(tǒng)理論，這是對(duì)上述隨機(jī)服務(wù)問(wèn)題進(jìn)行研究。隨機(jī)服務(wù)系統(tǒng)所面臨的問(wèn)題服務(wù)系統(tǒng)要改善自身的服務(wù)質(zhì)量，提高顧客滿意度，減少顧客的排隊(duì)等候時(shí)間。VS服務(wù)系統(tǒng)要控制內(nèi)部運(yùn)營(yíng)成本，減少人力、物力資源浪費(fèi)。如何兩者之間取得平衡？排隊(duì)論的研究?jī)?nèi)容性態(tài)問(wèn)題運(yùn)用概率統(tǒng)計(jì)手段，分析隨機(jī)服務(wù)系統(tǒng)的規(guī)律，主要研究排隊(duì)的隊(duì)長(zhǎng)分布、顧客等待時(shí)間分布、服務(wù)機(jī)構(gòu)的忙期分布。包括瞬態(tài)和穩(wěn)態(tài)兩種情形。最優(yōu)化問(wèn)題分為靜態(tài)優(yōu)化和動(dòng)態(tài)優(yōu)化。靜態(tài)優(yōu)化研究服務(wù)系統(tǒng)的設(shè)計(jì)，動(dòng)態(tài)優(yōu)化研究服務(wù)系統(tǒng)運(yùn)營(yíng)?；靖拍睿?）排隊(duì)過(guò)程的一般表示顧客源排隊(duì)機(jī)構(gòu)服務(wù)機(jī)構(gòu)顧客到來(lái)排隊(duì)規(guī)則服務(wù)規(guī)則離開(kāi)隨機(jī)服務(wù)系統(tǒng)顧客源服務(wù)系統(tǒng)服務(wù)對(duì)象的總體。顧客源的組成可能是有限的，也可能是無(wú)限。顧客到來(lái)（輸入過(guò)程）到來(lái)方式：一個(gè)一個(gè)的、成批到來(lái)。到達(dá)的時(shí)間間隔：確定型、隨機(jī)型到達(dá)事件的相互獨(dú)立性：以前到達(dá)顧客的事件對(duì)以后到來(lái)顧客的事件沒(méi)有影響輸入過(guò)程的平穩(wěn)性：顧客相繼到達(dá)的間隔時(shí)間分布和所含參數(shù)（如期望值、方差等）都與時(shí)間無(wú)關(guān)。否則，輸入過(guò)程是非平穩(wěn)的。基本概念（2）排隊(duì)規(guī)則即時(shí)制（損失制）與等待制即時(shí)制（損失制）：如果服務(wù)機(jī)構(gòu)正在被占用，顧客到來(lái)后隨即離去。等待制：如果服務(wù)機(jī)構(gòu)正在被占用，顧客到來(lái)后排隊(duì)等待對(duì)列容量：由于服務(wù)系統(tǒng)內(nèi)部的空間限制或其他原因，有的系統(tǒng)要規(guī)定排隊(duì)容量（允許進(jìn)入排隊(duì)系統(tǒng)的顧客數(shù)）的最大限。有的系統(tǒng)則沒(méi)有這方面限制。對(duì)列數(shù)目：可以使單列也可以是多列?；靖拍睿?）基本概念（4）服務(wù)規(guī)則先到先服務(wù)后到先服務(wù)隨機(jī)服務(wù)有優(yōu)先權(quán)的服務(wù)服務(wù)機(jī)構(gòu)服務(wù)臺(tái)的布置服務(wù)方式：?jiǎn)蝹€(gè)顧客服務(wù)，批量顧客服務(wù)服務(wù)時(shí)間：確定型，隨機(jī)型如果輸入過(guò)程中顧客相繼到達(dá)的時(shí)間間隔和服務(wù)時(shí)間兩者都為確定型（如生產(chǎn)流水線），該問(wèn)題很好處理，不是排隊(duì)論所討論的問(wèn)題。在排隊(duì)論的研究中，兩者至少有一個(gè)隨機(jī)型分布。服務(wù)時(shí)間的平穩(wěn)性。服務(wù)時(shí)間的分布和所含參數(shù)（如期望值、方差等）都與時(shí)間無(wú)關(guān)?；靖拍睿?）排隊(duì)模型的分類X/Y/Z/A/B/CX表示顧客相繼到達(dá)的間隔時(shí)間分布Y表示服務(wù)時(shí)間的分布M——負(fù)指數(shù)分布（Markov）D——確定型（Deterministic）Ek——k階愛(ài)爾朗（Erlang）分布GI——一般相互獨(dú)立（Generalindependent）的時(shí)間間隔分布G——一般服務(wù)時(shí)間分布Z表示并列服務(wù)臺(tái)的數(shù)目A表示服務(wù)系統(tǒng)容量（服務(wù)中和排隊(duì)等待的顧客總和）的限制B表示服務(wù)系統(tǒng)的顧客源數(shù)目C表示服務(wù)系統(tǒng)的服務(wù)規(guī)則，如先到先服務(wù)（FCFS），后到先服務(wù)（LCFS），隨機(jī)服務(wù)（SIRO），優(yōu)先權(quán)服務(wù)（PR）服務(wù)系統(tǒng)中的幾個(gè)重要參數(shù)服務(wù)系統(tǒng)中的性能指標(biāo)參數(shù)與性能指標(biāo)之間的關(guān)系1/λ相鄰兩個(gè)顧客到達(dá)的平均時(shí)間間隔1/u對(duì)每個(gè)顧客的平均服務(wù)時(shí)間Ls=Lq+S

對(duì)于單服務(wù)臺(tái)來(lái)講系統(tǒng)忙期=1-P0排隊(duì)論問(wèn)題的求解思路根據(jù)顧客到達(dá)的時(shí)間間隔和顧客服務(wù)時(shí)間的實(shí)際數(shù)據(jù)資料進(jìn)行分析，確定其理論上是屬于何種概率分布類型；確定系統(tǒng)處于各種狀態(tài)（系統(tǒng)中顧客數(shù)）的概率；計(jì)算反應(yīng)系統(tǒng)特征的一系列性能指標(biāo)（隊(duì)長(zhǎng)、忙期、逗留時(shí)間、等待時(shí)間等）顧客到達(dá)的時(shí)間間隔分布與服務(wù)時(shí)間的分布解決了顧客到達(dá)的時(shí)間間隔分布與服務(wù)時(shí)間的分布排隊(duì)論問(wèn)題迎刃而解；顧客到達(dá)的時(shí)間間隔分布與服務(wù)時(shí)間的分布是隨機(jī)的，情況較為復(fù)雜，需拿出來(lái)單獨(dú)研究；介紹幾種常用的隨機(jī)模型。泊松流（poisson）（1）設(shè)N(t)表示在時(shí)刻t服務(wù)系統(tǒng)內(nèi)的顧客數(shù)Pn(t1,t2)表示在時(shí)間區(qū)間[t1,t2)（t1>t2）內(nèi)有n個(gè)顧客到達(dá)的概率，即如果滿足以下三個(gè)條件，可以說(shuō)顧客到達(dá)的形成泊松流：（1）無(wú)后效性：在不相重疊的時(shí)間區(qū)間內(nèi)顧客到達(dá)數(shù)是相互獨(dú)立；（2）平穩(wěn)性：對(duì)充分小的⊿t，在時(shí)間區(qū)間[t,t+⊿t)內(nèi)有一個(gè)顧客到達(dá)的概率與t無(wú)關(guān)，而幾乎與區(qū)間長(zhǎng)⊿t成正比其中o(⊿t),當(dāng)⊿t→0時(shí)，是關(guān)于⊿t的高階無(wú)窮??；λ>0是常數(shù)，表示單位時(shí)間有一個(gè)顧客到達(dá)的概率。（3）普通性：對(duì)于充分小的⊿t，在時(shí)間區(qū)間[t,t+⊿t)內(nèi)有2個(gè)或2個(gè)以上顧客到達(dá)的概率極小，可以忽略目前在排隊(duì)論的研究中，顧客到達(dá)的時(shí)間分布還僅限于對(duì)泊松流分布的研究，其他分布用數(shù)學(xué)解析方法還得不到滿意解。泊松流（poisson）（2）實(shí)例負(fù)指數(shù)分布(1)設(shè)顧客到達(dá)的時(shí)間間隔T為隨機(jī)變量，是一個(gè)以λ為參數(shù)的負(fù)指數(shù)分布，則它的概率密度函數(shù)為：負(fù)指數(shù)分布(2)性質(zhì)（2）當(dāng)服務(wù)時(shí)間服從以u(píng)為參數(shù)的負(fù)指數(shù)分布則離開(kāi)服務(wù)系統(tǒng)的顧客數(shù)概率分布為概率密度為u的泊松流（3）無(wú)記憶性（馬爾可夫性）即一個(gè)顧客到來(lái)所需的時(shí)間間隔t與過(guò)去一個(gè)顧客到來(lái)所需的時(shí)間間隔s無(wú)關(guān)，所以在隨機(jī)服務(wù)系統(tǒng)中，如果顧客到達(dá)的時(shí)間間隔為負(fù)指數(shù)分布，則顧客到達(dá)是存隨機(jī)的。實(shí)例愛(ài)爾朗分布（Erlang）單服務(wù)臺(tái)負(fù)指數(shù)分布系統(tǒng)分析模型類型標(biāo)準(zhǔn)模型，M/M/1/∞/∞系統(tǒng)的容量有限制，M/M/1/N/∞顧客源為有限數(shù)，M/M/1/∞/mM/M/1/∞/∞（1）