运筹学

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

展开
  • 1. 曲阜师范大学管理学院运筹学研究院, 山东日照 276826

收稿日期: 2016-07-24

  网络出版日期: 2018-03-15

基金资助

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

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

Expand
  • 1. Institute of Operations Research, School of Management, Qufu Normal University, Rizhao 276826, Shandong, China

Received date: 2016-07-24

  Online published: 2018-03-15

摘要

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

本文引用格式

张龙, 张玉忠, 柏庆国 . 一类博弈排序问题的纳什均衡存在性证明   [J]. 运筹学学报, 2018 , 22(1) : 87 -96 . DOI: 10.15960/j.cnki.issn.1007-6093.2018.01.007

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.

文章导航

/