文档介绍：谨以此论文献给我的恩师和我的家人
---------- 赵婷
三类平行机博弈排序问题的协调机制研究
学位论文答辩日期:
指导教师签字:
答辩委员会成员签字:
独创声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的
研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其
他人已经发表或撰写过的研究成果, 也不包含未获得
(注:如没有其他需要特别声明的,本栏可空)或其他教育机构的学位或证书使
用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明
确的说明并表示谢意。
学位论文作者签名: 签字日期: 年月日
---------------------------------------------------------------------
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定,并同意以下
事项:
1、学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许
论文被查阅和借阅。
2、学校可以将学位论文的全部或部分内容编入有关数据库进行检索,可以
采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权清华大学“中
国学术期刊(光盘版)电子杂志社”KI《中国知识资源总库》,
授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》。
(保密的学位论文在解密后适用本授权书)
学位论文作者签名: 导师签字:
签字日期: 年月日签字日期: 年月日
三类平行机博弈排序问题的协调机制研究
摘要
排序理论是组合最优化理论的重要组成部分,如果在排序过程中有一个系统
管理员来安排相应任务,那么往往会得到比较理想的解。但是,随着互联网的发
展,在许多排序过程中由系统管理员来强加控制是不可行的,因为互联网的用户
具有独立性和自利性,他们“自私”地追求自身的利益最优,而不在乎是否造成
社会资源的浪费。若没有合理的资源使用机制,这种自利性往往会使结果与理论
最优值偏差巨大。因此设计合理的机制以影响、引导独立和“自私”的用户的选
择从而减少社会资源的浪费将具有重大的理论意义。
本文所研究的博弈排序模型描述如下:模型中有 m 台平行机
M1,M2,,Mm, n 个待加工的“自私”工件,形成工件集合 J {1,2,,n},工件
j 的加工时间为 p j ,每个工件对应一个局中人,每个工件 j 的目标是最小化自身
的完工时间,全局目标函数是某一关于工件完工时间的函数。协调机制是排序规
则的集合,它明确每台机器所实行的排序规则。工件可根据系统的机制自主选择
有利于优化自身目标函数的机器进行加工。一个工件 j 的策略集为
Xj M1,M2,,Mm, j1,2,,n 。每个工件的策略选定后形成策略局势
X X1 X 2 X n ,在其他工件不改变策略的情况下,没有一个工件可通过
单方面改变策略(即移动到另一台机器)从而减少自身完工时间的策略局势称为
纳什均衡。
本文研究三类平行机博弈排序问题的协调机制。
首先,我们探讨具有两台平行机,其全局目标函数为最小化最大完工时间的
博弈排序问题。 SPT LPT 机制是指一台机器按工件加工时间的不减顺序排序,
另一台机器按工件加工时间的不增顺序排序。我们设计了一种算法,并证明相应
博弈排序问题的纳什均衡集等于这一算法的解的集合,然后证明当工件数不小于
4时,对于相应博弈排序问题, SPT LPT 机制的无秩序代价为 4/ 3。
其次,我们探讨具有 m 台平行机,每个工件 j 有一权重 w j ,全局目标函数
为最小化最大加权完工时间的博弈排序问题。最大权重优先机制是指第i(i 1,2,
,m)台机器将选择了它的工件按权重从大到小排序,若权重相同,则序号小的
工件优先排,并于(i 1)时刻开始不间断地加工工件,直到所有选择了它的工件
完工。我们设计了一种算法,并证明相应博弈排序问题的纳什均衡集等于这一算
法得到的排序,然后证明对于相应博弈排序问题,最大权重优先机制的无秩序代
价至少为3/ 2 。
最后,我们探讨具有 m 台批容量无界的并行分批处理机,全局目标函数为最
小化最大完工时间的博弈排序问题。同批机制是指第i (i 1,2,,m)台机器将所
有选择了它的工件置于同一批,于(i 1)时刻开工。我们分析了相应博弈排序问
题的纳什均衡解的情况,然后证明对于相应排序博弈问题,同批机制的无秩序代