最大延遲排序的兩人合作博弈

邱言玲

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西西安 710071)

經(jīng)典的排序問題，是為加工若干個(gè)工件(Job)，而對(duì)工件及工件所需的機(jī)器(Machine)按時(shí)間進(jìn)行分配和安排，在完成所有工件加工時(shí)，使得某個(gè)(些)目標(biāo)為最優(yōu)［1］，所有工件均由一個(gè)“人”完成。然而，由于資金、技術(shù)、規(guī)模或時(shí)間的限制，一個(gè)“人”通常無(wú)法獨(dú)立的承擔(dān)所有工件的加工任務(wù)。此時(shí)，兩方或多方合作共同加工一批工件的情況便應(yīng)運(yùn)而生。如何進(jìn)行工件的劃分和進(jìn)行利益的分配，使得每個(gè)人相應(yīng)的合作收益有一定的合理性，且雙方均愿意接受合作收益所確定的利潤(rùn)分配方案，從而保證這一商業(yè)聯(lián)盟的穩(wěn)定性與可行性。這種建立在參與雙方均滿意基礎(chǔ)上的工件分配問題就是合作排序博弈，簡(jiǎn)稱合作博弈。

陳全樂博士首先開始研究?jī)扇撕献骷庸さ呐判騿栴}［2］，將納什博弈 解［3－4］(Nash Bargaining Solution，NBS)應(yīng)用到此類研究中，并加以推廣以此作為優(yōu)化的目標(biāo)。其所提出的優(yōu)化目標(biāo)函數(shù)，可根據(jù)實(shí)際需要，調(diào)節(jié)效率與公平的權(quán)重，從而使所建的數(shù)學(xué)模型更具一般性、可行性。但必須指出的是，文獻(xiàn)［2］假設(shè)工件加工時(shí)間、工期等參數(shù)均為整數(shù)，因而研究的是離散情況下的排序博弈問題。隨后，又有一些學(xué)者對(duì)機(jī)器排序博弈進(jìn)行了研究［5－12］。文獻(xiàn)［5～6］和文獻(xiàn)［12］討論工件加工時(shí)間相同情況下，以合作收益函數(shù)乘積為優(yōu)化目標(biāo)的排序博弈問題。不同的是，文獻(xiàn)［5］和文獻(xiàn)［12］分別考慮了以最小的最大完工時(shí)間和最小的總完工時(shí)間為加工成本的排序博弈問題，并給出了公式化結(jié)論;文獻(xiàn)［8］考慮工件有工期限制的問題，給出了動(dòng)態(tài)規(guī)劃算法。文獻(xiàn)［9］考慮工件加工時(shí)間不相同情況下的排序博弈問題。文獻(xiàn)［7］考慮合作雙方在協(xié)商確定工件劃分方案時(shí)影響力不等同的情況，證明當(dāng)合作收益函數(shù)與工件的排序無(wú)關(guān)時(shí)，該問題等價(jià)于背包問題。文獻(xiàn)［10～11］均是考慮工件加工時(shí)間與開工時(shí)間有關(guān)的排序博弈問題，以最小的最大流程時(shí)間為加工成本，優(yōu)化的目標(biāo)為使合作收益函數(shù)乘積最大，給出了相應(yīng)的定理，從而能直接確定使雙方均滿意的工件劃分方案。以上文章大多以加工工件最小的最大流程時(shí)間或是最小的總完工時(shí)間作為加工成本。

現(xiàn)有文獻(xiàn)大多只考慮了合作雙方的效率，對(duì)公平性則少有考慮。金霽［11］雖考慮到公平性問題，但與大多數(shù)文獻(xiàn)一樣，其是以最小的最大完工時(shí)間作為加工成本的。然而，所加工的工件是否延遲，以及延遲時(shí)間的長(zhǎng)短同樣影響著參與人的收益。迄今，少有學(xué)者在機(jī)器排序博弈方面將最大延遲作為工件的加工成本?；谶@一事實(shí)，本文同時(shí)考慮了合作雙方的效率及公平，討論了工件的加工時(shí)間均相同，以最小的最大延遲作為加工成本的兩人合作排序博弈問題。首先，討論優(yōu)化目標(biāo)函數(shù)是max v1v2的問題P(1，0)，在此基礎(chǔ)上分析問題 P(r1，r2)，其考慮成對(duì)的兩個(gè)最優(yōu)化目標(biāo)函數(shù)Pt((r1，r2))∶r1v1v2+r2min{v21，v22}，(t=1，2)，其中 vi是第i個(gè)人的整數(shù)取值合作收益，(r1，r2)是max v1v2與max min{v21，v22}的權(quán)重系數(shù)向量。事實(shí)上，當(dāng)r1=1，r2=0時(shí)，便是最大化納什博弈的目標(biāo)函數(shù)v1v2，陳全樂［2］博士說明了滿足max v1v2確定的利益分配方案是在充分考慮到能力高的一方收益情況下兼顧公平的結(jié)果。而目標(biāo)函數(shù)max min{v21，v22}則強(qiáng)調(diào)合作收益分配的公平性。權(quán)重系數(shù)向量可根據(jù)合作雙方的偏好合理設(shè)置。

