标题

Transcription

1 202 年 7 月重庆师范大学学报 ( 自然科学版 ) Jul.202 第 29 卷第 4 期 JournalofChongqingNormalUniversity(NaturalScience) Vol.29 No.4 运筹学与控制论 DOI:CNKI:50-65/N * 加工时间可变最大流程时间排序的纳什合作博弈 顾燕红, 金霁 2, 唐国春 3 (. 深圳大学数学与计算科学学院应用数学系, 广东深圳 58067; 2. 苏州市职业大学基础部, 江苏苏州 2504;3. 上海第二工业大学经济管理学院, 上海 20209) 摘要 : 在现实世界中, 往往存在一人无法承担一个项目中全部工件加工任务的情况, 这就要考虑由多人合作加工的情形本文研究工件加工时间是开工时间线性函数的情况下, 以最小的最大流程时间作为加工成本的 ( 两人 ) 纳什合作 ( 加工 ) 博弈问题, 每人有一台用于加工工件的机器通过确定这批工件的一个恰当划分, 把工件分配给两台机器, 使得相应的合作 ( 加工 ) 收益分配合理, 能够被双方接受关键词 : 排序 ; 纳什博弈 ; 合作收益 ; 最大流程 ; 线性函数中图分类号 :O22.7 文献标志码 :A 文章编号 : (202) 经典排序问题中只有一个 人 ( 一个自然人或 某一个集体 ) 参与工件加工, 然而由于资金 技术和 时间等原因, 有时一个 人 无法独立承担一个项目 中所有工件的加工任务, 这时就可能要考虑寻找合 作者这种合作建立在存在所有参与者满意的工件 分配方案的基础上, 这就是合作博弈 [-2] 纳什在研究两人合作博弈问题时定义了纳 什博弈解 [] (Nashbargainingsolution,NBS), 即是 使得两人合作收益乘积最大的利益分配方案由 此分配方案出发, 任一人为增加自己的收益而主张 的分配方案改变都会导致另一个人的收益减少, 即 此分配方案是帕累托有效的 (Paretoeficiency) [] 纳什进一步证明 : 如果可行博弈解的连续帕累托 有效 ( 子 ) 集是闭凹的, 那么 NBS 唯一 当上述帕累托有效 ( 子 ) 集不连续时, 称为离散 ( 两人 ) 合作博弈 Nagahisa 和 Tanaka [3],Marioṯ ti [4] 和 Lahiri [5] 在离散合作博弈模型的研究中并没 有假设合作收益函数取整数值, 而是对离散的帕累 托有效集提出某些假定, 得到了类似 NBS 唯一性的 性质陈全乐开创性地将 NBS 应用到整数化的 离散合作博弈模型中, 考虑成对的两个最优化目标 函数 Pt((r,r2)):rvv2+r2min {v 2,v 2 2},(t=, 2) 其中,vi 是第 i 人的整数取值的合作收益,ri= 0,,,(i=,2),(r,r2) 是 maxvv2 与 max: min {v 2,v 2 2} 的权重系数向量事实上, 当 r =, r2=0 时, 就是最大化纳什的目标函数 vv2 陈全 乐说明了满足 maxvv2 的最优解 (v *,v 2 * ) 确定 的利益分配方案是在充分考虑能力高的一方收益情 况下兼顾公平的结果而目标函数 max:min {v 2,v 2 2} 则强调合作收益分配的公平性为此, 将纳什的最 优化模型加以扩展, 通过选取不同的权重系数向量 (r,r2) 得到满足不同主观决策要求 或偏重效 率或偏重公平的最优解集 (Discretebargainingsolutions,DBS), 合作双方在 DBS 解集的基础上通过 协商确定最终的利益分配方案, 该方案未必是帕累 托有效的, 但却是双方都能接受的 [7] 顾燕红对文献 中提出的 Pt((r,r2)) 进 行改造, 证明使函数 Pt((r,r2)) 最大的 (v *,v * 2 ) 也是帕累托有效的, 并改进文献 中提出的用于实 现此离散博弈的博弈机制 陈全乐首先对两人合作加工工件的整数化离 散合作博弈模型进行研究在此博弈情形中, 每个 人的合作收益函数中的加工成本项是经典排序问 题中的某个最小化费用金霁等最早给出此博 弈情形的中文名称 : 排序博弈文献 [6,8-2] 中对 各种不同的最小化费用确定的加工成本, 设计求 解 maxpt((r,r2)) 的算法陈全乐和甘小冰 [0] 等设计的动态规划算法适用于所有的 (r,r2) * 收稿日期 : 网络出版时间 : :5:00 作者简介 : 顾燕红, 女, 副教授, 博士, 研究方向为组合优化 ; 通讯作者 : 金霁, szjinji@26.com 网络出版地址 :htp://

