工件加工时间是开工时间线性函数的排序博弈问题

金 霁

(苏州市职业大学 数理部，江苏 苏州 215104)

工件加工时间是开工时间线性函数的排序博弈问题

金 霁

(苏州市职业大学 数理部，江苏 苏州 215104)

工件加工过程中存在这样的情况：一个工件加工者无法独自完成一整批工件的加工任务，于是在排序研究中考虑多人合作共同加工一批工件的问题就应运而生了。讨论两人合作加工一批工件，每人提供一台机器用于加工，工件的加工时间是其开工时间的简单线性函数，以最小的最大完工时间为加工成本。给出最优工件划分，将工件分配给两人进行加工，让每个参与者都能获得合理的收益，从而愿意合作。

加工时间；线性函数；最大完工时间；合作收益；排序

工件加工过程存在着这样的情况：一个工件加工者无法独自完成一整批工件的加工任务，于是在排序研究中考虑多人合作共同加工一批工件的问题就应运而生了。但合作的同时，人们出于自身的考虑，往往希望获得较多的收益，即合作的同时存在着博弈。因而合作得以顺利实施的重要前提就是要有一个让各方满意的收益分配方案，使得各个参与者愿意合作。2006年Chen Q L在排序研究中考虑两人合作加工工件的问题[1]，并将纳什博弈解NBS[2-3](nash bargaining solution)应用到排序研究中，将排序研究带入了一个全新的领域。2011年文献[4]将这类考虑多人合作加工工件的排序问题明确定义为排序博弈问题。 目前，排序博弈问题的有关成果比较有限，如果按工件加工时间的不同情况，主要可以概括为如下三种情形：①工件加工时间相同的排序博弈问题[4-6]。文献[4]和文献[5]分别以最小的最大完工时间和最小的总完工时间作为加工成本，通过分析可行解集，给出了最优解(集)；文献[6]考虑工件有交货期的限制，通过构造示性函数，给出多项式时间的动态规划算法，在此基础上文献[6]进一步考虑工件加工时间互不相同的情况，证明其为NP-困难问题，同时给出伪多项式时间的动态规划算法；②工件加工时间是其开工时间线性函数的排序博弈问题[7-10]。工件加工时间与开工时间有关的排序问题的研究成果较为丰富，但现有成果中考虑多人合作加工情况的不多。文献[7]-文献[10]分别以最小的总完工时间、最小的最大流程时间和最小的加权总完工时间作为加工成本，给出了使双方满意的工件划分方案；其中文献[8]目标函数的设计则更好地体现了合作过程中效率优先兼顾公平的原则。③其他工件加工时间各不相同的排序博弈问题[11-13]。文献[11]对文献[1]提出的博弈机制作出明显改进，文献[12]研究工件有窗口交货期的问题，给出动态规划算法；文献[13]考虑合作双方在协商确定工件划分方案时影响力不等同的情况下，证明当合作收益函数与工件的排序无关时，该问题等价于背包问题。

本文考虑两人合作加工一批工件，每人提供一台机器用于加工，工件加工时间是其开工时间的简单线性函数，以最小的最大完工时间为加工成本，以合作收益函数的乘积作为目标函数，通过分析可行解集的情况，给出了最优解(集)。

1 问题的提出

设有工件集J={1，2，…，n}，每个工件都在时刻t0(t0＞0)之后开始加工，且只需被加工一次，相邻两个待加工工件之间无等待，即前一个工件加工完毕紧接着加工后一个工件。工件j的加工时间pj=αt(t≥t0)，其中：α(α＞0)为比例系数；t(t≥t0)是工件 的开始加工时间。工件j的完工时间为Cj。

假设由两人合作一起加工这批工件，每人提供一台机器用于加工这批工件中的一部分，每个工件只需被加工一次。不妨设X1和X2为工件集J的两个互不相交的子集，即。集合Xi(i=1，2)内的工件由第i人加工，每加工单位时间的工件将使第i人获得bi个单位的收益，以最小的最大完工时间作为加工成本，于是收益函数可表示为

合作收益函数为

现在解决问题的关键就是要找到一个合适的工件分配方案，让参与合作的两人都能获得满意的收益，从而愿意合作。注意到α和t0都是常数，因此收益函数ui与Xi内工件的加工次序无关，仅与Xi内工件个数有关，为此记X1＝｛1，2，…，k｝，X2＝｛k+1，k+2，…，n｝(1≤k≤n－1)，因此k就是问题(P)的决策变量。于是，收益函数为

根据文献[4]的三参数表示法，该问题可记为

合作收益函数为

其中(e1，e2)为合作博弈论中的无协议点[14]，满足

2 问题的求解

假设参数α、t0、b1、b2都是正整数，e1、e2是非负整数，因此本文考虑的是离散情况下的排序博弈问题。合作双方愿意合作的首要前提是他们各自的合作收益大于零，即vi＞0(i=1，2)，从而必有参数bi≥2(i=1，2)。否则，若b1＝1，那么v1＝－t0－e1＜0，显然这样的合作无法让第一个参与人满意；同样地，如果b2＝1，则v1＝－t0－e2＜0。

为方便叙述，令A＝(b1－1)t0，B＝(b2－1)t0，C＝b1t0＋e1，D＝b2t0＋e2，从而合作收益函数可记为

