【大學課件】QuickPass系統(tǒng)排隊問題

1、http:/ v銀行窗口，atmv醫(yī)院、理發(fā)、火車售票v游樂場的游樂項目?http:/ is quickpass?v工作原理：1.到達的顧客將自己的票插入fastpass的slot中2.fastpass計算出建議顧客返回的時間間隔（time interval）或時間點或時間窗（time window）3.顧客無需排隊，在指定的時間返回就可持票進入http:/ 只是有序的組織了顧客，并沒有減少等待時間v如果能實現(xiàn)知道輪到自己需要等待多少時間，再選擇合適的時間來，豈不很好？http:/ pass真的那么好用嗎？http:/ statistical model），求出最優(yōu)的顧客返回時間。 建模的一般

2、步驟以及：* 模型的改進* 啟發(fā)與待解決的問題http:/ 模型的假設v游樂園開放時間為8:00-18:00,一天中不同時間的顧客流量不同，比如上午10:00和下午3:00的顧客流量是最大的。v顧客的到達時間符合非時間齊次泊松過程(nonhomogeneous possion process)，到達速率是 （t）http:/ processiii( ( ) ),0,1,2.!ktt tekk整數(shù)值的隨機過程n(t),t0是強度為 的poisson過程，如果（i）n(0)=0,(ii)n(t)是獨立增量過程，（） t0,s0,pn(s+t)-n(t)=k=http:/ processexp()i

3、titi顧客到達時間間隔（t）exp( (t)t)t顧客 接受服務的時間（t）和 的確定都將在后面仿真的部分給出http:/ 分析1：能否得到準確的返回時間？ (1. ),1immii1,m+1ii1,m+1如果能夠準確得知前面所有顧客的到達時間間隔t 和接受服務的時間t當然可以知道第個顧客到達就可以馬上接受服務的時間隔t.可現(xiàn)在t 和t都是隨機變量，我們只能用隨機過程的方法，求出t期望值。 2 在我們開始動手建模之前，先要問幾個問題：http:/ 分析2：使用fastpass后排隊是不是可以避免的？vfastpass給出的返回時間只是期望值，而非確定值v假設所有的顧客都使用fastpass,

4、但需考慮有的顧客可能會不遵守fastpass給出的返回時間 2 在我們開始動手建模之前，先要問幾個問題：fastpass2,m+1結論：使用后顧客仍需排隊，但是排隊的時間會大大減少。并設第m+1個顧客排隊的時間是thttp:/ 分析3：我們優(yōu)化的目標函數(shù)（或cost function）是什么？是排隊時間嗎？ 2 在我們開始動手建模之前，先要問幾個問題：1.fastpass1,iw2,i給 出 的 顧 客 i的 等 待 時 間 t太 長 ,同 樣 會 引來 抱 怨 ,并 且 不 能 超 過 公 園 的 開 放 時 間 t2.排 隊 的 時 間 t也 要 考 慮但 是 后 者 引 來 的 抱 怨

5、更 大 ； 而 且 等 待 的 時 間 越 長 ， 抱怨 越 多 .結 論 ： 目 標 函 數(shù) 應 該 是 兩 者 的 時 變 加 權 和 （ time-variantweighted average）http:/ 優(yōu)化問題的目標函數(shù)為： 11221,11,11,1min ( )( ) . .ijiwjiiiwze uc t tc t tttts ttttt公園一天的開放時間3 模型的建立（1）目標函數(shù)http:/ 3 模型的建立（1）目標函數(shù)http:/ theory）的分類規(guī)則,（x/y/z/a）代表一類排隊的規(guī)則，其中 x:顧客流到達所符合的分布 y:顧客接受服務的時間所服從的分布 a

6、z:服務臺的個數(shù) a:服務臺一次可服務的顧客數(shù)量（系統(tǒng)的容量）v針對各個游樂項目的特點，我們主要討論兩種排隊系統(tǒng):模型的建立（2） 排隊模型的分類/1/ / %m mm m c ac電話亭（phonebooth）的隊列模型和過山車（scenic railway）的隊列模型http:/ 電話亭模型http:/ , )1()*nn kkini ktepa *,0;( )0,0.x xxx1,1nnnnjkiattep第n個顧客的返回時間：是第k個顧客可以接受服務的時刻是隊列中的顧客i仍會停留的時間（包括使用系統(tǒng)的時間）http:/ , )0,min ( )( )min()nnnnnn kn kkn