1 問題的提出

設(shè)有工件集J={1，2，…，n}，所有工件有相同的就緒時(shí)間t=0，每個(gè)工件只需加工一次。工件i的加工時(shí)間pi=p，工件i的完工時(shí)間Ci，也是其緊后工件的開始加工時(shí)間。每個(gè)工件i有相同的交貨期di=d。顯然工件加工時(shí)間只與其開始加工的“位置”有關(guān)，所以劃分工件集只需考慮每個(gè)集合中工件的個(gè)數(shù)。由兩個(gè)人合作共同加工這n個(gè)工件，即要將工件集劃分成兩個(gè)互不相交的集合，分別給這兩臺(tái)機(jī)器加工。記兩個(gè)集合分別為 X1={1，2，…，k}和 X2={k+1，k+2，…，n}，1≤k≤n －1，則 X1∪X2=J，X1∩X2= Φ，集合Xl(l=1，2)內(nèi)的工件由第l人加工。工件i的延遲為L(zhǎng)i=Ci－di。假設(shè)每人有一臺(tái)加工機(jī)器，每加工單位時(shí)間的工件會(huì)使第l人獲得bl個(gè)單位的收益。因此，收益函數(shù)

由于成本函數(shù)是最小的最大延遲，根據(jù)收益函數(shù)可知，即使完全不加工收益函數(shù)中也會(huì)有一個(gè)固定項(xiàng)。因此，為保證實(shí)際操作的合理性，必須滿足ul＞d，l=1，2，所以有

合作收益函數(shù)

其中，el是第l個(gè)人選擇不進(jìn)行合作時(shí)的機(jī)會(huì)成本，(e1，e2)為合作博弈中的無(wú)協(xié)議點(diǎn)，滿足

本文考慮離散情況下的合作博弈問題，并假設(shè)參數(shù) p，d，bl均是正整數(shù)，e1，e2是非負(fù)整數(shù)。

2 兩人合作排序博弈

2.1 目標(biāo)函數(shù)為max v1v2的排序博弈問題

根據(jù)以上敘述，可得到合作收益函數(shù)

由于達(dá)成合作的合作收益函數(shù)vi(k)，i=1，2必須＞0。即存在某個(gè) k，k∈{1，2，…，n}，使得

根據(jù)式(3)和式(4)可得

又因k是一個(gè)滿足兩人合作的正整數(shù)，所以有

v1v2=v1(k)v2(k)=(b1－)(b2－1)p(k－α1)p(α2－k)是一個(gè)關(guān)于決策變量k開口向下的二次函數(shù)離散點(diǎn)集。對(duì)稱軸為(α1+α2)，所以記 α =(α1+α2)，顯然，α未必是整數(shù)。

因此，研究的目標(biāo)函數(shù)為max v1(k)v2(k)的相同工件最大延遲排序兩人合作博弈問題的最優(yōu)解，k*可在多項(xiàng)式時(shí)間內(nèi)得到，且最優(yōu)值為v1(k*)v2(k*)=

性質(zhì)1 當(dāng)式(1)和式(2)成立時(shí)，最大延遲排序兩人合作博弈問題有解的充分必要條件為

證明 由式(6)和式(7)可知，最大延遲排序兩人合作博弈問題有解等價(jià)于(α1，α2)∩［1，n －1］≠Φ，即至少存在一個(gè)正整數(shù) k，使得 k∈(α1，α2)∩［1，n －

顯然，1≤αl≤n －1，1≤αr≤n －1，即［αl，αr］中至少包含一個(gè)正整數(shù)，故此合作博弈問題有解等價(jià)于αl≤αr。

定理1 當(dāng)式(8)成立時(shí)，最大延遲排序兩人合作博弈的最優(yōu)解最多有兩個(gè)。