注意到参数bi≥2(i=1，2)，t0是正整数，e1、e2是非负整数，知A＞0，B＞0，C＞0，D＞0。

如果存在某个正整数k(1≤k≤n－1)，使合作收益函数vi(k)＞0(i=1，2)，那么这样的正整数k就是问题(P)的可行解。根据式(1)、式(2)知

充分性。若正整数k满足ξl≤k≤ξu，注意到ξl≥ξ1，ξu≤ξ2，从而有ξ1≤ξl≤k≤ξu≤ξ2。所以，必有合作收益函数vi(k)＞0(i=1，2)。

进一步，容易证明最优解k*必定在区间[ξl，ξu]上。

注意到C＞A，D＞B，从而有ξ1＞0，ξ2＜n。又由于ξ1＜k＜ξ2及1≤k≤n－1(n≥2)，可知0＜ξ1＜n－1， 1＜ξ2＜n。从而

所以，若问题(P)有解，那么最优解k*必定在区间[ξl，ξu]上。

当参数α、t0、b1、b2、e1、e2以及n都给定时，那么上式第一项和第四项都是常数。

令f( k ) = AD (1+α)k+ BC(1+α)n−k，当函数f(k)取到最小值，那么目标函数v(k)v(k)最大。

12

注意到AD(1+α)k＞0，BC(1+α)n-k＞0，根据均值不等式有

显然，当参数α、t0、b1、b2、e1、e2以及n都给定时，为定值。

当且仅当AD(1+α)k＝BC(1+α)n-k时，即时，函数f(k)取到最小值。

若1＜ξ＜n－1，如果ξ恰好为整数，那么排序博弈问题的最优解k*＝ξ。否则，比较的大小。注意到，使函数f(k)较小的正整数k，对应的目标函数v1(k)v2(k)最大，因此正整数k就是所求的最优解 。

3 结论

本文研究这样一类排序博弈问题：两人合作加工一批工件，每人提供一台机器用于加工工件，每个工件的加工时间是其开工时间的简单线性函数，每个工件只需被加工一次，后一个工件紧接着前一个工件进行加工，以最小的最大完工时间作为加工成本，通过分析可行解的情况，得到了最优工件划分方案。对排序博弈问题的研究尚处于初始阶段，后续还有很多排序博弈问题值得研究，如工件有窗口交货期限制的排序博弈问题，工件须加工2～3个工序的排序博弈问题等。

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

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

[3] NASH J F. Two person cooperative games[J]. Econometrica，1953，21(1)：128-140.

[4] 金霁，顾燕红，唐国春.最大完工时间排序的两人合作博弈[J].上海第二工业大学学报，2011，28(1)：14-17.

[5] 窦文卿，顾燕红，唐国春.总完工时间排序两人合作博弈的纳什博弈解[J].重庆师范大学学报(自然科学版)，2012，29(5)：1-5.

[6] GU Yanhong，FAN Jing，TANG Guochun，et al. Maximum latency scheduling problem on two-person cooperative games[J]. Journal of Combinatorial Optimization，2013，26：71-81.

[7] 金霁.加工时间可变的总完工时间排序两人合作博弈问题[J].苏州市职业大学学报，2013，24(3)：35-39，74.

[8] 金霁.加工时间是开工时间线性函数的两人合作排序博弈问题[J].南京师范大学学报(工程技术版)，2012，12(4)：87-92.

[9] 顾燕红，金霁，唐国春.加工时间可变最大流程时间排序的纳什合作博弈[J].重庆师范大学学报(自然科学版)，2012，29(4)，18-23.

[10] 邱言玲，高淑萍，张宝玉.基于加权总完工时间的两人合作排序博弈[J].重庆师范大学学报(自然科学版)，2014，31(6)：9-15.

[11] GU Y H，GOH M，CHEN Q L，et al. A new two-party bargaining mechanism[J]. Journal of Combinatorial Optimization，2013，25：135-163.

[12] GAN Xiaobing，GU Yanhong，GEORGE 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.

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

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

(责任编辑：沈凤英)

The Bargaining Problem on Scheduling with Linear Processing Time of Its Start Time

JIN Ji

(Department of Mathematics and Physics，Suzhou Vocational University，Suzhou 215104，China)

There is such a situation in workpiece processing： a processor is not able to undertake all processing jobs alone.So the new scheduling problems come into being， where many people work together to process a batch of workpieces. In this paper， we discuss the problem where two persons process a batch of workpieces by cooperation. Each person is offered a single machine and does each job with linear processing time of its start time， and his processing cost is defined as the smaller maximum makespan. An optimal division of those jobs is proposed and assigned to the two persons respectively so that each participant can get a satisfactory return and be willing to cooperate.

processing time；linear function；maximum makespan；cooperative profit；scheduling

O221.7

A

1008-5475(2017)01-0041-04

10.16219/j.cnki.szxbzk.2017.01.009

2016-11-16；

2016-12-14

金 霁(1978-)，女，江苏苏州人，副教授，硕士，主要从事排序研究。

金霁.工件加工时间是开工时间线性函数的排序博弈问题[J].苏州市职业大学学报，2017，28(1)：41-44.