周意元, 張 強

(1.北京理工大學 管理與經(jīng)濟學院，北京 100081; 2.三峽大學 理學院，湖北 宜昌 443002)

?

排序?qū)Σ叩囊粋€新的收益分配準則

周意元1,2, 張 強1

(1.北京理工大學 管理與經(jīng)濟學院，北京 100081; 2.三峽大學 理學院，湖北 宜昌 443002)

針對一個機器的排序問題，給出了排序問題中成本增加量的表達式，提出了收益分配的不小于成本增加量準則。針對一類特殊的排序問題，給出一個符合不小于成本增加量分配準則的解，并證明了它滿足有效性，啞元性和單調(diào)性。結(jié)合一個算例，對本文的提出的方法進行了分析驗證。

合作對策；排序問題；收益分配準則；核心

0 引言

排序?qū)Σ?sequencing game)是Curiel等[1]為了利用合作對策的方法解決如下的排序問題而提出來的。有限個局中人在一個機器前按初始順序排隊等待服務(wù)，每位局中人有一個工件需要在這個機器上處理。局中人在等待他的工件被處理完的過程中有成本，這些成本與完工時間成正比，隊列的總成本是各局中人成本之和?？梢酝ㄟ^調(diào)整局中人的順序使總成本最小，相對于初始順序時的總成本，減少的總成本可以認為是所有局中人合作而產(chǎn)生的收益，那么這些收益該如何在所有局中人之間分配？文獻[1]提出了收益分配的EGS準則(equal gain splitting rule), 它將相鄰局中人通過交換順序而減少的成本平均分配給這兩位局中人，EGS準則所產(chǎn)生的解屬于排序?qū)Σ叩暮诵摹?/p>

此后，學者們對排序問題和排序?qū)Σ咧械墓ぜ幚頃r間、機器數(shù)量、初始順序等進行了拓展研究[2～6]。由于合作對策的核心具有較好的性質(zhì)且凸對策和均衡對策的核心非空，因此這些研究工作的重點是相應(yīng)對策的凸性或均衡性。也有學者研究排序問題和排序?qū)Σ叩氖找娣峙錅蕜t，如GS準則(gain splitting rule)[7]、退出單調(diào)準則[8]等。

在排序問題和排序?qū)Σ咧校斂偝杀緶p少時，有些局中人的成本會減少，但是有些局中人的成本反而會增加，這些成本增加量就是他們的損失。如果按照某個收益分配準則，一位局中人得到的分配小于他的成本增加量，這樣的分配準則是不夠合理的。

本文主要考慮排序?qū)Σ叩氖找娣峙錅蕜t，提出了不小于成本增加量的分配準則，滿足這個準則的分配都屬于排序?qū)Σ叩暮诵?，同時它能保證每個局中人得到的分配不小于他的成本增加量。針對一類特殊的排序問題，給出了一個滿足不小于成本增加量分配準則的解，它滿足有效性、啞元性。

1 排序問題和排序?qū)Σ?/h2>

排序問題中，所有局中人的集合記為N={1,2,…,n}，局中人i的工件也記為i，σ0是隊列的初始順序，σ0(i)=j表示初始時局中人i排在第j位或工件i排在第j位，工件i的處理時間pi>0，排在隊列首位的工件從時刻t=0開始處理。局中人i在順序σ0下的成本C(σ0,i)=αit，其中t是工件i在順序σ0下的完成時間，αi≥0是局中人的單位時間成本。則排序問題可以記為(N,σ0,p,α)，其中向量p=(pi)i∈N，α=(αi)i∈N。

記號P(σ,i)={j∈N|σ(j)<σ(i)}表示在順序σ下，比工件i先處理的工件構(gòu)成的集合，F(xiàn)(σ,i)={j∈N|σ(j)>σ(i)}表示在順序σ下，比工件i后處理的工件構(gòu)成的集合。

對排序問題(N,σ0,p,α)，總有一個合作對策(N,ν)與之對應(yīng)，稱為排序?qū)Σ遊1]。為了確定排序?qū)Σ咧新?lián)盟S?N的收益值ν(S)，需要討論哪些順序?qū)β?lián)盟S是可接受的。對聯(lián)盟S?N內(nèi)的局中人調(diào)整順序時，不能影響NS中局中人的成本。

定義1[1]如果對任意的j∈NS，工件處理順序σ滿足P(σ0,j)=P(σ,j)，則稱σ對聯(lián)盟S是可接受的，∑S表示聯(lián)盟S所有可接受的順序構(gòu)成的集合。

排序?qū)Σ?N,ν)定義如下，

(1)

它表示在可接受的順序下，聯(lián)盟S中的局中人合作最多能節(jié)約的成本。顯然ν({i})=0，而

(2)

其中τ是大聯(lián)盟的最優(yōu)順序。

定義2[1]對所有i,j∈S和k∈N，如果由σ0(i)≤σ0(k)≤σ0(j)可以得到k∈S，則稱聯(lián)盟S是連通的。

對于連通的聯(lián)盟S，表達式(1)可以改寫為

(3)

