共享平臺下基于閾值的占線任務分配策略

代文強, 章瀟月, 姜玉琦

(電子科技大學經濟與管理學院,四川成都 611731)

1 引 言

隨著互聯網時代的來臨,信息技術不斷加強,共享經濟作為一種新型的經濟模式越來越受到人們的關注. 根據中國國家信息中心頒布的《中國共享經濟發展年度報告(2020)》,2019 年我國的共享經濟交易規模達到32 828 億元,與2018 年相比增長了11.6%,并且預計至2022 年,我國共享經濟的年均增幅將會繼續維持在15%左右[1]. 共享經濟是用戶在不擁有資源的情況下訪問和共享他人資源,從而提高資源利用率的新型商業模式,其本質是以獲得一定報酬為主要目的,基于陌生人且存在物品使用權的暫時轉移[2]. 在這其中,共享平臺作為連接資源需求方與供應方的橋梁,起著基礎性的作用. 目前研究共享經濟的文獻中,只有較少一部分從共享平臺企業運營角度開展研究,已有的研究也大多都是進行定性研究,缺乏對平臺的定量化研究[3]. 并且共享平臺上的需求任務到達信息相當復雜,使得平臺定量化研究更加困難.因此本文主要聚焦平臺的定量化研究,從平臺的角度出發,研究如何將需求進行實時合理分配給現有的資源以使得平臺收益達到最優.

在現有針對共享平臺的定量研究中,大多數是將其轉化為設施規劃問題.例如,以共享車輛平臺為例,He 等[4]研究了單向電動汽車共享系統服務區域設計的戰略規劃問題,制定了一個綜合服務區規劃模型,考慮了用戶在采用服務時的滿意行為以及單向電動汽車共享系統的各種運行特性. Shu 等[5]提出了具有比例限制的網絡流模型用以描述網絡內自行車的周期性流動,并由此建模并分析了共享自行車的布局與再分配優化問題.Mak 等[6]提出了魯棒優化模型用以研究并求解共享電動車公司電池交換基礎設施優化選址問題.除共享車輛平臺外,最近王海燕等[7]研究了醫聯體信息共享過程中平臺運營商的最優收費定價策略以及三級醫院、社區醫院的參與決策和付費方式選擇策略.可以看出已有的文獻大多研究需求模式已知的條件下的路徑規劃問題或者平臺定價問題.而本文研究的是在需求未知的情況下,平臺方如何實時對需求進行分配以滿足利潤最大化的問題.

共享平臺的一個典型特征是未來需求到達信息往往呈現高度不確定性. 以往針對信息不確定的建模,常用的建模思路是假設隨機分布或隨機過程的條件下尋求平均意義上的最優解. 但是,網絡平臺上的需求任務信息變化復雜,決策者往往并不能假設未來需求服從某種隨機分布或隨機過程. 以往文獻假設的某種隨機分布或隨機過程的條件一旦發生變化,其給出的最優方案就會失去最優性. 近年來受到管理學界廣泛關注的占線(online)問題和競爭策略(competitive strategy)的方法能夠很好地處理動態特征較強的問題,其針對變化因素的每一個特例都能給出一個方案,并使得這一方案所給出的平臺收益離決策者在已知該特例輸入下的最優方案得到的平臺收益總在一定的比例之內,因此能夠避免傳統的靜態優化方法所得到的結論對初始假設依賴強的弊端[8-14].

就理論上來說,可以將本文研究的問題視作無任務優先權的占線區間排序問題.在以往研究占線區間排序問題的文獻中,大多都考慮任務具有優先權[15]. 但在共享經濟背景下,往往不能假設任務優先權的存在.已有一些學者研究了無任務優先權的占線區間排序問題,例如Boyar 等[16]在火車票保留背景下研究了占線區間排序問題,因此其可行集是若干離散集合,Gupta 等[17]研究了運輸行業中的占線區間排序問題,設計了相應的分配策略.關于區間排序的綜述性文獻和進一步的研究,可以參考文獻[18,19].

同以往的研究相比,本文的貢獻在于不僅考慮了共享平臺供應方服務時長的差異性,并且結合實際,考慮平臺的收益規則包含每單固定價格和單位可變價格,建立了共享平臺下實時占線任務分配模型,在滿足不確定需求的條件下盡可能最大化平臺收益.為了盡可能地讓服務器服務具有較長持續時間的需求,引入閾值參數的概念,在此基礎上給出了占線任務分配策略并證明了競爭性能比.本文不假設需求具有任何分布信息,因此可以彌補以往相關研究假設性太強的缺陷,同時本文也是現有占線問題研究的有益補充,具有重要的理論意義和實踐價值.

