Ｍ／Ｍ／１服務系統的動態控制

摘要：以不同的價格服務于多種類型的顧客并基于顧客需求動態地分配能力是服務系統面臨的一大難題。文章以M/M/1服務系統為例，借助于最優化方程的方法，從速率設定和價格設定兩個方面得到使服務系統實現福利最大化的到達速率和服務速率。文章指出，此時的系統本質上相當于一個擁有有限緩沖數目的服務系統。

關鍵詞：M/M/1服務系統；動態控制；馬爾可夫過程

一、 引言

面對急劇變化的市場環境和日益激烈的市場競爭，當今普遍認為動態控制成本和價值的能力能夠給企業運作帶來明顯的競爭優勢。“基于需求的計算”（Computing on Demand）即體現了此戰略，意指一個公司依據經驗的或預期的需求，從另一個公司購買服務時間、存儲空間或處理能力（或以上的一個組合）， 而不是投資于一個固定的產能、組織內的計算基礎設施。這一戰略使得公司能夠迅速地將計算能力調整到使用的峰值， 同時又能將IT開支保持在相當低的水平。“基于需求的帶寬”（Bandwidth on Demand）是動態成本控制戰略的另一個實例，是指企業與互聯網服務提供商之間簽訂一個靈活的帶寬合約，而不是外包一個固定的帶寬，這樣就使得企業可以隨時改變對帶寬的需求，并基于真實的用量進行支付。動態能力（成本）控制在IT服務中相當容易落實， 因為變動分配給一個顧客的計算能力（“基于需求的計算”）或變動顧客的帶寬需求（“基于需求的帶寬”）只會引致較低的安裝和邊際成本。但近年來， 靈活運作的戰略在較傳統的行業中也越來越明顯。

在所有動態成本和價值控制可行的環境中，關鍵的采納決策是在潛在收益、 成本和實施的復雜性之間進行權衡。管理一個服務設施本身是一件復雜的事情，而使這一設施以不同的價格服務多種顧客類型并基于顧客需求動態地分配能力是一件更具挑戰性的工作。本文即將為應對這一挑戰提供一些見解。

二、 理論基礎

“擁塞定價”（Congestion Pricing）理論作為動態控制的一塊理論基石，從靜態角度決定服務速率和定價，該理論由Naor（1969），Mendelson（1985），Dewan和Mendelson（1990），Mendelson和Whang（1990），Westland（1992）以及其它學者提出。他們提供了一類服務系統模型，在該類模型中，請求服務的顧客是理性的、效用最大化且對延遲敏感的決策者。例如，Mendelson（1985）、Dewan和Mendelson（1990）研究了一個組織的內部服務設施，在這個組織中，系統經理在不同的延遲成本結構下設置價格和容量以最大化福利。但他們研究的控制都是靜態的，即在任何實際被觀察到之前基于平均績效估計，同時做出服務速率和定價決策，之后不再更改。Naor（1969）模擬了一個固定容量服務系統，在這個系統中，到達的顧客在決定是否進入排隊之前觀察隊伍的長度。然而，所提出的旨在最大化福利或收入的系統費用是靜態的。即，它們不依賴于系統的狀態。Mendelson（1985）也提供了一個框架來模擬對價格和延遲都敏感的顧客的行為。

“排隊系統的動態控制”在過去30多年中已經由運作研究文獻廣泛研究（參見Stidham，1988，2002中的調查）。尤其值得一提的是George和Harrison（2001）研究了系統經理動態選擇服務速率以最小化長期平均成本但對顧客的到達速率不施加控制的馬爾可夫排隊系統。Low（1974），另一方面，在一個擁有有限緩沖數目、系統經理通過價格控制到達速率而對容量水平不施加任何控制的馬爾可夫排隊系統中研究了最優控制。到達的顧客是獨立且理性的決策者，他們觀察由系統經理設定的價格并基于凈效用來決定是否參與到排隊中來。系統經理設定價格的目標是最大化由服務顧客而獲得的長期平均收益。結果表明，由系統經理公示的最優價格是系統中顧客人數的非減函數。

Masuda和Whang（1999）在一個固定容量的通訊網絡中研究了動態定價控制問題，在這一網絡中系統經理希望最大化福利且顧客是延遲敏感型的。作者假設系統經理對于需求曲線具有有限信息，并使用觀察到的系統績效作為定價公式的輸入信息。他們發現，最大化社會福利的解決方案是一個均衡，并證實不穩定問題的出現正是由于系統可能從未達到所期望的均衡。

Paschalidis和Tsitsiklis（2000），Paschalidis和Liu（2002）研究了服務多種顧客類別的通訊網絡中的動態定價問題。在他們的模型中，服務提供商設置的價格可能依賴于擁塞的水平， 但網絡容量是固定的且網絡如損耗網絡（Loss Networks）一樣運行。在這一背景下，作者證實了最優動態戰略的績效與適當選擇的類型依存的靜態定價之間具有高度匹配關系。