其中g(shù)ij=max{0,αjpi-αipj}表示當σ0(i)=σ0(j)-1時, 局中人i和j交換順序后減少的成本。對非連通的聯(lián)盟T，有ν(T)=∑S∈Tσ0ν(S)，其中Tσ0是由T的最大連通子集構(gòu)成的集合，“最大”是指連通子集增加任何一個不屬于該子集的元素后就不是連通的。

為了把所有局中人合作產(chǎn)生的收益ν(N)在這些局中人之間分配，學者們提出了EGS準則[1]和GS準則[7]。在EGS準則下，局中人i得到的分配是

而按照GS準則，局中人i得到的分配為

合作對策(N,ν)的核心C(ν)={x∈Rn|x(N)=ν(N),x(S)≥ν(S),?S?N}，由EGS準則和GS準則產(chǎn)生的解都屬于排序?qū)Σ叩暮诵腫1,7]。

2 不小于成本增加量的分配準則

在排序問題(N,σ0,p,α)中，若σ0(i)=σ0(j)-1和ui0，局中人i增加的成本ΔCi=αipj>0，局中人j增加的成本ΔCj=-αjpi<0，他的成本實際減少了αjpi。更一般地，如果隊列中某位局中人向后方移動，那么他的工件的完成時間會延后，從而成本也增加；相反，如果他向隊列前方移動，他的成本會減少。

對給定的i∈N，令H(u,i)={j∈N|uj>ui}表示緊迫性指數(shù)大于ui的局中人構(gòu)成的集合，L(u,i)={j∈N|uj

對于局中人i和j，如果j∈H(u,i)∩F(σ0,i)，根據(jù)最優(yōu)順序的緊迫性指數(shù)遞減原則，i和j需要交換順序，即i往后移動，j往前移動，則i的成本是增加的，j的成本是減少的。如果j∈L(u,i)∩P(σ0,i)，則i往前移動，j往后移動，那么i的成本是減少的，j的成本是增加的。如果j∈H(u,i)∩F(σ0,i)，則反之有i∈L(u,j)∩P(σ0,j)。為了行文方便，將H(u,i)∩F(σ0,i)記作H∩F，將L(u,i)∩P(σ0,i)記作L∩P。

從初始順序σ0變?yōu)樽顑?yōu)順序τ后，局中人i增加的成本ΔCi為

當ΔCi>0時，局中人i的成本是增加的;ΔCi<0時，他的成本實際是減少的。

定義3 對策(N,ν)是與排序問題(N,σ0,p,α)對應(yīng)的排序?qū)Σ?，不小于成本增加量分配準則是：分配x∈Rn滿足(1)x∈C(ν), (2)xi≥ΔCi,i∈N。

所有滿足不小于成本增加量分配準則的解記作G(N,σ0,p,α)，即

G(N,σ0,p,α)={x∈Rn|x∈C(ν),xi≥ΔCi,i=1,2,…,n}

顯然有G(N,σ0,p,α)?C(ν)。

對于排序?qū)Σ撸m然它的核心一定存在，但是滿足不小于成本增加量分配準則的解不一定存在，下面針對一類特殊的排序?qū)Σ?，給出一個滿足不小于成本增加量分配準則的解。

證明 對連通的聯(lián)盟S，

所以fλ,σ0(S)≥ν(S)。當S=N時，fλ,σ0(N)=ν(N)。對于非連通的聯(lián)盟T有

如果對所有i∈N和j∈H∩F都有2ui

從而

因此fλ,σ0≥ΔCi。由以上證明過程有fλ,σ0∈G(N,σ0,p,α)，證明完畢。

Hamers等[7]提出了排序問題(N,σ0,p,α)解的三個性質(zhì)：有效性、啞元性和單調(diào)性。

設(shè)排序問題(N,σ0,p,α)的最優(yōu)順序是τ，向量x是它的解。

(1)有效性：x(N)=C(σ0,N)-C(τ,N)。

(2)啞元性：如果存在k∈N使P(σ0,k)=P(τ,k)，則xk=0，即如果隊列中沒有局中人與k交換順序，則k得不到任何分配。

(3) 單調(diào)性：假設(shè)(N,σ1,p,α)也是排序問題，其中σ0(i)=σ0(j)-1，σ1(i)=σ0(j)，σ1(j)=σ0(i)，而當k≠i,j時，σ1(k)=σ0(k)。對(N,σ0,p,α)的任意解x∈Rn，則一定存在(N,σ1,p,α)的解y∈Rn，使下面兩個結(jié)論之一成立。

(i)當k≠i,j時，xk=yk，而xi≥yi和xj≥yj；

(ii)當k≠i,j時，xk=yk，而xi≤yi和xj≤yj。

定理2 對策(N,ν)是與排序問題(N,σ0,p,α)對應(yīng)的排序?qū)Σ撸绻麑λ衖∈N和j∈H(u,i)都有2ui

證明 (1)因為fλ,σ0∈G(N,σ0,p,α)?C(ν)，有效性是顯然的。

