论文部分内容阅读
在传统的排序问题中，工件的加工是由一个中心决策者来控制和调配的，工件本身并不能参与决策的过程.随着博弈思想的加入，工件具有自主选择权的排序博弈问题开始得到更多研究者的关注.本文研究几个不同的排序博弈模型，重点关注在不同的排序博弈中纳什均衡的性质.通过对Price of Anarchy(PoA)和Price of Stability(PoS)的估计，来衡量纳什均衡的优劣程度，以量化评估工件自由选择对整个系统效益的影响.本文共分为五章. 第一章是绪论，对组合优化问题，算法及计算复杂性，经典排序问题和排序博弈的基本概念进行了介绍，并且对本文的整体结构和主要成果进行了简要叙述. 第二章研究同型机环境下工件加工时间可变的排序博弈问题.工件的实际加工时间与工件的开工时间成正比，比例系数称为工件的恶化率.本章给出了三种不同的协调机制，每种协调机制中都设定所有机器遵从同一种规则.三种协调机制应用的规则分别为恶化率非减(SDR)规则、恶化率非增(LDR)规则、以及工件费用为其所在机器负载的规则(MS规则).证明了三种协调机制下纳什均衡的存在性，分别给出了目标为极小化工件最大完工时间和极小化机器总负载的排序博弈在这三种规则下PoA和PoS的估计，且给出的界大部分为参数紧的. 第三章研究了工件带等级的平行机排序博弈问题的混合协调机制.混合协调机制允许每台机器选择不同的规则.提出了四种基于工件等级和工件加工时间的常用规则，证明了由这四种规则形成的混合协调机制下纳什均衡的存在性，并将其应用于同型机这一特殊情形.对两种分属低等级优先(LG)和高等级优先(HG)规则的混合协调机制，研究了目标为极小化最大完工时间的排序博弈的PoA和PoS值.在遵从同一种规则的机器指标连续的情形下，得到了PoA和PoS的若干紧界. 第四章研究低等级优先的混合协调机制，即所有机器都遵从LG规则，在等级相同的工件中，机器遵从加工时间非增(LPT)规则或加工时间非减(SPT)规则，分别研究了目标为极小化工件最大完工时间和极大化机器最小负载的排序博弈问题，给出了PoA和PoS的紧界.研究结果表明，在这两类排序博弈模型中，纳什均衡的性质都与最后一台机器遵从的规则直接相关. 第五章对本文的主要结果进行了总结，并给出了若干待研究的问题.