排序对策的一个新的收益分配准则

周意元, 张 强

(1.北京理工大学 管理与经济学院，北京 100081; 2.三峡大学 理学院，湖北 宜昌 443002)



排序对策的一个新的收益分配准则

周意元1,2, 张 强1

(1.北京理工大学 管理与经济学院，北京 100081; 2.三峡大学 理学院，湖北 宜昌 443002)

针对一个机器的排序问题，给出了排序问题中成本增加量的表达式，提出了收益分配的不小于成本增加量准则。针对一类特殊的排序问题，给出一个符合不小于成本增加量分配准则的解，并证明了它满足有效性，哑元性和单调性。结合一个算例，对本文的提出的方法进行了分析验证。

合作对策；排序问题；收益分配准则；核心

0 引言

排序对策(sequencing game)是Curiel等[1]为了利用合作对策的方法解决如下的排序问题而提出来的。有限个局中人在一个机器前按初始顺序排队等待服务，每位局中人有一个工件需要在这个机器上处理。局中人在等待他的工件被处理完的过程中有成本，这些成本与完工时间成正比，队列的总成本是各局中人成本之和。可以通过调整局中人的顺序使总成本最小，相对于初始顺序时的总成本，减少的总成本可以认为是所有局中人合作而产生的收益，那么这些收益该如何在所有局中人之间分配？文献[1]提出了收益分配的EGS准则(equal gain splitting rule), 它将相邻局中人通过交换顺序而减少的成本平均分配给这两位局中人，EGS准则所产生的解属于排序对策的核心。

此后，学者们对排序问题和排序对策中的工件处理时间、机器数量、初始顺序等进行了拓展研究[2～6]。……