论文部分内容阅读
排序博弈问题是近年来组合优化研究的热点之一.随着研究的不断深入，各种不同类型的排序博弈问题模型相继出现.本文主要研究几类不同的排序问题，重点研究不同博弈模型下Nash均衡的性质，给出反映Nash均衡性能优劣的指标Price ofAnarchy(PoA)和Price of Stability(PoS)的估计.本文共分五章. 第一章对组合优化问题、排序博弈问题等作了简单介绍，然后对主要工作成果进行了梳理. 第二章讨论了以工件所选择机器完工时间为工件费用，以极小化makespan和极大化机器最小完工时间为社会费用的排序博弈问题，给出了以工件加工时间相似系数r为参数的PoA值.当机器环境为两台及三台同型机时，我们得到了PoA的紧界.另外我们还给出了对于m≥4台同型机的PoA下界. 第三章我们考虑带机器激活费用，工件费用为机器完工时间和工件分摊机器完工时间比例之和，社会费用为极小化工件总费用的排序博弈问题.我们证明了当以工件数n为参数时，博弈的PoA和PoS均为n+1/3，且对每一个n均为紧的.若以工件最小加工时间的倒数ρ为参数，PoA至多为max{1，ρ+1/3}.当1≤ρ≤3时，PoS为1，当3＜ρ＜4时，PoS至少为4ρ/3ρ+2，当ρ≥4，PoS至少为ρ+4/2√ρ+3. 第四章我们主要研究社会费用为机器完工时间的Lp范数的排序博弈问题.对m台同型机，给出了以机器完工时间的平方和为社会费用的排序博弈问题的PoA的紧界.对带等级的两台和三台同型机，社会费用为极小化机器完工时间的p次平方和，分别给出了PoA的紧界.特别地，当社会费用为极小化机器完工时间平方和，PoA分别为3+√5/4和2+√2/2. 第五章我们研究加工时间可变的排序博弈问题，工件的实际加工时间为开工时间的线性函数.工件可自由选择同型机中任一台进行加工，机器规则为每台机器上的工件按恶化率非减顺序加工，工件费用定义为工件的完工时间，社会费用为机器总完工时间.我们证明了Nash均衡必定存在，并且得到了PoS和PoA的紧界皆为m+bn/m(1+bn)1/m.