排序?qū)Σ叩囊粋€(gè)新的收益分配準(zhǔn)則

周意元, 張 強(qiáng)

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

?

排序?qū)Σ叩囊粋€(gè)新的收益分配準(zhǔn)則

周意元1,2, 張 強(qiáng)1

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

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

合作對(duì)策；排序問題；收益分配準(zhǔn)則；核心

0 引言

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

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

在排序問題和排序?qū)Σ咧校?dāng)總成本減少時(shí)，有些局中人的成本會(huì)減少，但是有些局中人的成本反而會(huì)增加，這些成本增加量就是他們的損失。如果按照某個(gè)收益分配準(zhǔn)則，一位局中人得到的分配小于他的成本增加量，這樣的分配準(zhǔn)則是不夠合理的。

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

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

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

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

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

定義1[1]如果對(duì)任意的j∈NS，工件處理順序σ滿足P(σ0,j)=P(σ,j)，則稱σ對(duì)聯(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]對(duì)所有i,j∈S和k∈N，如果由σ0(i)≤σ0(k)≤σ0(j)可以得到k∈S，則稱聯(lián)盟S是連通的。

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

(3)

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

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

而按照GS準(zhǔn)則，局中人i得到的分配為

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

2 不小于成本增加量的分配準(zhǔn)則

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

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

對(duì)于局中人i和j，如果j∈H(u,i)∩F(σ0,i)，根據(jù)最優(yōu)順序的緊迫性指數(shù)遞減原則，i和j需要交換順序，即i往后移動(dòng)，j往前移動(dòng)，則i的成本是增加的，j的成本是減少的。如果j∈L(u,i)∩P(σ0,i)，則i往前移動(dòng)，j往后移動(dòng)，那么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為

當(dāng)ΔCi>0時(shí)，局中人i的成本是增加的;ΔCi<0時(shí)，他的成本實(shí)際是減少的。

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

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

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

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

對(duì)于排序?qū)Σ?，雖然它的核心一定存在，但是滿足不小于成本增加量分配準(zhǔn)則的解不一定存在，下面針對(duì)一類特殊的排序?qū)Σ?，給出一個(gè)滿足不小于成本增加量分配準(zhǔn)則的解。

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

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

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

從而

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

Hamers等[7]提出了排序問題(N,σ0,p,α)解的三個(gè)性質(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，即如果隊(duì)列中沒有局中人與k交換順序，則k得不到任何分配。

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

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

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

定理2 對(duì)策(N,ν)是與排序問題(N,σ0,p,α)對(duì)應(yīng)的排序?qū)Σ?，如果?duì)所有i∈N和j∈H(u,i)都有2ui

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

(2)如果P(σ0,k)=P(τ,k)且隊(duì)列的最優(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時(shí)σ1(k)=σ0(k)成立，則對(duì)所有的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)。

由于當(dāng)i∈N和j∈H(u,i)時(shí)，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ù)相等且初始時(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準(zhǔn)則的收益分配方案為EGS=(7.5,7.5,0,7.5,7.5)。

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

4 結(jié)論

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

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

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

O225

A

1007-3221(2015)06- 0011- 05

10.12005/orms.2015.0190