邱言玲

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

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

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

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

1 問題的提出

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

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

合作收益函數(shù)

其中，el是第l個人選擇不進行合作時的機會成本，(e1，e2)為合作博弈中的無協(xié)議點，滿足

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

2 兩人合作排序博弈

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對任意給定的向量(r1，r2)，問題(P(r1，r2))可在O(n)時間內解決。事實上，若存在某個正整數(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 對任意給定的向量(r1，r2)，最大延遲排序兩人合作博弈問題(P(r1，r2))的最優(yōu)解k*對應的合作收益分配方案(v1*，v2*)=(v1(k*)，v2(k*))是帕累托有效的。

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

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

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

定理3 對任意給定的向量(r1，r2)，若最大延遲排序的兩人合作博弈問題(P(r1，r2))滿足性質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。所以，對任意的權重系數(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。故對任意的權重系數(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。

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

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

4 結束語

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

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

［1］唐國春，張峰，羅守成，等.現(xiàn)代排序論［M］.上海:上?？茖W普及出版社，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］金霽，顧燕紅，唐國春.最大完工時間排序的兩人合作博弈［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］顧燕紅，金霽，唐國春.加工時間可變最大流程時間排序的納什合作博弈［J］.重慶師范大學學報:自然科學版，2012，9(4):18 －23.

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

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