排隊系統(tǒng)中的顧客進隊策略分析

韋驍劼

（廣西職業(yè)師范學院，廣西 南寧 530007）

1 排隊論概述

一個排隊系統(tǒng)由隊伍與服務臺構(gòu)成，日常中可視為排隊系統(tǒng)的現(xiàn)象有購物、餐廳等位、交通擁堵、醫(yī)院救護、水庫泄水、飛機起降的調(diào)度、碼頭貨物的裝卸、工廠的流水線生產(chǎn)、網(wǎng)絡(luò)數(shù)據(jù)傳輸。當顧客在排隊時，很自然想到的問題就是“我還需要等多久”“有多少人排在我前面”等等諸如此類的問題。而作為服務系統(tǒng)的管理者，雖然提高服務效率可以減少擁擠，然而過度的提升，會造成資源的浪費，也會加速服務設(shè)備的損耗，所以，管理者會很自然去關(guān)心如何合理的調(diào)整服務臺的服務能力，使之既能滿足顧客的需求，又能最大程度的節(jié)約運營成本。為了解決優(yōu)化顧客與服務臺之間的問題，便發(fā)展出了排隊論這個領(lǐng)域，經(jīng)過了一個世紀的發(fā)展，排隊論的應用已經(jīng)深入各個領(lǐng)域，在交通運輸、倉庫存儲、工業(yè)生產(chǎn)、網(wǎng)絡(luò)數(shù)據(jù)傳輸、計算機系統(tǒng)設(shè)計、自動化技術(shù)、可靠性理論甚至軍事作戰(zhàn)領(lǐng)域都能看到排隊論的身影。

排隊系統(tǒng)的相關(guān)研究最早是在20 世紀初由埃爾朗（A.K.Erlang，丹麥數(shù)學家）研究話務理論開始[1]，他得出了著名的埃爾朗損失率公式并且為排隊理論奠定了基礎(chǔ)。20 世紀30 年代波拉切克（Pollacezk F，法國數(shù)學家）、辛欽（Khinchin A Y，前蘇聯(lián)數(shù)學家）等人也做了許多相關(guān)的工作，得到了一些重要的結(jié)果，比如波拉切克-辛欽公式。20世紀50年代，肯道爾（Kendall D G，英國數(shù)學家）使用嵌入馬氏鏈方法進一步奠定了排隊系統(tǒng)的理論基礎(chǔ)，比如在M/G/1 與GI/M/1 排隊系統(tǒng)中，嵌入點分別是顧客的離去時刻與到達時刻。除了嵌入馬氏鏈方法，學者們還運用許多其他方法對排隊系統(tǒng)進行研究，比如積分方程方法、補充變量法、向量馬氏過程方法、矩陣幾何方法。

在排隊論中，最經(jīng)典的模型是M/M/1 排隊系統(tǒng)，學者們不僅研究了該系統(tǒng)的平穩(wěn)性態(tài)，還得出了瞬時性態(tài)的結(jié)果。雖然泊松輸入這個假設(shè)在實際情況中不一定能成立，比如去食堂吃飯的學生大都集中在下課之后，這就不滿足平穩(wěn)性的假設(shè)，又比如去食堂吃飯的學生往往是三兩成群，這就不滿足普通性的假設(shè)，還有就是如果某個學生覺得這個食堂的菜比較好吃，那么下次他極有可能再來這個食堂吃飯，這就不滿足獨立增量性這個假設(shè)。然而，泊松輸入過程仍可以看成是實際情況相當程度上的近似。隨著研究的深入，科學家們還考慮了其他情形更為一般排隊模型，并且都得到了瞬時性態(tài)的相關(guān)結(jié)果。比如GI/M/1 型排隊系統(tǒng)、離散時間排隊系統(tǒng)、GI/M/n 型排隊系統(tǒng)、GI/G/1型排隊系統(tǒng)。

同時，還有許多具有特殊排隊規(guī)則的排隊系統(tǒng)也被科學家們深入的研究，比如帶負顧客的排隊系統(tǒng)、重試排隊系統(tǒng)、帶中途止步的排隊系統(tǒng)、具有伯努利控制策略的排隊系統(tǒng)。