7、 kze uc t tc t tc e tcq tqp nk其中，顧客前有 個顧客在排隊http:/ 2212,1111111,1 ,1 ,1 ,1,11()(.),(1),(), (0 )kkknkkkknkskskksnkkkkkkkkkkkikikikikkkiniqpepaqpeppaqpeppaaaepeepaepqqqqqpae下 面 求 出 狀 態(tài) 轉 換 平 衡 狀 態(tài) 方 程 ：）且模型的建立（3）電話亭模型http:/ 的函數(shù)，并從圖中得出結果模型的求解（4）電話亭模型21 1,22121,221,2()(1()uc tc pttn tt22wttt0( )1,0 xtxt

8、n xedtex 21,2()uthttp:/ call time(min*10) u2 t2508.051617.08023.051632.5http:/ tttptttn tttn ttn ttttpttn ttg tttpptttn ttg tttppttt但是第4個人，第5個人呢？這種方法太繁瑣，似乎不好用可否有近似的算法？http:/ 過山車模型http:/ 系統(tǒng)有兩條隊列：fastpass 和standby隊列v不考慮standby隊列，將得到greedy algorithm模型v考慮standby隊列，將得到效用函數(shù)模型模型的建立（5）過山車http:/ algorithm),將

9、每個顧客盡量安排在離顧客到達時間最近的，且還沒有安排滿人的一班車上。v假設被安排的顧客按照beta分布到達所被安排的時間段內(nèi)模型的建立（5）過山車模型http:/ 如果開車的時間不固定，則a%是多少最優(yōu)？就是說顧客坐滿多少就開車？ 2.如果開車的時間間隔是固定的，則多長時間開一次是最優(yōu)的？v衡量的標準：目標函數(shù)模型的建立（5）過山車模型http:/ 2,2212121212,.()()()()()()kjjiij kkkkkjkjkjkkkjkkkjjkjkkkkkh hhbbbttzzec tc te c tc tc eetc becc ectc bccctcj-1i2,iii個人被安排在中

10、的一班車設i個人的返回時間是則t121)()jjkkkbeccctk常數(shù)， 由 決定，http:/ bckb ，如果開車時坐滿的人數(shù)固定如果開車的時間間隔固定則常數(shù)模型的建立（5）過山車模型怎樣求解最優(yōu)的a%c和最優(yōu)的開車間隔？對于這類復雜的問題，離散仿真是最好的方法了http:/ 2.給定不同的a%c, 開車時間間隔不定，計算代價函數(shù)，畫出代價函數(shù)性能曲線 3.開車時間固定，給出不同的開車時間間隔，計算畫出代價函數(shù)性能曲線 4.得出最優(yōu)的結論模型的仿真（5）過山車模型http:/ 過山車模型的仿真（5.1）得到v在第j天的某一固定時刻 i 采集樣本,i=1m,j=1100形成樣本空間的矩陣1

11、1121,10021222,100,1,2,100. . . . . .mmmlllllllll( ) thttp:/ 過山車模型的仿真（5.1）v 用列向量的均值估計參數(shù)v樣本的更新用時間序列的方法（time serial analysis）,計算列向量的eucilid距離dthreshold就更新一次( )it,1,2,100,. tiiimeanlll21()mkkkdllhttp:/ 對某一個或一組變量x(t)進行觀察測量，將在一系列時刻t1, t2, , tn (t為自變量且t1t2 tn ) 所得到的離散數(shù)字組成序列集合x(t1), x(t2), , x(tn)，我們稱之為時間序列

12、，這種有時間意義的序列也稱為動態(tài)數(shù)據(jù)。時間序列分析是根據(jù)系統(tǒng)觀測得到的時間序列數(shù)據(jù)，通過曲線擬合和參數(shù)估計來建立數(shù)學模型的理論和方法 時間序列分析（time serial analysis）http:/ 過山車模型的仿真（5.1）啟發(fā)：有沒有別的方法判別樣本如何更新？如：求樣本矩陣的秩， 求樣本向量的相關系數(shù)http:/ 個顧客到達時間uniform( ) thttp:/ function是間隔的單調(diào)函數(shù)？怎么辦？過山車模型的仿真（5.4）http:/ 4.67min最優(yōu)過山車模型的仿真（5.4）123456789100.511.522.53x 104cycle interval: minec

13、omomic gains of an amusement item: $average delayeconomic gainaverage delay averhttp:/ 模型的穩(wěn)健性與優(yōu)缺點v電話亭模型較精確，雖可行但復雜v過山車模型的貪心算法，簡單，但不是最優(yōu)（quasi-optimal）（為什么不是最優(yōu)?）vstandby隊列會有什么影響？v每個人的c1和c2可能不同http:/ theory中的erlang c公式，能夠得出阻塞概率p(block)，系統(tǒng)容量c，顧客流的強度a（ ）三者的關系v平均隊列長度為：v可將顧客安排在一天之內(nèi)平均隊列短的時刻7 過山車模型的改進 ( ) t10p(_)!(1)!ckcckablockedgos gradeofserviceaaacck( )prtlblockedathttp:/ c的圖形7 過山車模型的改進http:/ 過山車模型的改進http:/ 過山車模型的改進http:/ 過山車模型的改進統(tǒng)計隊列長度曲線應該實時更新！但是：可能所有的顧客都被安排到同一個隊列長度短的時段了http:/ 過山車模型的改進使用邊際效用函數(shù)(marginal utility function)的思想：fastpass隊列中每增加一個人，會對standby隊列中的人造成目標函數(shù)的損失http:/ 將來的工作：設計更好的fast