2 占線任務分配模型

2.1 模型描述

首先針對共享平臺下服務器及任務需求的概念進行簡要的描述. 共享平臺下某時刻可同時使用的資源數量稱為服務器,記n代表該時刻可同時使用的服務器數量,每個服務器i的可持續服務時間被限制在一定值內,且每個服務器一次只能處理單個需求任務.以L表示需求任務的有限非空序列,需求一個個到達,對于某需求j,其開始時間用tj表示,需求持續時間長度為dj. 設最小可能需求時間長度為Dmin＞0,最大可能長度為Dmax＜+∞. 注意當需求j到達時,決策者只能觀察到dj及之前的需求信息,dj之后的需求信息不可觀察且無法預測. 記D=[Dmin,Dmax],并設需求L的集合為L(D),同時定義Δ=Dmax/Dmin.

當需求j到達時,平臺的決策者必須在不知道未來需求信息的情況下立即做出決策,根據系統中存在的可服務的服務器決定將該需求分配給哪臺服務器. 決策一旦做出便立即執行,且無法更改.此外,若需求k和需求l同時滿足tk≤tl和tk+dk ＞tl,則稱需求k和需求l是重疊或沖突的,顯然其不能分配給同一個服務器. 令s為每單需求為平臺帶來的固定收益,單位可變收益設為1,其中比例為p(0＜p ＜1)的部分是平臺的收益抽成.因此,平臺的收益可以表示為π=sm+pm∑i=1di,其中m為已接受需求的數量. 此外,為計算方便定義f=s/Dmin. 由于p是一個固定的常數,為便于描述,通過對收益函數的適當處理可將其等價地轉化為p=1.

2.2 競爭性能比

為了證明研究問題的競爭性能比,首先提出以下定義.

定義1 給定兩個集合B和C,定義集合B到集合C的分配方案ω:B×C →R+滿足

對于共享平臺下的任務分配問題,只要針對不同的問題特征設計相應的占線策略,再構造滿足式(1)的分配方案,即可根據定理1 得到相應的競爭比. 在下面的分析中,將利用定義1 與定理1 證明本文設計的策略具有較好的競爭性能比.

3 任務分配策略及競爭性能分析

3.1 任務分配策略

本文是從共享平臺的角度出發考慮如何分配任務需求使得平臺收益最大化. 由于在一定條件下,需求的持續時間越長,給共享平臺帶來的收益越大,故引入閾值的概念盡可能的讓服務器服務較長持續時間的需求. 首先給出如下閾值的定義.

定義2 每個服務器i存在一個可接受服務時間的最低值?(i)(即閾值),當需求j的持續時間dj大于等于?(i)時,需求j對于服務器i來說才是可指派的.

基于上述閾值的概念,一個簡單的占線任務分配策略A 可以設計為如下步驟:

在豐富多彩的數學教學活動中，如果教師能把進行法制教育的方法、時機掌握恰當，運用靈活，對提高學生的思想覺悟、抵制心靈污染，定會收到良好的效果。數學教材中蘊含著極其豐富的育人因素，其中“綜合與實踐”板塊，既能幫助學生回顧某一單元的知識網絡，又能綜合檢測學生的實踐能力，同時我們也可結合切入點對學生滲透法治教育。例如，在教學“繪制校園平面圖”時，學生通過測量、計算，最終繪制出校園平面圖，不僅掌握了相關知識，提高了動手能力，還可滲透《中華人民共和國地圖條例法》。在教學年月日，讓學生繪制年歷表時，對學生滲透《全國年節及紀念日放假辦法》、《中華人民共和國勞動法》。

步驟1 按照服務器的可持續工作時間對當前系統中存在的可用服務器進行排序,并按照可持續工作時間從短到長的順序分別編號為1,2,...,n,當用戶需求信息到達時,按照編號順序將其分配給服務器,注意需求與服務器一一對應,不能重疊或沖突.

步驟2 分配給需求j的服務器i必須滿足不等式dj≥?(i),即需求的持續時間必須超過所分配服務器的閾值,否則就釋放該需求,需求重新進入需求序列并重復進行步驟1 和步驟2,直到策略推薦出合適的服務器.

在上述策略中,核心是閾值的設計.根據以下定義計算閾值?(i).

定義3 令服務器i的閾值為?(i),則?(i)的計算方式如下

其中t(n,y)和I為中間計算式. 上述?(i)的定義中以服務器的數量n和Δ作為參數輸入,后續的推導也將根據n和Δ的取值分情形討論.為了后面分析競爭性比方便,首先給出以下的結構性質.