Yoon和Lewis（2004）沿著另一個有趣的方向探討了動態定價和準入控制問題。他們研究了到達速率和服務速率非靜態且顧客為價格敏感的問題，并論證了最優策略的幾個結構性特征，包括：在不同的成本結構下，最優價格隨系統狀態呈單調特性。他們還提出了對最優動態策略的一個實際的逐點靜態近似估計（Pointwise Stationary Approximation）的方法。

Maglaras和Zeevi（2003）利用大容量近似（Large Capacity Asymptotics）的方法解決了在流量高峰期使用共享資源的系統所面臨的聯合靜態定價和容量規模問題。

Ata和Shneorson（2006）的研究結合了George和Harrison（2001）及Low（ 1974）的模型， 他們將Mendelson（1985）、Dewan和Mendelson（1990）對于價值和成本因素的雙重控制問題一般化到動態的環境中去，證實了最優價格不需要隨著系統狀態呈現單調的特性，利用動態策略獲得的福利相比靜態策略更顯著。

本文以M/M/1排隊系統為例， 在Ata和Shneorson（2006）的研究基礎上，探討當到達速率和服務速率可調節情況下M/M/1排隊系統的動態控制問題。毫無疑問，在大多數的現實案例中，服務設施排隊系統的動態性比M/M/1排隊系統更加復雜。然而，由于這一程式化的馬爾可夫模型的易處理性，在本文分析中使用這一模型可以作為現實系統的一個良好近似。盡管M/G/1可能是一個更好的模型，但它經不起動態的分析。M/M/1模型可能無法刻畫系統行為的所有方面， 但它可以捕捉到與“擁塞”（Congestion）相關的現象的許多方面。更進一步說，使用這一模型能夠清晰刻畫最優策略，了解它們的主要特性，并評價落實這一動態策略的凈增值。

三、 速率設定問題

“生滅過程”（Birth—Death Process）是馬爾可夫過程（Markov Process）的一個特例，在這一過程中，從狀態Ek只能轉換到相鄰的狀態Ek+1、Ek和Ek-1。通常引入“出生率”和“滅亡率”的概念，并記為和λk和?滋k，k表示人口數量。M/M/1隊列是一類簡單但非常重要的系統，在這一系統中，出生率λk和滅亡率?滋k分別被定為常數λ和?滋（對于k=0，1，2，…）。

系統經理選擇?滋n和λn，n為系統狀態， 即隊伍長度n如生滅過程一般演化，該過程的到達速率為λn，服務速率為?滋n。給定三個函數： c（?滋）是與服務速率相關的成本發生速率； b（λ）是與到達速率相關的價值生成速率；在系統狀態為n時，系統經理在單位時間內引致一個滯留成本hn，它與價格設定問題中顧客招致的延遲成本相對應，滯留成本與系統中顧客人數呈線性關系。系統經理的問題是以一個無限期的規劃視野來選擇一個單位時間內最大化長期平均社會福利的策略（λ，?滋）。

以上是速率設定問題中目標函數的構造，證明以上候選策略是可采納的且可采納的策略是最優的方法多種多樣，其中之一是考察最優化方程的相關系統，使最優化方程的形式適用于半馬爾可夫（Semi—markov）決策過程，在其中加入長期平均成本尺度， 再使用一致化技術（Uniformization Technique）（參見Bertsekas，1995），構造相對價值函數vn，之后定義相對價值之差，再將最優化方程轉換成最大平均價值估計函數。

最后推導出來的最優結果為如下形式：對所有n?叟N，有λn=0（對n?叟N+1，有 ?滋n=M），其中N代表“最優的緩沖數目”，它是在推導候選策略（Candidate Policy）的過程中唯一被確定的。

四、 價格設定問題

在價格設定問題中， 系統經理控制服務速率和價格，但不能直接控制到達速率。系統經理選擇服務速率和價格的目標和速率設定問題中一樣——最大化長期平均福利。福利被定義為從服務中獲得的收益減去容量成本，再減去延遲成本，這一延遲成本相當于速率設定問題中的滯留成本。因此，系統經理的目標是協調系統實現?酌*≡sup?酌λ，?滋中定義的?酌*。為了做到這點，可以構造系統經理應該設定的最優狀態依存的價格和容量（p*，?滋*）以誘使速率設定問題中最優化λ*和?滋*的產生。

由系統經理設定的價格對應于顧客為每份提交的待處理的服務請求而支付的費用。這些價格是狀態依存的。顧客在到達設施的時候支付公示的價格，這一價格不依賴于他們經受的真實等待時間。特別地，在系統的每一個狀態n時，系統經理都必須設定服務速率?滋n和價格pn，同時還要公示真實的系統期望等待時間。然后，理性、效用最大化且對延遲敏感的顧客觀察這一服務的價格和公示的期望延遲來決定是否提交他們的服務請求。很明顯，為了引致最優的服務速率，系統經理選擇速率設定問題中的服務速率?滋*。但為了找到最優的價格，有必要發展出顧客行為的模型。

