工件有交货期的两人合作排序博弈问题

Two-Person Cooperative Games on Processing Jobs with Due Date

随着社会发展与进步,合作共赢已经成为一种共识,但人们出于自身利益的考虑,在合作的过程中总是希望自身利益最大,这就是合作博弈.合作博弈研究的问题就是要找到一个恰当的收益分配方案,使参加合作的所有利益主体愿意合作.这里考虑两人合作共同加工一批有交货期的工件排序博弈问题.每人提供一台机器用于工件的加工,工件加工时间是开工时间的简单线性函数,以最小的最大延误作为加工成本.设计一个多项式时间动态规划算法寻找到一个合理的博弈解集,由合作双方在解集中选定最终的合作收益分配方案,即找到最终的博弈解.

Along with the social progress and development, cooperation and win-win has become a consensus. But each people will persue the maximization of their interests in the process of cooperation out of their own interests. It is called cooperative games. The key problem of cooperative games is to determine a proper profit allocation scheme so as to sustain and implement the related alliance. In this paper, a two-person cooperative game problem is considered, where the two persons jointly undertake a large-scale project including a number of jobs＇ the processing time of each job is a linear function of the start time point,each person offers a single machine to process the jobs with due date, and his processing cost is defined as his minimized maximal tardiness. A polynomial dynamic programming algorithm is designed to find a reasonable bargaining solution set, which is used by the two persons to negotiate the final cooperative profit allocation scheme, i.e. the final bargaining solution.