證明 顯然，當(dāng)式(8)中αl≤αr成立時(shí)，至少存在一個(gè)正整數(shù)k，使得vi(k)＞0(i=1，2)成立，若將v1v2=v1(k)v2(k)=(b1－1)(b2－1)p(k－α1)p(α2－k)抽象成連續(xù)的，則是一個(gè)關(guān)于決策變量k開口向下的二次函數(shù)，對(duì)稱軸α=(α+α)，滿足目標(biāo)函數(shù)最大的k12一定是距離對(duì)稱軸最近的某個(gè)正整數(shù)。所以，若，則最大延遲排序兩人合作博弈的最優(yōu)解，則最大延遲排序兩人合作博弈的最優(yōu)解k*=:若α為整數(shù)，則最大延遲排序兩人合作博弈的最優(yōu)解 k*=α:若，則最大延遲排序兩人合作博弈的最優(yōu)解集為

所以，若αl≤αr成立，最大延遲排序兩人合作博弈的最優(yōu)解最多有兩個(gè)。

2.2 目標(biāo)函數(shù)排序博弈問題

目標(biāo)函數(shù)max v1v2確定的利益分配方案是，在充分考慮能力高的一方收益情況下兼顧公平的結(jié)果，強(qiáng)調(diào)了合作收益分配的效率原則。而目標(biāo)函數(shù)max min{v21，v22}則強(qiáng)調(diào)合作收益分配的公平性。根據(jù)合作雙方的偏好程度，本文綜合考慮效率原則及公平性，建立如下排序博弈模型

其中，(r1，r2)是權(quán)重系數(shù)向量。記其最優(yōu)解為k*(r1，r2)。

對(duì)任意給定的向量(r1，r2)，問題(P(r1，r2))可在O(n)時(shí)間內(nèi)解決。事實(shí)上，若存在某個(gè)正整數(shù)k(1≤k≤n－1)，使得合作收益函數(shù) vi(k)＞0，i=1，2，則這樣的正整數(shù)k就是問題(P(r1，r2))的可行解。所求的最優(yōu)解k*滿足k∈{1，2，…，n －1}}。

定理2 對(duì)任意給定的向量(r1，r2)，最大延遲排序兩人合作博弈問題(P(r1，r2))的最優(yōu)解k*對(duì)應(yīng)的合作收益分配方案(v1*，v2*)=(v1(k*)，v2(k*))是帕累托有效的。

證明 假設(shè)對(duì)任意給定的向量(r1，r2)，存在一個(gè)可行解，使得，且至少存在一個(gè)i=1，2使不等式vi()＞vi(k*)嚴(yán)格成立。所以，有顯然v22(k*)}即 z()＞ z(k*)，這與 k*是最大延遲排序兩人合作博弈問題(P(r1，r2))的最優(yōu)解相矛盾。所以，假設(shè)不成立，問題得證。

顯然，問題(P(r1，r2))的目標(biāo)函數(shù)是max v1(k)v2(k)與max min{v21(k)，v22(k)}的線性組合。為此先考慮如下兩個(gè)優(yōu)化問題

分別記問題(P(1，0))、(P(0，1))的最優(yōu)解為 k*(1，0)和k*，令 W={k*，k*}，則下述定理成立。(0，1)(1，0)(0，1)

定理3 對(duì)任意給定的向量(r1，r2)，若最大延遲排序的兩人合作博弈問題(P(r1，r2))滿足性質(zhì)1，則其最優(yōu)解k*(r1，r2)∈W。

3 算例分析

例1 b1=3，b2=5，e1=5，e2=37，n=10，p=1，d=7，則 α= －1，α=2.5，α =(α+ α)=0.75，有1212k(1，0)=1，k(0，1)=1，即問題 P(1，0)和 P(0，1)的最優(yōu)解均為1。所以，對(duì)任意的權(quán)重系數(shù)向量(r1，r2)問題 P(r1，r2)的最優(yōu)解均為1。

例2 b1=3，b2=5，e1=5，e2=11，n=10，p=1，d=3，則 α=1，α=8，α =(α+ α)=4.5，有 k=1212(1，0)4 或 5，k(0，1)=5，即問題 P(1，0)的最優(yōu)解為 k*(1，0)=4 或5，問題 P(0，1)的最優(yōu)解為 k*(0，1)=5。故對(duì)任意的權(quán)重系數(shù)向量(r1，r2)問題 P(r1，r2)的最優(yōu)解均為 k*(r1，r2)=5。

例3 b1=8，b2=5，e1=22，e2=4，n=10，p=1，d=8，則α=2，α=11，α =(α+α)=6.5 有k=1212(1，0)6 或 7，k(0，1)=5，即問題 P(1，0)的最優(yōu)解為 k*(1，0)=6 或7，問題 P(0，1)的最優(yōu)解為 k*(0，1)=5。

