加工時(shí)間可變的總完工時(shí)間排序兩人合作博弈問題

金 霽

(蘇州市職業(yè)大學(xué) 馬列與公共教學(xué)部，江蘇 蘇州 215104)

加工時(shí)間可變的總完工時(shí)間排序兩人合作博弈問題

金 霽

(蘇州市職業(yè)大學(xué) 馬列與公共教學(xué)部，江蘇 蘇州 215104)

研究工件加工時(shí)間與開始加工時(shí)間有關(guān)的情況下，兩人合作共同加工一批工件的納什博弈問題.每人有一臺機(jī)器用于工件加工，以最小的總完工時(shí)間作為加工成本，通過確定這批工件的一個(gè)合理劃分，使參與合作加工的兩人都能得到滿意的合作收益.

排序；博弈；合作；收益；加工時(shí)間；線性函數(shù)

在經(jīng)典排序中，工件的加工時(shí)間通常是一個(gè)常數(shù)，然而在現(xiàn)實(shí)生活中未必如此，有時(shí)工件的加工時(shí)間與開工時(shí)間有關(guān)，是一個(gè)關(guān)于開工時(shí)間的函數(shù).例如，在消防救火工作中，開始救火的時(shí)間越晚，那么救火工作的難度就越大，花的時(shí)間就越長.因而，對工件加工時(shí)間隨開工時(shí)間變化的排序問題進(jìn)行研究有著積極的實(shí)際意義.自從Gupta N D和Gupta K[1]對該問題進(jìn)行研究之后，對于此類問題的研究十分活躍，得到了許多可喜的成果，關(guān)于此類問題的綜述見文獻(xiàn)[2].

1 問題的描述

2 問題的求解

下面對兩個(gè)不同的收益函數(shù)下的排序博弈問題進(jìn)行討論.為方便敘述，記問題P1為

記問題P2為

2.1 排序博弈問題P1的求解

合作收益函數(shù)為

注意到合作收益必須滿足vi(k)＞0（i=1，2），所以

證明參見文獻(xiàn)[8].

由式(1)、式(2)得合作收益函數(shù)的乘積為

注意到當(dāng)參數(shù)b1、b2、e1、e2、t0、α以及n都給定的時(shí)候，合作收益函數(shù)的乘積v1(k)v2(k)中第一項(xiàng)和第三項(xiàng)都是常數(shù)，因此要使目標(biāo)函數(shù)v1(k)v2(k)最大，只要式(5)中第二項(xiàng)最小.所以令

由式(3)可知，AD＞0，BC＞0，從而有AD(1+α)k＞0，BC(1+α)n-k＞0.所以

證明思想方法可參見文獻(xiàn)[8].

2.2 排序博弈問題P2的求解

由于ui(πi)＞0，所以bi＞1（i=1，2）.

合作收益函數(shù)為

因?yàn)関i(πi)＞0(i=1，2)，所以

注意到M＞0，N＞0，E≥M＞0，F(xiàn)≥N＞0，α＞0,所以，

由于兩人要進(jìn)行合作，因此必有

由式(10)～(12)可知

證明同性質(zhì)1，從略.

由式(8)、式(9)得合作收益函數(shù)的乘積為

令ψ(k)=MF(1+α)k+NE(1+α)n-k，當(dāng)參數(shù)b1、b2、e1、e2、α、t0以及n都給定的時(shí)候，式(14)中第一、第三項(xiàng)都是常數(shù)，只有第二項(xiàng)ψ(k)中含有決策變量k.所以，要使目標(biāo)函數(shù)v1(k)v2(k)最大，只要使ψ(k)最小.注意到MF(1+α)k＞0，NE(1+α)n-k＞0，所以，

證明同定理1，從略.

3 結(jié)論

考慮了兩人合作共同加工一批工件，其中工件的加工時(shí)間是開工時(shí)間的簡單線性函數(shù)，當(dāng)以最小的總完工時(shí)間為加工成本時(shí)，定理1和定理2分別給出不同收益函數(shù)對應(yīng)的排序博弈問題的最優(yōu)解(集).

[1]GUPTA N D，GUPTA K .Single facility scheduling with nonlinear processing[J].Computer Ind Engng，1988，14(4)：387-393 .

[2]CHENG T C E，DING Q，LIN B M T .A concise survey of scheduling with time-dependent processing time[J].European Journal of Operational Research，2004，152：1-13 .

[3]NASH J F.The bargaining problem[J].Econometrica，1950，18：155-162.

[4]NASH J F.Two person cooperative games[J].Econometrica，1953，21：128-140.

[5]CHEN Q L.A new discrete bargaining model on job partition between two manufacturers[D].Ph.D.Dissertation：The Chinese University of Hong Kong，2006.

[6]GU Yanhong，CHEN Quanle.Some extended knapsack problems involving job partition between two parties[J].Appl.Math.J.Chinese Univ.Ser.B，2007，22(3)：366-370.

[7]GAN X B，GU Y H，VAIRAKARAKIS G L，et al.A scheduling problem with one producer and the bargaining counterpart with two producers[C].ESCAPE，2007：305-316.

[8]金霽，顧燕紅，唐國春. 最大完工時(shí)間排序的兩人合作排序[J]. 上海第二工業(yè)大學(xué)學(xué)報(bào)，2011，28(1)：14-17.

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

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

[11]MUTHOO A.Bargaining theory with applications[M].Cambridge，United Kingdom：Cambridge University Press，1999.

Two-Person Cooperative Games on Total Completion Time Scheduling with Changeable Processing Time

JIN Ji

(Marxism Leninism and Public Education Department，Suzhou Vocational University，Suzhou 215104， China)

This paper studies two-person Nash bargaining problem，in which job processing time depends on its start time，each person is equipped with one machine and the processing cost is def i ned as minimized total completion time.It focuses on how to divide the jobs reasonably in order to make every participant satisf i ed with cooperation prof i t.

scheduling；game；cooperation；prof i t；processing time；linear function

O223

A

1008-5475(2013)03-0035-05

2013-04-11；

2013-05-02

金 霽(1978-)，女，江蘇無錫人，講師，碩士，主要從事組合優(yōu)化研究.

(責(zé)任編輯：沈鳳英)