在不存在延遲的情形下，顧客獲得服務時會得到一個正的價值。假設顧客的服務價值是從一個連續分布函數F中抽取的獨立同分布，對應的概率密度函數為f，b（λ） 代表總的網絡價值生成速率。請求服務的顧客是延遲敏感型的，單位時間延遲引致v單位的顧客負效用。狀態n時，期望的系統延遲為Dn，它是請求到達速率λ、服務速率?滋、服務所需時間分布的函數。

當系統中已經有n位顧客時，為了推（下轉第50頁）（上接第47頁）

導一位新到達顧客的凈效用，必須從顧客的總效用中減去他為服務所支付的價格pn和他的期望延遲成本v·Dn+1。因此， 當系統中已經有n位顧客時， 邊際顧客的期望凈效用為b′（λn）-pn-v·Dn+1，只要凈效用為正，顧客就選擇提交服務請求。因此，當到達速率 λ*和服務速率 ?滋*給定時， 狀態n時的最優價格為：

pn*=b′（λ*）-v·D*n+1，n=0，…，N-1

為了最大化價格設定中的福利，系統經理利用函數b（g）、c（g）和線性滯留成本hn=vn解決了速率設定問題。記所得的最優策略為（λ*，?滋*），系統經理直接將服務速率控制策略?滋*運用于系統中，然而，不同于速率設定問題的地方在于，系統經理只能通過公示的價格和期望延遲來間接控制或誘導出最優化的到達速率λ*。

五、 結束語

本文研究結果顯示，為了對服務設施中到達速率和服務速率實施動態控制，可構造最大化長期平均系統福利的目標。這一方案可以用來解決最優動態價格和系統經理應該設定的服務速率問題，前提是所服務的顧客是延遲敏感且理性的。遵循這些前提，對于一個在最優到達速率和服務速率上運行的系統來說，實質上僅需要一個由最優化方法得出的有限緩沖數目。

在本文中，假定顧客對于系統狀態具有完全的信息，或者大體上在他們做出是否提交服務請求時對于期望的延遲具有完全信息。但顧客對于當下系統負荷易產生誤解，研究這類顧客是否使得系統經理的經濟狀況變得更好是非常有意義的；在顧客擁有對系統狀態的個人信念的情況下，是否不真實的戰略會成為可持續的均衡；最后，將戰略性顧客也吸納進模型，這些顧客寧愿推遲進入系統時間，對于豐富這類研究也大有裨益。

參考文獻：

1．Baris，Ata．，Shiri Shneorson．Dynamic Contr- ol of an M/M/1 Service System with Adjustable Arrival and Service Rates．Management Science，2006，52（11）：1778-1791．

2．Maglaras，C．，A．Zeevi．Pricing and capacity sizing for systems with shared resources：App- roximate solutions and scaling relations．Manag- ement Science，2003，（49）：1018-1038．

3．Masuda，Y．，S．Whang．Dynamic pricing for n- etwork service：Equilibrium and stability．Manag- ement Science，1999，45（6）：857-869．

4．Mendelson，H．Pricing computer services：Que- ueing effects．Comm．Assoc．Computer Machinary，1985，（28）：312-321．

5．Mendelson，H．，S．Whang．Optimal incentive- compatible priority pricing for the M/M/1 queue．Operational Research，1990，38（5）：870-883．

6．Naor，P．The regulation of queue size by- levying tolls．Econometrica，1969，37（1）：15-24．

7．Paschalidis，I．Ch．，Y．Liu．Pricing in mult iservice loss networks：Static pricing，asymptotic optimality，and demand substitution effects．IEE- E/ACM Trans．Networking，2002，10（3）：425-438．

8．Paschalidis，I．Ch．，J．N．Tsitsiklis．Cong- estion-dependent pricing of network services．IEE- E/ACM Trans．Networking，2000，8（2）：171-184．

9．Stidham，S．Analysis，design，and control of qu- eueing systems．Operational Research，2002，50（1）：197-216．George，J．M．，J．M．Harrison．Dynamic con- trol of a queue with adjustable service rate．Op- erational Research，2001，49（5）：720-731．

10．Yoon，S．，M．E．Lewis．Optimal pricing and admission control in a queueing system with peri- odically varying parameters．Queueing Systems，2004，47（3）：177-199．

基金項目：中山大學“985”工程二期“區域經濟協調發展與產業結構”專項基金資助。

作者簡介：錢錫紅，中山大學嶺南學院管理科學與工程專業博士生；徐萬里，中山大學管理學院企業管理專業博士生。

收稿日期：2008-05-05。