现代排序理论中的三类重要问题：博弈排序，分批可拒绝排序和在线排序

发布时间：2017-12-28 22:14

本文关键词：现代排序理论中的三类重要问题：博弈排序，分批可拒绝排序和在线排序　出处：《曲阜师范大学》2016年博士论文　论文类型：学位论文

【摘要】：现代排序理论最重视的就是方法,而排序问题作为应用数学的一个重要分支,在其分析和解决过程中并没有标准的方法,事实上,几乎每一个排序问题的解决方法都是与众不同的.这就意味着我们在面对那些尚未解决的排序难题时必须挖掘出有效的新方法,而这也正是当前国内外排序界所最重视的一项工作.那么如何找到新方法呢,在解决排序难题的过程中我们就真的无章可循吗?虽然没有固定的方法,但是在分析排序问题寻找解题办法时是否存在着普遍适用的指导思想呢?我们认为这种指导思想是存在的,而分类法便是其中之一.本文将通过对现代排序中的三类重要问题的研究,阐明分类法的重要性.所谓分类法就是指一种将研究对象按照一定的性质划分为若干子问题,以显示其不同的规律性而方便进一步分别进行研究的思想.这其实是十分自然的思路,然而作为一种帮助人们认识复杂事物的简单直接的方法,分类法能够很好的化简排序难题,使问题的内在本质规律得以显现.所以当我们在面对一个排序问题一筹莫展苦于没有新方法时,如果能有意识的正确使用分类法,往往能取得意想不到的收获.事实上,分类法已经多次地被成功应用在许多排序问题的解决过程中了,下面我们将通过三个具体的例子来展示分类法在排序研究中的巨大作用.第一个模型(第二章)是关于等同平行机排序博弈(也称工作量均衡分配博弈)中纳什均衡的强稳定性问题的.其中,每个局中人都有一个独立的工件要在某台机器上加工以求极小化它自己的加工费用,即他的工件所在机器的总工作量.在本模型的一个纳什均衡中,如果有若干个局中人形成一个联盟而作一次协调性的策略改变,那么就有可能降低每个联盟成员各自的费用从而打破原来的稳定状态.首先,如果在一个策略组合中不存在这样的联盟行动,我们就称它为强纳什均衡.而在一个纳什均衡(非强纳什均衡)中,一个工件一次背离(改变策略)的改进率定义为在其背离前与背离后的费用之比值.那么如果在该纳什均衡中任何一个联盟都不能只通过该联盟的一次协调联合背离而使每个联盟成员都获得一个大于ρ的改进率,则这个纳什均衡就被称为ρ-近似强纳什均衡.显然ρ越小则原来的排序就越稳定.所以,对于该模型中纳什均衡关于强纳什均衡的近似性这一重要问题,我们在第二章中进行了一系列研究并且在分类法的帮助下最终证明了本模型中的任何一个纳什均衡都是一个(5/4)-近似强纳什均衡,并且这个近似界是紧的.第二个模型(第三章)是关于串行分批排序中在一致平行机上极小化总完工时间问题的.其中,加工速度成比例的串行批机器一共有m台,在这里的m是一个固定的常数而不是输入数.我们研究该模型的两个子问题:在第一个子问题中,所有的工件都不得不被安排在这m台串行分批机器上进行加工,我们的目标是极小化工件们的总完工时间;在第二个子问题中,每个工件都可以被接受或者被拒绝,所有被接受的工件都必须被安排在那m台机器上进行加工,而每一个被拒绝的工件都要求支付一个拒绝费用,这样我们的目标就是极小化被接受工件的总完工时间和被拒绝工件的总拒绝费用之和.在第三章中,我们利用分类法设计了一个多项式时间算法来解决上述两个子问题,该算法对这两个问题的时间复杂性分别是:O(m~2n~(m+2))和O(m~2n~(m+5)).第三个模型(第四章)是关于在线排序中在平行机上极小化时间表长问题的.其中,所有的工件都是以在线over time的方式到达的.我们考虑该问题的两个基本模型:在第一个模型里,一共有两台速度成比例的一致平行机,其中一台速度为1,另一台速度为s(s≥1);而在第二个模型里,一共有m台速度一样的等同机.在第四章中,我们用分类法分别研究了这两个模型,证明了:一种在线LPT算法对于第一个模型的竞争比为(1+(?))/2≈1.6180,并且这个界对于本算法来说是紧的,而且如果在本模型中的参数s≥1.8020的话,在线LPT算法就是一个最好可能的算法;而对于本问题的第二个模型,任何一个确定型的在线算法的竞争比都要大于等于一个下界(15-(?))/8≈1.3596,这一结果改进了在早先文献中已经得到的下届1.3473.
[Abstract]:Is the most important method of modern scheduling theory, and the scheduling problem is an important branch of Applied Mathematics, method, in the analysis and solving process and there is no standard solution in fact, almost every sort of problem is out of the ordinary. This means that we must find new effective method in the face of those unsolved sorting problem, which is also the current domestic and international ranking task the most important. So how to find a new method in solving the problem of sorting, we really nowhere? Although there is no fixed method, but the search for problem solving method in analysis when the sorting problem whether there is the guiding ideology of the universal? We believe that this guiding ideology exists, and classification is one of them. This paper will research on three important problems in the modern order, Clarify the importance of classification. It means a research object can be divided according to the nature of the so-called problem into several sub classification method, to show the different regularity and facilitate the further research were thought. This is actually a very natural idea, simple and direct ways but as a help people understand complex things the classification method can simplify the scheduling problem well, inherent law of the problem will be appeared. So when we are in the face of a scheduling problem with no new method do suffer from, if there is awareness of the proper use of classification, can often get unexpected harvest. In fact, the classification method has been repeatedly has been successfully applied in solving many problems in the process of sorting, here we will use three specific examples to demonstrate the great role of classification in the sort of research. The first model ( The second chapter is about equal) parallel machine scheduling game (also known as the workload balance allocation game) strong stability of Nash equilibrium in which each player has an independent of the workpiece to be machined in order to minimize processing costs of its own in a machine, the total workload that he work machine. In a Nash equilibrium of the model, if there are a number of players to form a coalition to change a coordination strategy, it is possible to reduce the cost of each of each member of the alliance to break the original steady state. First, if the coalition does not exist in a combination of strategies and we'll call it the strong Nash equilibrium. In a Nash equilibrium (non Nash equilibrium), a departure from a workpiece (change strategy) defined as the improvement rate in the use of the deviation and deviation of the ratio of the fee before. What if the Nash equilibrium in any alliance not only by a departure from the alliance and joint coordination so that each alliance member can obtain an improved rate greater than P, then the Nash equilibrium is called P - approximate Nash equilibrium. Obviously, the smaller the P original ranking is more stable so, the model for Nash equilibrium approximation on the important issue of the Jonas equilibrium in the second chapter, we conducted a series of studies and classification with the help of the final proved that any Nash equilibrium in this model is a (5/4) - approximate Jonas equilibrium, and the approximation the bound is tight. Second models (the third chapter) is about the serial batch scheduling on uniform parallel machine total completion time minimization problem. The processing speed is proportional to the number of serial machine a total of M, here is a m Constant rather than the input number. We study the problem of two sub models: in the first sub problems, all parts have to be arranged in the M serial batch processing machine, our goal is minimizing the total completion time are; in the second sub problems, each job can be accepted or rejected, all accepted the workpiece must be arranged in the M processing machine, and each rejected workpieces are required to pay a fee to this, our goal is to minimize the acceptance of the work piece total completion time and the total cost of the work was rejected refused and in the third chapter, we use the classification method to design a polynomial time algorithm to solve the above two sub problems, the algorithm of the two problems are: the time complexity of O (m~2n~ (m+2)) and O (m~2n~ (m+5)). Three models (the fourth chapter) is about the online scheduling on parallel machines to minimize the makespan problem. Among them, all parts are in online over time way to arrive. We consider two basic models of the problem: in the first model, a total of two speed proportional uniform parallel one machine, the rate of 1, another speed of S (s = 1); and in the second model, a total of m speed equivalent machine. In the fourth chapter, we use the classification method of the two models, respectively research proved: an online LPT algorithm for the first model of the competitive ratio (1+ (?) /2 = 1.6180), and this bound for this algorithm is tight, and if in the model parameters of S = 1.8020, the online LPT algorithm is one of the best possible algorithm; and for the second model of the problem, any a certain type in Line algorithm competition than are greater than or equal to a lower bound (15- (?) /8 = 1.3596), this result was improved in previous literature has been the next 1.3473.
【学位授予单位】：曲阜师范大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O223

【相似文献】