北大中文核心期刊
中国科学引文数据库（CSCD）来源期刊
中国科技核心期刊
入选数学领域高质量科技期刊
Scopus
EBSCO 

运筹学学报 ›› 2018, Vol. 22 ›› Issue (1): 87-96.doi: 10.15960/j.cnki.issn.1007-6093.2018.01.007

• 运筹学 • 上一篇    下一篇

一类博弈排序问题的纳什均衡存在性证明   

张龙1 张玉忠1,*  柏庆国1   

  1. 1. 曲阜师范大学管理学院运筹学研究院, 山东日照 276826
  • 收稿日期:2016-07-24 出版日期:2018-03-15 发布日期:2018-03-15
  • 通讯作者: 张玉忠 E-mail: yuzhongrz@163.com
  • 基金资助:

    国家自然科学基金(Nos.11771251, 71771138), 山东省自然科学基金(Nos. ZR2015GZ009, ZR2017MG009), 曲阜师范大学博士科研创新资助基金

Existence of Nash equilibria in scheduling game on limited machines with activation cost

ZHANG Long1  ZHANG Yuzhong1,*  BAI Qingguo1   

  1. 1. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China
  • Received:2016-07-24 Online:2018-03-15 Published:2018-03-15

PDF

555

摘要：

研究机器带有激活费用的博弈排序问题. 机器集由两类组成: 一类是速度为1、 激活费用为B的k_1台同型机; 另一类是速度为a(>1)、激活费用为aB的k_2台同型机,
其中k_1与k_2是任意正整数. 工件作为``局中人", 其目的是极小化自身的费用, 工件的费用是由其所在机器的负载和其所承担的激活费用组成, 其中工件承担的激活费用与工件的加工时间成正比. 针对不同的情况, 设计不同的算法, 并证明各算法得到的排序都是纳什均衡.

关键词: 博弈排序, 纳什均衡, 激活费用, 成比例分配

Abstract:

In this paper, we investigate game scheduling of jobs in two kinds of limited number of uniform machines with activation cost. The number of machines with speed 1 and activation cost B in the first category is limited. Similarly, the number of machines with speed a(>1) and activation cost aB in the second category is also limited.  Jobs are served as self-interested players who choose a machine with the objective of minimizing their individual cost without considering other players' cost and the total social cost. A job's cost is composed of its machine's load and its share in the machine's activation cost, which is proportionally shared with respect to its size. We design different algorithms for different cases. Then, every assignment obtained by each different algorithm is proved to be a Nash equilibrium.

Key words: game scheduling, Nash equilibrium, activation cost, proportional sharing rule