引理1 給定一個需求序列L,令根據策略A 所確定的需求集合為BL,離線最優方案所確定的需求集合為CL,那么有以下三個論述:

1)若n=1,?b ∈BL∩CL,每個需求任務b除了自身,不會和集合CL重疊.同樣的,?c ∈CL∩BL,每個需求任務c除了自身,不會和集合BL相重疊.

3)如果Dmax＞Dmin,?b ∈BL,與BL重疊的CL的總區間長度(服務時間)嚴格小于n(2Dmax+db).

證明 1)此時集合BL和CL均不包含重疊需求,因此論述1 成立. 對于2)若需求序列L已知,則集合CL里的需求也為已知,假設集合CL可以被劃分為n個子集,而且每個子集只包含不重疊的需求. 在該情形下,因為所有需求任務的長度都相等,則集合BL中的每個需求任務最多與集合CL每個子集中的2 個需求任務相重疊.即BL最多和CL中的2n個需求相重疊.3)同理,假設集合CL可以被劃分為n個子集,且每個子集中的需求均不重疊.則對于任意的需求b ∈BL,與需求b重疊的CL的區間長度(服務時間)小于2Dmax+db. 因此,與需求組BL重疊的CL的總區間長度(服務時間)嚴格小于n(2Dmax+db). 證畢.

3.2 競爭比分析

下面首先從特殊情況出發,討論n=1,Δ=1 時的情形.

1)策略在n=1,Δ=1 時的結論.

當n= 1,Δ= 1 時,根據定義3 并經簡單化簡可知對于任意的i ∈[n],都有?(i) =Dmin,即服務器的閾值與需求到達序列的最小區間長度相等. 首先定義如下函數.

同樣簡單化簡可知,對于?i ∈[n+1]時,都有?(i)=Dmin恒成立.

證明 當a=b時,代表這k+1 個需求持續時間相等,此時需求i最多與2 個需求相重疊.即k ＜2.此時,di=a,因此di/k≥a/2. 當a ＞b時,與a=b的情況相反,此時k≥3,且至少有k-2 個需求在需求i的開始時間si之后開始,并在需求i的結束時間si+di之前結束. 所以,di≥(k-2)a成立. 進一步進行分式變換得,di/k≥(k-2)a/k≥a/3. 證畢.

證明 對于由該確定性策略分配給服務器i的任何給定b ∈BL,從b到集合CL中非空分配是必須有持續時間大于或等于?(i)的需求,并且b屬于集合BL∩CL. 集合CL是已知需求到達序列L時確定的需求集合.因此,集合CL和CL可以被劃分成n個子集,這每個子集只包含不相互重疊的需求.

表1 匯總了以上四個定理分別給出的策略在四種不同情形下的競爭比. 綜合情況1)和情況3)可知,當n ∈N,Δ= 1 時,策略的競爭比只與參數f有關,且上界為3(1+f),即策略在f取值越小時競爭比越好;綜合情況2)和情況4)可知,當n ∈N,Δ ＞1 時,競爭比與f和Δ都相關.

表1 競爭比總結表Table 1 The summary of competitive ratios

4 數值算例

在這一節中結合數值算例評估策略的實際性能.假設有20 組需求集合在一段時間內陸續到達,相鄰到達的兩個集合間隔1 個單位,每組需求集合內包含x個需求任務,其中x ∈[3,10]. 每個需求的持續時間的區間為D= [6,12],系統中可服務的服務器數量為n= 5 個.假設每單需求帶給平臺的固定收益s= 1,可變收益為1,此時Δ=2,定義3 中的t(n,Δ)=t(5,2)≈5.405,I=3.

根據上述規則用計算機隨機生成一組需求到達序列,根據本文提出的任務分配策略進行編程,得到策略A 所調度的結果如表2 和圖1.

圖1 A 調度結果示意圖Fig.1 The scheduling results diagram of A

表2 A 調度結果表Table 2 The scheduling results of A

表3 OPT 調度結果表Table 3 The scheduling results of OPT

圖2 OPT 調度結果示意圖Fig.2 The scheduling results diagram of OPT

5 結束語

本文考慮的是共享平臺下的實時任務分配問題.在實際中需求信息常常是難以預測也不可用概率分布刻畫的實際背景下,考慮平臺的收益包含固定收益和可變收益,建立了占線任務分配模型,引入閾值的概念,給出了相應的實時任務分配策略,從理論上證明了該策略具有較好的常數競爭性能比.在未來的研究中,可以通過考慮將更多的實際因素融入到模型中以增加模型的指導性.