论文部分内容阅读
现代排序理论最重视的就是方法,而排序问题作为应用数学的一个重要分支,在其分析和解决过程中并没有标准的方法,事实上,几乎每一个排序问题的解决方法都是与众不同的.这就意味着我们在面对那些尚未解决的排序难题时必须挖掘出有效的新方法,而这也正是当前国内外排序界所最重视的一项工作.那么如何找到新方法呢,在解决排序难题的过程中我们就真的无章可循吗?虽然没有固定的方法,但是在分析排序问题寻找解题办法时是否存在着普遍适用的指导思想呢?我们认为这种指导思想是存在的,而分类法便是其中之一.本文将通过对现代排序中的三类重要问题的研究,阐明分类法的重要性.所谓分类法就是指一种将研究对象按照一定的性质划分为若干子问题,以显示其不同的规律性而方便进一步分别进行研究的思想.这其实是十分自然的思路,然而作为一种帮助人们认识复杂事物的简单直接的方法,分类法能够很好的化简排序难题,使问题的内在本质规律得以显现.所以当我们在面对一个排序问题一筹莫展苦于没有新方法时,如果能有意识的正确使用分类法,往往能取得意想不到的收获.事实上,分类法已经多次地被成功应用在许多排序问题的解决过程中了,下面我们将通过三个具体的例子来展示分类法在排序研究中的巨大作用.第一个模型(第二章)是关于等同平行机排序博弈(也称工作量均衡分配博弈)中纳什均衡的强稳定性问题的.其中,每个局中人都有一个独立的工件要在某台机器上加工以求极小化它自己的加工费用,即他的工件所在机器的总工作量.在本模型的一个纳什均衡中,如果有若干个局中人形成一个联盟而作一次协调性的策略改变,那么就有可能降低每个联盟成员各自的费用从而打破原来的稳定状态.首先,如果在一个策略组合中不存在这样的联盟行动,我们就称它为强纳什均衡.而在一个纳什均衡(非强纳什均衡)中,一个工件一次背离(改变策略)的改进率定义为在其背离前与背离后的费用之比值.那么如果在该纳什均衡中任何一个联盟都不能只通过该联盟的一次协调联合背离而使每个联盟成员都获得一个大于ρ的改进率,则这个纳什均衡就被称为ρ-近似强纳什均衡.显然ρ越小则原来的排序就越稳定.所以,对于该模型中纳什均衡关于强纳什均衡的近似性这一重要问题,我们在第二章中进行了一系列研究并且在分类法的帮助下最终证明了本模型中的任何一个纳什均衡都是一个(5/4)-近似强纳什均衡,并且这个近似界是紧的.第二个模型(第三章)是关于串行分批排序中在一致平行机上极小化总完工时间问题的.其中,加工速度成比例的串行批机器一共有m台,在这里的m是一个固定的常数而不是输入数.我们研究该模型的两个子问题:在第一个子问题中,所有的工件都不得不被安排在这m台串行分批机器上进行加工,我们的目标是极小化工件们的总完工时间;在第二个子问题中,每个工件都可以被接受或者被拒绝,所有被接受的工件都必须被安排在那m台机器上进行加工,而每一个被拒绝的工件都要求支付一个拒绝费用,这样我们的目标就是极小化被接受工件的总完工时间和被拒绝工件的总拒绝费用之和.在第三章中,我们利用分类法设计了一个多项式时间算法来解决上述两个子问题,该算法对这两个问题的时间复杂性分别是:O(m2nm+2)和O(m2nm+5).第三个模型(第四章)是关于在线排序中在平行机上极小化时间表长问题的.其中,所有的工件都是以在线over time的方式到达的.我们考虑该问题的两个基本模型:在第一个模型里,一共有两台速度成比例的一致平行机,其中一台速度为1,另一台速度为s(s≥1);而在第二个模型里,一共有m台速度一样的等同机.在第四章中,我们用分类法分别研究了这两个模型,证明了:一种在线LPT算法对于第一个模型的竞争比为(1+(?))/2≈1.6180,并且这个界对于本算法来说是紧的,而且如果在本模型中的参数s≥1.8020的话,在线LPT算法就是一个最好可能的算法;而对于本问题的第二个模型,任何一个确定型的在线算法的竞争比都要大于等于一个下界(15-(?))/8≈1.3596,这一结果改进了在早先文献中已经得到的下届1.3473.