對于一個排隊系統(tǒng)，人們主要關(guān)心的性能指標是：

等待時間：指的是從顧客到達開始直到接受服務的這段時間。

逗留時間：指的是等待時間加上顧客被服務的時間，也就是從到達開始直到離開隊伍的這段時間。

系統(tǒng)隊長：指的是系統(tǒng)中的顧客數(shù)，包括正在排隊的顧客和正在接受服務的顧客。

忙期：指的是從服務臺開始工作直到把系統(tǒng)中的顧客全部服務完畢的這段時間。

閑期：指的是從服務臺將顧客全部服務完畢開始直到下一次開始工作的這段時間。

忙循環(huán)：指的是相鄰兩次忙期的開始時間的間隔。

還有一個重要的指標是排隊系統(tǒng)的服務強度，定義如下：

假設(shè)某個排隊系統(tǒng)的顧客到達間隔的分布函數(shù)為A(x)，服務時間的分布函數(shù)為B(x)，記為公式（1）。

公式（2）稱為服務臺的服務強度。在許多排隊系統(tǒng)中，ρ＜1 是排隊系統(tǒng)平穩(wěn)的條件。

在經(jīng)典排隊系統(tǒng)中，服務臺的服務率不會隨時間變化，這明顯與現(xiàn)實有著較大的偏差。比如生產(chǎn)工具的磨損會使生產(chǎn)效率降低，又比如由于交通擁堵導致路口的通過率下降。為此，研究者們在排隊系統(tǒng)中引入了休假機制，這里的休假除了傳統(tǒng)意義的“休假”外，也可以是在當前排隊系統(tǒng)不繁忙時，服務臺以較低的服務率來為顧客提供服務或者去從事另外一項服務工作，這被稱為工作休假。

自從20 世紀70 年代，學者們首先對M/G/1 休假排隊系統(tǒng)做了初步研究，此后休假排隊系統(tǒng)立刻成為排隊論的研究熱點。庫柏（Cooper R B）、哈里斯（Harris C M）等人利用隨機分解手段并且做了大量的研究工作后，逐步完善了休假排隊理論，田乃碩等首次利用矩陣幾何方法來對休假排隊系統(tǒng)研究，進一步推進了休假排隊論的發(fā)展。直到2022 年，工作休假的概念才被提出，隨后便引起了學者們的極大興趣，大量關(guān)于工作休假排隊系統(tǒng)研究工作就此展開。

與經(jīng)典排隊模型不同，在描述休假排隊系統(tǒng)時，還要加入休假策略來進行描述。所謂休假策略，指的是觸發(fā)休假的條件和休假結(jié)束的規(guī)則。一般來說，觸發(fā)休假的條件有兩類：第一類是當服務臺忙期結(jié)束時立刻開始休假，被稱為空竭服務；另一類是雖然系統(tǒng)中仍有顧客排隊但也可以開始休假，被稱為非空竭服務[2]。而常見的休假結(jié)束的條件有：

N 策略：當系統(tǒng)中排隊顧客數(shù)到達指定數(shù)量N 時，服務臺休假結(jié)束。

啟動時間：當有新顧客到達系統(tǒng)時，服務臺需要經(jīng)歷一個隨機時長的啟動期。

單重休假：服務臺只進行一次休假，若休假結(jié)束時有顧客到達系統(tǒng)，則正常為顧客提供服務，若休假結(jié)束時仍無顧客到達，則進入閑期。

多重休假：服務臺可進行多次休假，具體地說，若一次休假結(jié)束時系統(tǒng)中仍無顧客到達，則開始另一次獨立同分布的休假，直到某次休假結(jié)束時系統(tǒng)中已有顧客在等待。

此外，還有許多休假策略的組合所形成的策略，比如N 策略多重休假，啟動期單重休假等。

2 排隊經(jīng)濟學概述

當顧客到達某排隊系統(tǒng)時，根據(jù)隊伍長度信息與服務臺狀態(tài)信息的不同組合，可將系統(tǒng)的信息水平分為四類：完全可見、幾乎可見、幾乎不可見以及完全不可見。排隊經(jīng)濟學主要的研究目的是利用排隊系統(tǒng)的相關(guān)指標來構(gòu)建顧客和社會的收益函數(shù)，在考慮隊伍長度以及服務臺狀態(tài)的前提下給出顧客的均衡進隊策略和使得顧客和服務商的總收益達到最大的策略，即社會最優(yōu)策略（顧客與服務商之間的利益轉(zhuǎn)換不計入其中）。