此時(shí)，因k*(0，1)是一個(gè) k*(1，0)與無(wú)關(guān)的數(shù)值。所以，問題P(r1，r2)的最優(yōu)解與權(quán)重系數(shù)向量(r1，r2)的選取有關(guān)。(r1，r2)=(1，0)時(shí)，k*(1，0)=6 或 7，(r1，r2)=(0，1)時(shí)，k*(0，1)=5，(r1，r2)=(0.5，0.5)時(shí)，k*(0.5，0.5)=6，(r1，r2)=(0.6，0.4)時(shí)，k*(0.6，0.4)=6，(r1，r2)=(0.3，0.7)時(shí)，k*(0.3，0.7)=5。

根據(jù)以上幾個(gè)例子可看出，當(dāng)k*與 k*相等，(0，1)(1，0)或是k*(0，1)等于 k*(1，0)中的某一個(gè)值時(shí)，無(wú)論(r1，r2)取何值，問題 P(r1，r2)的最優(yōu)解 k*(r1，r2)均確定的值。但當(dāng)k*(0，1)與 k*(1，0)不相等，或 k*(0，1)不與 k*(1，0)中的任意一個(gè)值相等時(shí)，問題 P(r1，r2)的最優(yōu)解 k*(r1，r2)與(r1，r2)的取值有關(guān)。所以，決策者可通過協(xié)商根據(jù)對(duì)效率或公平的偏好程度來合理定義(r1，r2)的大小，從而確定最終的利益分配方案，使合作雙方均滿意。

4 結(jié)束語(yǔ)

本文討論了由兩個(gè)人合作共同完成一批工件加工的排序博弈問題。每一方均只有一臺(tái)加工機(jī)器，加工無(wú)法中斷，以最小的最大延遲作為加工成本，分別以max v1v2和r1v1v2+r2min{v21，v22}作為目標(biāo)函數(shù)，兼顧效率和公平原則的前提下，確定如何分配加工任務(wù)才能使每個(gè)人均對(duì)自己的合作收益滿意。本文針對(duì)加工時(shí)間完全相同且交貨期均相同的情形，對(duì)不同的目標(biāo)函數(shù)進(jìn)行了分析并運(yùn)用數(shù)值算例驗(yàn)證了性質(zhì)定理的準(zhǔn)確性。

隨后，將針對(duì)工件的加工時(shí)間是與開始加工時(shí)間有關(guān)的變量及每個(gè)工件有不同交貨期的情形展開研究，探討這些情況下以最小的最大延遲作為加工成本的兩人合作博弈問題的最優(yōu)解。

［1］唐國(guó)春，張峰，羅守成，等.現(xiàn)代排序論［M］.上海:上?？茖W(xué)普及出版社，2003.

［2］Chen Q L.A new discrete bargaining modle on job partition between two manufactures［D］.Hongkong:The Chinese University of Hong Kong，2006.

［3］Nash JF.The bargaining problem［J］.Econometrica，1950，18(2):155－162.

［4］Nash J F.Two person cooperative games［J］.Econometrica，1953，21(1):128 －140.

［5］金霽，顧燕紅，唐國(guó)春.最大完工時(shí)間排序的兩人合作博弈［J］.Journal of Second Polytechnic University，2011，28(1):14－17.

［6］Gan X B，Gu Y H，Vairaktarakis G L，et al.A scheduling problem with one producer and the bargaining counterpart with two producers［J］.Lecture Notes in Computer Science，2007，4614:305 －316.

［7］Gu Y H，Chen QL.Some extended knapsack problems involving job partition between two parties［J］.Appl Math J Chinese Univ Ser B，2007，22(3):366 －370.

［8］Gu Y H，F(xiàn)an J，Tang GC，et al.Maximum latency scheduling problem on two － person cooperative games［J/OL］.(2011 －11－16)［2012－04－18］http://www.springerlink.com/content/6mm57855x5598kv8/fulltext.pdf.

［9］Gu Y H，Goh M，Chen Q L，et al.A new two － party bargaining mechanism［J/OL］.(2011－11－02)［2012－04－18］http://www.springerlink.com/content/q40684034261hh62/fulltext.pdf.

［10］顧燕紅，金霽，唐國(guó)春.加工時(shí)間可變最大流程時(shí)間排序的納什合作博弈［J］.重慶師范大學(xué)學(xué)報(bào):自然科學(xué)版，2012，9(4):18 －23.

［11］金霽.加工時(shí)間是開工時(shí)間線性函數(shù)的兩人合作排序博弈問題［J］.南京師范大學(xué)學(xué)報(bào):工程技術(shù)版，2012，12(4):87－92.

［12］竇文卿，顧燕紅，唐國(guó)春.總完工時(shí)間排序兩人合作博弈的納什博弈解［J］.重慶師范大學(xué)學(xué)報(bào):自然科學(xué)版，2012，29(5):1－5.