(2)如果P(σ0,k)=P(τ,k)且隊列的最優(yōu)順序是τ，則P(σ0,k)=P(τ,k)=H(u,k)，F(xiàn)(σ0,k)=F(τ,k)=L(u,k)，所以H(u,k)∩F(σ0,k)=?，L(u,k)∩P(σ0,k)=?。因此

(3)由于(N,σ1,p,α)是排序問題，且k≠i,j時σ1(k)=σ0(k)成立，則對所有的k∈N{i,j}，有P(σ0,k)=P(σ1,k)，F(xiàn)(σ0,k)=F(σ1,k)，而

根據(jù)單調(diào)性定義中的條件有P(σ0,i)=P(σ1,j)和F(σ0,j)=F(σ1,i)，為了行文方便，記P=P(σ0,i)=P(σ1,j)，F(xiàn)=F(σ0,j)=F(σ1,i)。

由于當i∈N和j∈H(u,i)時，2ui

(a)如果ui>uj，則ui>2uj和αipj-2αjpi≥0，而

(b)如果ui

3 數(shù)值算例

排序問題(N,σ0,p,α)，其中N={1,2,3,4,5}，初始順序σ0(i)=i，p=(3,2,2,7,3)，α=(6,9,4,2,3)。

局中人的緊迫性指數(shù)大小關(guān)系為u2>u1=u3>u5>u4，局中人1和3的緊迫性指數(shù)相等且初始時1排在3的前面，因此最優(yōu)順序中1也應(yīng)該排在3的前面，最優(yōu)順序τ為τ(1)=2，τ(2)=1，τ(3)=3，τ(4)=5，τ(5)=4. 從初始順序調(diào)整為最優(yōu)順序后，局中人的成本增加量分別為ΔC1=12，ΔC2=-27，ΔC3=0，ΔC4=6，ΔC5=-21. 滿足EGS準則的收益分配方案為EGS=(7.5,7.5,0,7.5,7.5)。

在調(diào)整隊列順序的過程中，沒有局中人與3交換順序，也就是說局中人3在此次合作中沒有任何貢獻，他得不到任何分配。成本增加的局中人1和4得到的分配都大于他們的成本增加量。

4 結(jié)論

本文提出了不小于成本增加量的分配準則，滿足這個準則的解能使局中人得到的分配不小于他的成本增加量。針對滿足一定條件的排序問題，給出了一個滿足不小于成本增加量分配準則的解，并證明了它具有良好的性質(zhì)。

[1] Curiel I, Pederzoli G, Tijs S. Sequencing games[J]. European Journal of Operational Research, 1989, 40: 344-351.

[2] Grundel S, Ciftci B, Borm P, Hamers H. Family sequencing and cooperation[J]. European Journal of Operational Research, 2013, 226: 414- 424.

[3] Hamers H, Klijn F, Van Velzen B. On the convexity of precedence sequencing games[J]. Annals of Operations Research, 2005, 137: 161-175.

[4] Van Velzen B. Sequencing games with controllable processing times[J]. European Journal of Operational Research, 2006, 172: 64- 85.

[5] Slikker M. Balancedness of multiple machine sequencing games revisited[J]. European Journal of Operational Research, 2006, 174: 1944-1949.

[6] Klijn F, Sanchez E. Sequencing games without initial order[J]. Mathematical Methods of Operations Research, 2006, 63: 53- 62.

[7] Hamers H, Suijs J, Tijs S, Borm P. The split core for sequencing games[J]. Games and Economic Behavior, 1996, 15: 165-176.

[8] Fernandez C, Borm P, Hendrickx R, Tijs S. Drop out monotonic rules for sequencing situations[J]. Mathematical Methods of Operations Research, 2005, 61: 501-504.

[9] Smith W. Various optimizers for single-stage production[J]. Naval Research Logistic Quarterly, 1956, 3: 59- 66.

A New Allocation Rule for Sequencing Games Coalition of Sequencing Games

ZHOU Yi-yuan1,2, ZHANG Qiang1

(1.SchoolofManagementandEconomics,BeijingInstituteofTechnology,Beijing100081,China; 2.CollegeofScience,ChinaThreeGorgesUniversity,Yichang443002,China)

One-machine sequencing situations and corresponding sequencing games are considered, the main aim is an allocation rule. The expression of the cost increment is presented. A new allocation rule is introduced, the payoff based on the rule is greater than or equal to the cost increment and belongs to the core of corresponding sequencing game. For a special class of sequencing situation, a solution is designed to compensate players for their losses firstly and allocate the remaining worth among the players secondly, it is proved that this solution satisfies the new rule and has the property of efficiency, dummy property and monotonicity. Meanwhile, a numerical example is studied.

cooperative games; sequencing situation; allocation rule; core

2014- 04-21

國家自然科學基金資助項目(71371030,71071018,71201089);高等學校博士學科點專項科研基金資助項目(20111101110036)；宜昌市科學技術(shù)研究與開發(fā)項目(A201230225)

周意元(1980-)，男，講師，博士研究生，主要研究方向：合作對策，決策理論和方法；張強(1955-)，男，教授，博士生導師，研究方向：合作對策，決策理論和方法。

O225

A

1007-3221(2015)06- 0011- 05

10.12005/orms.2015.0190