在經(jīng)典的排隊理論中，顧客是被動接受服務的一方，無法主動做出決策。然而事實上，顧客會根據(jù)風險偏好、收支結(jié)構(gòu)等因素，在處于不同的信息程度的條件下來做出自己滿意的選擇，最常見的就是顧客會考慮何時選擇止步或者進隊或者中途退出。而對于服務系統(tǒng)的管理者而言，由于提供服務的成本，他們需要控制客流量或者對顧客收取一定的費用。總之，顧客和管理者在決策的同時都必須把對方的行為考慮進去，于是就形成了雙方的博弈。同樣的，顧客與顧客之間也存在著博弈，比如排位靠前的顧客所做的決策可能會對后到的顧客產(chǎn)生影響。于是，越來越多的學者開始運用博弈論對于有顧客個體特征的排隊系統(tǒng)進行研究。

最早的一篇基于博弈論的排隊經(jīng)濟學文獻是Naor[3]關(guān)于M/M/1 排隊經(jīng)濟學模型的研究，并給出了在隊伍長度及服務臺狀態(tài)可見時的顧客進隊策略和社會最優(yōu)策略，并且發(fā)現(xiàn)顧客為了追求個人最優(yōu)，會對系統(tǒng)造成擁堵，于是提出需要對顧客征收一定的費用來保證社會收益最大化。而后侯賽因、拉森及內(nèi)勒巴夫等學者對該模型進行了一系列的拓展。斯迪達姆研究了更一般的GI/M/1 排隊模型，值得一提的是在大部分文獻中，顧客經(jīng)過服務后所獲得的回報一般假設(shè)為常數(shù)R，而在斯迪達姆的文獻中，顧客經(jīng)過服務所獲得的回報被假設(shè)為一個隨機變量，同樣的假設(shè)出現(xiàn)在米勒和巴克曼的文獻中。除了上述經(jīng)典排隊模型，具有特殊排隊規(guī)則的排隊模型也被深入的研究。比如可修排隊系統(tǒng)、有優(yōu)先權(quán)的排隊系統(tǒng)、重試排隊系統(tǒng)。

2007 年學者們開始對休假排隊系統(tǒng)中的排隊經(jīng)濟學問題進行研究，博內(nèi)塔斯與伊科諾穆在M/M/1 模型中加入了啟動機制，并得出了在不同信息下的顧客進隊策略，田乃碩、郭鵬飛等對該模型進行了推廣，加入了啟動可中斷的條件。隨后又有學者們提出了新的模型，他們引入了N 策略機制，即當系統(tǒng)中有N 名顧客排隊時服務臺便結(jié)束休假，同樣得出了不同信息水平下的顧客進隊策略，伊科諾穆、戈麥斯和坎塔考慮了M/G/1 多重休假排隊系統(tǒng)，得出了在隊伍長度不可知時的顧客進隊策略和社會最優(yōu)策略。另外，對于工作休假排隊經(jīng)濟學模型的研究，成果如下：在單重工作休假的Geo/Geo/1 模型下，得出了在隊伍長度及服務臺狀態(tài)都可知與都不可知情形下的顧客進隊策略；更進一步地，考慮在服務完工作休假期中進入的第一名顧客后，如果仍有顧客在排隊，則以某個正概率中斷工作休假；如果沒有顧客在排隊，則繼續(xù)工作休假的在休假可中斷的Geo/Geo/1 工作休假模型下，得出了隊長與服務臺均可知、隊長可知但服務臺狀態(tài)不可知與隊長及服務臺狀態(tài)均不可知情形下的顧客進隊策略與社會最優(yōu)策略；在多重工作休假的M/M/1 排隊模型中，給出了所有信息水平下的顧客進隊策略與社會最優(yōu)策略。在批量到達的GI/M/1 單重和多重休假排隊系統(tǒng)中，分析了隊伍長度與服務臺狀態(tài)均可見與隊伍長度不可知但服務臺狀態(tài)可知下的顧客進隊策略以及隊伍長度及服務臺狀態(tài)均不可知情形下的社會最優(yōu)策略。