2 第 4 期 顾燕红, 等 : 加工时间可变最大流程时间排序的纳什合作博弈 9 文献 [2] 中的两个动态规划虽仅针对 maxvv2, 但 也可以求解任意其他的 maxpt((r,r2)) 当 r=,r2=0 且加工成本较为简单时, 金霁等和窦文 [9] [] 卿等提出公式化的结论顾燕红和陈全乐考 虑一方的能力大大高于另一方, 并由此在协商工件 分配方案时有一些特权的情况当合作收益函数与 工件的排序无关时, 证明这个问题等价于背包问题, 可以用求解背包问题的算法来确定双方都满意的收 益分配方案 与文献 [8-9] 相同, 本文研究问题 maxvv2 假 定每人有一台机器用于工件加工, 每个工件只需加 工一次, 加工时间是其开工时间的函数研究这类 加工时间与开工时间有关的问题有着积极的现实意 义, 它们广泛存在于钢铁 塑料工业和医疗等领 域 [3] 例如, 有的工件加工有一定的温度要求, 如 果工件在加工前温度不够, 那么无论是重新加温使 其满足温度要求, 还是在不满足温度要求下进行低 温加工, 都将导致加工时间的增加加工成本是取 为最小的最大流程时间 minfmax 第 2 节讨论工件 的加工时间是开工时间的线性函数的情形, 第 3 节 讨论工件的加工时间是开工时间的分段线性函数的 情形这两个问题都能在多项式时间内求解 问题的提出 设有工件集 J={,2,,n}, 所有工件在时刻 t0(>0) 之后开始加工, 每个工件只需加工一次工 件 j 的加工时间 pj 是关于其开始加工时间 t( t0) 的函数 pj=f(t), 工件 j 的完工时间 C j 也就是其紧 后工件的开始加工时间, 工件 j 的流程时间 F j = C j -t0 现在由两人合作一起加工这批工件, 也就是 要将工件集 J 划分为两个互不相交的集合 X 和 X2, 满足 :X X2=J,X X2=Æ, 集合 Xi(i=, 2) 内的工件由第 i 人加工假设每人有一台加工机 器, 每加工单位时间的工件会使第 i 人获得 bi 个单位 的收益如果以最小的最大流程时间 minf i max 作为加工成本, 那么收益函数 ui=bi pj-minf i max 本文第 2 节研究工件加工时间 pj=f(t)=αt 的情 形, 其中 α(>0) 为比例系数 ; 第 3 节研究工件加工时间 pj=f(t)= αt,t<t 的情形, 其中 { T 是一个给 αt,t T 定的常数对于工件的加工时间是这两种函数时, 这些工件都是相同的, 都是从 t0 时刻可以开始加工, 工件加工时间都只与开始加工的 位置 有关, 而且 比例系数是常数 α, 所以划分工件集时只需要考虑 工件的个数此时 X X2 内的工件已经是 SPT 序 ( 最小加工时间序 ), 已经使最大流程时间 F i max 为最 小, 因而不失一般性,X 和 X2 可记为 X= {,2,,k} 和 X2={k+,k+2,,n} 从而 k 是把工件 集 J 划分成为两部分分别给两台机器加工的决策变 量此时, 第 台机器加工的工件数是 k, 第 2 台机 器加工的工件数是 n-k 因此收益函数 ui=ui(k)=bi pj -minf i max=bi pj -F i max = bi pj - ç p j X i æ è ö j =(bi -), pj ø 其中 i=,2; 并且,u(0)=0 或 u2(n)=0 分别是 第 台机器或第 2 台机器没有分配工件, 都由第 2 台机器或第 台机器加工所有工件时的收益值于 是合作收益函数 vi=vi(k)=ui(k)-ei,i=,2, [4] 其中 (e,e2) 是合作博弈论中的无协议点 e u(0)=0,e2 u2(n)=0, 其中 ei 是第 i 人不参加这次合作而参与别的商业活 动所能获得的最低收益, 也就是第 i 人参加这个合 作的机会成本由此, 只需要讨论 k n- 的情 况根据文献 离散化的假设 ἀ,t0,bi 和 p 都取 正整数值, 因而都大于或者等于,ei 取非负整数值 本文研究以最小的流程时间作为加工成本使得 两人的合作收益函数的乘积 vv2 为最大的两人排 序合作博弈问题按照参考文献 定义的三参数 表示法, 此问题 (P) 可以表示为 G2 pj=f(t)vv2/fmax 如果存在某个 k,k {,2,,n-}, 使得合作收益 函数 vi(k)>0 (i=,2), 那么问题 (P) 的最优解 k * 有 v(k * )v2(k * )=max{v(k)v2(k) v(k)>0, v2(k)>0,k Î{,2,,n-}} 因此, 问题 (P) 可以在 O(n) 时间内解决 2 加工时间是开工时间线性函数的排序博弈问题 本节中工件 j 的加工时间为 pj=αt, 所以 X 中 各个工件的完工时间为 C=t0+αt0=(+α)t0, C2=C+αC=(+α) 2 t0, Ck=Ck-+αCk-=(+α) k t0

3 20 重庆师范大学学报 ( 自然科学版 ) htp:// 第 29 卷 同样地, 注意到 X2 内的工件也从时刻 t0 开始加工, 所以 X2 中各个工件的完工时间为 Ck+=t0+αt0=(+α)t0, Ck+2=Ck++αCk+=(+α) 2 t0, Cn=Cn-+αCn-=(+α) n-k t0 因此, 收益函数为 u(k)=u(x)=(b -) j X pj = (b-)(ck-t0)=t0(b-)[(+α) k -], u2(k)=u2(x2)=(b2 -) j X2 pj = (b2 -)(Cn -t0)=t0(b2-)[(+α) n-k -] 由于收益函数要满足 ui(xi)>0, 所以必须有 bi> (i=,2) 合作收益函数为 v(k)=v(x)= u(x)-e=t0(b-)[(+α) k -A], () v2(k)=v2(x2)= u2(x2)-e2=t0(b2-)[(+α) n-k -B], (2) 其中 A=,B e ( - ) +,B= e2 t0 ( b2 - ) + t0 b 注意到 ei 0,bi> (i=,2),t0, 故有 A 因为两人要合作, 所以要满足 vi(k)>0(i=, 2), 从而有 β<k<β2, (3) 其中 β= lna ln(+α), β2=n- lnb ln(+α) 注意到 A,B ἀ, 知 β 0, β 2 n (4) 又由于两人要进行合作, 故必有 结合 (3) (4) 以及 (5) 式, 知 k n- (5) 0 β<n-,<β2 n, β <β2,n 2 (6) 由 () (2) 式, 得 v(k)v2(k)= t 2 0(b-)(b2-)[(+α) k -A][(+α) n-k -B]= t 2 0(b-)(b2-)[(+α) n +AB]- t 2 0(b-)(b2-)[A(+α) n-k +B(+α) k ] (7) 当参数 bi,ei(i=,2),t0 α 以及 n 都给定的时 候,(7) 式中的第一项是常数为此, 令 φ ( k)= A(+α) n-k +B(+α) k, 只要使 φ ( k) 最小, 目标函 数 v(k)v2(k) 就最大 注意到 A(+α) n-k >0,B(+α) k >0, 所以根 据均值不等式, 得 φ ( k)=a(+α) n-k +B(+α) k 2 AB (+α) n ( 定值 ), (8) 当且仅当 A (+α) n-k =B (+α) k 时, 即 k= 2 ( β+β2) 时, φ (k) 取到最小值 2 AB (+α) n 事实上, 2 ( β+β2) 未必是整数, 故令 β= 2 ( β+ β2), 且由 (6) 式知 性质 2 < β<n- 2 ( 9) 加工时间是开工时间线性函数的排序 博弈问题 G2 pj=αt vv2/fmax 有解的充要条件是 βl βr, 其中 βl=ë β û+, β r=é β 2 ù- 证明根据 (3) (5) 式有, 排序博弈问题 (P) 有 解等价于 ( β, β 2) [,n-] Æ, 即至少存在一个 正整数 k, 有 k ( β, β 2) [,n-] 注意到 k 是 整数, 于是令 βl=ë β û+, β r=é β 2 ù- 由于 β 和 β2 可能是整数, 所以不能令 βl=é β ù-, β r=ë β 2 û+ 由 (6) 式知, βl n-, βr n- 故问题 (P) 有解等价于 βl βr, 即闭区间 [ β l, β r] 中至少有 一个正整数 k 定理 证毕 如果加工时间是开工时间线性函数的 两人合作排序博弈问题 G2 pj=αtvv2/fmax 存在 正整数解 k, 那么其最优解 ( 集 ) 为 a) 如果 2 < β, 那么该排序博弈问题的最优 解 k * = b) 如果 <β<n-, 当 β 为整数时, 那么该排序 博弈问题的最优解 k * =β ; 否则, 若 φ (ë β û) <φ (é β ù), 那么该排序博弈问题的最优解 k * =ë β û; 若 φ (ë β û) > φ (é β ù), 那么该排序博弈问题的最优解 k * =é β ù; 若 φ (ë β û) =φ (é β ù), 那么该排序博弈问题的最优解集为 {ë β û,é β ù} c) 如果 n- β<n- 2, 那么该排序博弈问题 的最优解 k * =n- 证明 性质 表明, 加工时间是开工时间线性 函数的排序博弈问题 G2 pj=αt vv2/fmax 的最优 解 ( 集 ) 只能是位于闭区间 [ β l, β r] 中的正整数 a) 当 2 < β 时, 有 <β +β2 2 注意到 0 β<β2, 故有 2β<β+β2 2, 所以 0 β< 因 此, β l=ë β û+=

4 第 4 期 顾燕红, 等 : 加工时间可变最大流程时间排序的纳什合作博弈 2 另一方面, 由 <β+β2 2, β 0 以及 β2>, 得 <β2 2, 所以 βr=é β 2 ù-= 由于 βl=βr=, 从而该排序博弈问题的最优解 k * = b) 当 <β<n- 时, 如果 β 为整数, 那么该排 序博弈问题的最优解 k * =β ; 否则, 比较 φ (ë β û) 与 φ (é β ù) 的大小所以结论 b) 成立 c) 当 n- β<n- 2 时, 类似情况 a) 的分析有 βl=βr=n-, 从而该排序博弈问题的最优解 k * = n- 证毕 3 加工时间是开工时间的分段线性函数的排序博弈问题 本节中工件 j 的加工时间为 pj = αt,t<t { αt,t T 如果 X 和 X2 内工件开始加工时间 t0 T, 此时工 件 j 的加工时间 pj=αt, 是一个固定的常数, 这就 是文献 所讨论的问题如果集合 X 和 X2 内最 后一个工件的完工时间分别为 Ck=(+α) k t0 T,Cn=(+α) n-k t0 T, 此时该问题就是第 2 节中讨论的情形因此假定 t0<t, 且考虑 X X2 内都有临界工件的情况不 妨设 X 内第 ρ(2 ρ k-) 个工件为临界工件, X2 内第 ρ2(2 ρ2 n-k-) 个工件为临界工件, 即 C ρ -=(+α) ρ - t0<t,c ρ =(+α) ρ t0 T, Ck+ρ 2 -=(+α) ρ 2 - t0<t,ck+ρ 2 =(+α) ρ 2 t0 T, 事实上, 由于 α t0 T 都是常数, 所以 ρ=ρ2=ρ, 从 而 C ρ -=Ck+ρ 2 -=(+α) ρ- t0<t, C ρ =Ck+ρ 2 =(+α) ρ t0 T 于是 X 中各个工件的完工时间为 C=t0+αt0=(+α)t0, C ρ -=C ρ-=(+α) ρ- t0<t, C ρ =C ρ =(+α) ρ t0 T, C ρ +=C ρ+=c ρ +αt=(+α) ρ t0+αt, Ck=(+α) ρ t0+(k-ρ ) αt X2 中各个工件的完工时间为 Ck+=t0+αt0=(+α)t0, Ck+ρ-=(+α) ρ- t0<t, Ck+ρ=(+α) ρ t0 T, Ck+ρ+=Ck+ρ+αT=(+α) ρ t0+αt, 此时, 收益函数为 Cn=(+α) ρ t0+(n-k-ρ ) αt u(k)=u(x)=(b-) j X pj=(b-)(ck-t0)= (b-)[(+α) ρ t0+(k-ρ ) αt-t0], u2(k)=u2(x2)=(b2-) j X2 pj=(b2-)(cn-t0) (b2-)[(+α) ρ t0+(n-k-ρ ) αt-t0] 由于 ui(xi)>0, 所以 bi>,i=,2 其中 合作收益函数为 v(k)=v(x)=u(x)-e= αt(b-)(k-ρ+c), (0) v2(k)=v2(x2)=u2(x2)-e2= αt(b2-)(n-k-ρ+d) () (+α) C= t0 ρ (b-)+e αt -t0 αt(b-), (+α) D= t0 ρ (b2-)+e2 αt -t0 αt(b2-) 因为 vi(k)>0(i=,2), 所以 其中 θ=ρ-c,θ2=n-( ρ -D) θ<k<θ2, (2) 又注意到 2 ρ k- 且 2 ρ n-k-, 所以 并且由 (3) 式, 有 结合 (2) (3) 式, 知 性质 2 排序博弈问题 3 k n-3 (3) n 6 (4) θ<n-3,θ2>3,θ<θ2 (5) 加工时间是开工时间分段线性函数的 G2 pj=αt,t<t;pj=αt,t T vv2/fmax 有解的充要条件是 θl θr, 其中 θl= ëθ û+,θr= éθ2 ù- 证明同性质, 略 由 (0) (), 得 v(k)v2(k)= α 2 T 2 (b-)(b2-)(k-θ)(θ2-k) (6) 即合作收益函数的乘积 v(k)v2(k) 是关于决策变量 k 的二次函数, 且开口向下由于其对称轴 2 ( θ+ θ2) 未必是整数, 故令 θ= 2 ( θ+θ2) 定理 2 如果加工时间是开工时间的分段线性

5 2 重庆师范大学学报 ( 自然科学版 ) htp:// 第 29 卷 函数的排序博弈问题 G2 pj=αt,t<t;pj=αt,t T vv2/fmax 存在正整数解 k, 那么其最优解 ( 集 ) 为 : a) 当 θ 3 时, 该排序博弈问题的最优解 k * =3 b) 当 3<θ<n-3 时, 若 θ 为整数, 则该排序博 弈问题的最优解 k * =θ; 否则, 如果 θ- ëθ û<θéθù, 则该排序博弈问题的最优解 k * =ëθû, 如果 θ- ëθû>θ-éθù, 则该排序博弈问题的最优解 k * =éθù, 如果 θ-ëθû=θ-éθ ù 0, 则该排序博弈问题的最优 解集为 {ëθû,éθù} c) 当 θ n-3 时, 该排序博弈问题的最优解 k * =n-3 证明 对 θ θ2 分 4 种情况进行讨论 ) 若 θ<3,θ2>n-3, 则 θl 3,θr n-3, 即 θl<θr, 根据性质 2, 问题必定有正整数解 k 注意到 该正整数解 k 必定在闭区间 [3,n-3] 上, 所以又分 3 种情况 k * =3 如果 θ 3, 那么该排序博弈问题的最优解 2 如果 3<θ<n-3, 当 θ 为整数时, 那么该排 序博弈问题的最优解 k * =θ; 否则, 如果 θ- ëθ û< θ-éθù, 则该排序博弈问题的最优解 k * =ëθû, 如果 θ-ëθû>θ-éθù, 则该排序博弈问题的最优解 k * = éθù, 如果 θ-ëθû=θ-éθù 0, 则该排序博弈问题的 最优解集为 {ëθû,éθù} 3 如果 θ n-3, 那么该排序博弈问题的最优 解 k * =n-3 2) 若 θ<3,3<θ2 n-3, 则 θl 3,3 θr n- 4, 即 θl θr, 因此问题必定有正整数解 k,k [3,θr] 又 θ= 2 ( θ+θ2), 故 θ< n 2 注意到 n 2 = n- n 以及 n 6, 所以有 n 2 2 n-3, 即总有 θ<n-3 因此, 类似 ) 的分析, 有结论 a) b) 成立 3) 若 3 θ<n-3,θ2>n-3, 则 4 θl n-3, θr n-3, 即 θl θr, 因此问题在闭区间 [θl,n-3] 上 必定有正整数解 k 同样由 θ= 2 ( θ+θ2) 知,θ> n 2 3, 即总有 θ>3 同理可知结论 b) c) 成立 4) 若 3 θ <n-3,3<θ2 n-3, 则 4 θl n-3,3 θr n-4 只要 θl θr, 则问题必定有解, 且正整数解 k [θl,θr] 由 θ= 2 ( θ+θ2) 知,3< θ<n-3 所以, 当 θ 为整数时, 那么该排序博弈问 题的最优解 k * =θ; 否则, 如果 θ- ëθ û<θ- éθ ù, 则该排序博弈问题的最优解 k * = ëθ û, 如果 θ- ëθ û> θ-éθù, 则该排序博弈问题的最优解 k * =éθù, 如果 θ-ëθû=θ-éθù 0, 则该排序博弈问题的最优解集为 {ëθû,éθù} 综合上述 4 种情况, 定理 2 成立证毕 4 总结 本文考虑了两人合作共同加工一批工件, 工件的加工时间是开工时间的函数, 当以最小的最大流程时间为加工成本时, 定理 和定理 2 分别给出加工时间是开工时间的线形函数和分段线形函数时的最优解 ( 集 )该最优解 ( 集 ) 充分体现了效率原则, 今后可以考虑强调公平性的优化目标 max:min {v 2,v 2 2}, 或考虑优化目标函数组 Pt((r,r2)), 通过选取不同的 (r,r2) 得到一组最优工件划分解集, 从而使模型能更好地贴近现实, 更好地为决策提供依据致谢 : 本文的研究是在陈全乐博士的提议和资助下完成的, 对此我们深表感谢! 我们也感谢上海第二工业大学排序研究室师生的参与 讨论和帮助参考文献 : []NashJF.Thebargaining problem [J].Econometrica, 950,8(2): [2]NashJF.Twopersoncooperativegames[J].Economeṯ rica,953,2(): [3]Nagahisa R,Tanaka M.An axiomatization ofthe Kalai- Smorodinskysolutionwhenthefeasiblesetscanbefinite [J].SocialChoiceand Welfare,2002,9(4): [4]MariotiM.Nashbargainingtheorywhenthenumberof alternativescanbefinite[j].socialchoiceand Welfare, 998,5(3): [5]LahiriS.Axiomaticcharacterization ofthe Nash and Kalai-Smorodinsky solutions for discrete bargaining problems[j].puremathematicsandapplications,2003,4 (3): ChenQL.A Newdiscretebargainingmodelonjobpaṟ titionbetweentwo manufacturers[d].hongkong:the ChineseUniversityofHongKong,2006. [7]GuY H,Goh M,ChenQ L,etal.Anewtwo-partybaṟ gaining mechanism [J/OL].Journalof Combinatorial Optimization.Availableonline(20--02)[ ]. htp://

6 Vol.29No.4 JournalofChongqingNormalUniversity(NaturalScience) htp:// 23 hh62/. 金霁, 顾燕红, 唐国春. 最大完工时间排序的两人合作博弈 [J]. 上海第二工业大学学报,20,28():4-7. [9] 窦文卿, 顾燕红, 唐国春. 总完工时间排序的两人合作博弈 [J]. 重庆师范大学学报 : 自然科学版,202,29(5): 待刊发. [0]GanXB,GuY H,VairaktarakisG L,etal.Ascheduling problem with one producer and the bargaining counterpartwithtwoproducers[j].lecture Notesin ComputerScience,2007,464: []GuY H,ChenQL.Someextendedknapsackproblems involvingjobpartitionbetweentwoparties[j].appl MathJChineseUnivSerB,2007,22(3): [2]Gu Y H,FanJ,Tang G C,etal.Maximum latency schedulingproblem ontwo-personcooperativegames [J/OL].Journal of Combinatorial Optimization,In Press(20--6)[ ].htp:// [3]ChengTCE,DingQ,LinB M T.Aconcisesurveyof scheduling withtimeḏependentprocessingtime[j]. EuropeanJournalofOperationalResearch,2004,52:-3. [4]Muthoo A.Bargainingtheory withapplications[m]. Cambridge,United Kingdom:Cambridge UniversityPress, 999. OperationsResearchandCybernetics NashBargainingon MaximumFlowTimeSchedulingwithChangeableProcesingTime GU Yaṉhong,JINJi 2,TANG Guo-chun 3 (.Dept.ofApplied Mathematics,ShenzhenUniversity,ShenzhenGuangdong58060; 2.Dept.ofFoundation,SuzhouVocationalUniversity,SuzhouJiangsu2504; 3.Economics& ManagementSchool,ShanghaiSecondPolytechnicUniversity,Shanghai20209,China) Abstract:Intherealworld,thereoftenexiststhesituationwhereonepersonisnotabletoundertakealthejobsaloneinalarge project.inthispaper,weconsiderthesituationwheretwopersonscooperateintheperformanceofaproject.wediscussthe (two-person)nashbargainingproblem,wherejobprocessingtimeisalinearfunctionofitsstarttime,eachpersonofersa singlemachinetoprocessjobs,andhisprocessingcostisdefinedashisminimizedmaximumflowtime.byproposingaproper divisionofthosejobs,weusethetwocorrespondingsubsetofjobs,assignedtothetwopersonsrespectively,toyieldareasoṉ ablecooperative(processing)profitalocationschemeacceptabletothem. Keywords:scheduling;Nashbargaining;cooperativeprofit;maximumflowtime;linearfunction ( 责任编辑黄颖 )