3 一類排隊系統(tǒng)中顧客的進隊策略

考慮一個M/M/1 排隊系統(tǒng)，并在該排隊模型中加入啟動機制及N 策略，即當系統(tǒng)中無人排隊時，服務臺開始休假期，不再提供服務，直到系統(tǒng)中有N 名顧客時時，服務臺開始進入一個時長服從指數(shù)分布的啟動期[4]。隨后服務臺開始工作直到系統(tǒng)再次變空。引入啟動機制與N 策略具有很現(xiàn)實的應用背景，比如當水位到達一定高度時，水庫才開始開閘泄洪，又比如大巴車需要等到滿座才發(fā)車。進一步地，假設(shè)每名顧客都是風險中立的，并且顧客一旦選擇進隊就不允許退出，而選擇止步的顧客則不允許再次進入隊伍。顧客在被服務完畢后可獲得的回報為常數(shù)R，逗留期間每個單位時間的等待費用為常數(shù)C。同時，為使系統(tǒng)為空時顧客選擇進隊，應有回報R 大于該顧客的總等待費用。

先考慮在完全可見情形下的顧客進隊策略，此時顧客知道排隊人數(shù)以及服務臺處于休假期、啟動期還是正在工作。作為顧客而言，一個最直觀的想法就是根據(jù)排隊人數(shù)來決定是否進入隊伍，因此可以選擇閾值策略，即顧客根據(jù)服務臺的不同狀態(tài)來選擇進入隊伍的不同閾值。顧客發(fā)現(xiàn)服務臺在休假且有n 人排隊，若n＜n_0，則選擇進隊，否則止步；顧客發(fā)現(xiàn)服務臺在啟動且有人排隊，若n＜n_1，則選擇進隊，否則止步；顧客發(fā)現(xiàn)系統(tǒng)在工作且有n 人排隊，若n＜n_2，則選擇進隊，否則止步。顯然，在服務臺休假時到達的顧客必然會選擇進入隊伍。而對于處于啟動期與工作期的排隊系統(tǒng)，根據(jù)閾值策略可求得：

根據(jù)以上分析有如下結(jié)論：在完全可見情形下，策略“若顧客發(fā)現(xiàn)系統(tǒng)在休假則必然進隊；顧客發(fā)現(xiàn)系統(tǒng)在啟動期且排隊人數(shù)少于則選擇進隊，否則止步；顧客發(fā)現(xiàn)系統(tǒng)在工作且排隊人數(shù)少于則進隊，否則止步”唯一的均衡策略。

接下來進一步地考慮在幾乎可見情形下的顧客進隊策略，此時顧客知道排隊人數(shù)但不知道服務臺處于休假期、啟動期還是正在工作，與完全可見情形完全類似，顧客很自然地會根據(jù)隊伍人數(shù)來選擇是否進隊，因此仍然考慮選擇閾值策略，即：顧客發(fā)現(xiàn)系統(tǒng)中有n人排隊，若n＜ne，則選擇進隊，否則止步。此時，可列出平衡方程，進而得出系統(tǒng)的穩(wěn)態(tài)概率。更進一步的，由穩(wěn)態(tài)概率可列出關(guān)于收益的函數(shù)，經(jīng)過一系列分析可得出結(jié)論：在幾乎可見情形下，對于具有啟動期及N策略的M/M/1 排隊系統(tǒng)，存在正整數(shù)K1、K2(K1＜K2)使得進隊閾值ne∈[K1,K2]，并且策略“若排隊人數(shù)n＜ne，則顧客進隊；否則，顧客止步”是均衡策略。[5]

在R=25，C=1，N=5，λ=0.5，μ=1，θ=0.1 時的系統(tǒng)收益函數(shù)圖像，經(jīng)過計算可知K1=16，K2=19。這就是說對于該排隊系統(tǒng)而言，當隊伍長度為16 至19人時，均可選擇進隊，但是當隊伍長度至少為20 人時，就應該止步。