本文關鍵詞：現(xiàn)代排序理論中的三類重要問題：博弈排序，分批可拒絕排序和在線排序　出處：《曲阜師范大學》2016年博士論文　論文類型：學位論文

  更多相關文章： 排序 平行機博弈 近似強納什均衡 串行批 可拒絕 多項式時間算法 在線算法 下界

【摘要】：現(xiàn)代排序理論最重視的就是方法,而排序問題作為應用數(shù)學的一個重要分支,在其分析和解決過程中并沒有標準的方法,事實上,幾乎每一個排序問題的解決方法都是與眾不同的.這就意味著我們在面對那些尚未解決的排序難題時必須挖掘出有效的新方法,而這也正是當前國內(nèi)外排序界所最重視的一項工作.那么如何找到新方法呢,在解決排序難題的過程中我們就真的無章可循嗎?雖然沒有固定的方法,但是在分析排序問題尋找解題辦法時是否存在著普遍適用的指導思想呢?我們認為這種指導思想是存在的,而分類法便是其中之一.本文將通過對現(xiàn)代排序中的三類重要問題的研究,闡明分類法的重要性.所謂分類法就是指一種將研究對象按照一定的性質(zhì)劃分為若干子問題,以顯示其不同的規(guī)律性而方便進一步分別進行研究的思想.這其實是十分自然的思路,然而作為一種幫助人們認識復雜事物的簡單直接的方法,分類法能夠很好的化簡排序難題,使問題的內(nèi)在本質(zhì)規(guī)律得以顯現(xiàn).所以當我們在面對一個排序問題一籌莫展苦于沒有新方法時,如果能有意識的正確使用分類法,往往能取得意想不到的收獲.事實上,分類法已經(jīng)多次地被成功應用在許多排序問題的解決過程中了,下面我們將通過三個具體的例子來展示分類法在排序研究中的巨大作用.第一個模型(第二章)是關于等同平行機排序博弈(也稱工作量均衡分配博弈)中納什均衡的強穩(wěn)定性問題的.其中,每個局中人都有一個獨立的工件要在某臺機器上加工以求極小化它自己的加工費用,即他的工件所在機器的總工作量.在本模型的一個納什均衡中,如果有若干個局中人形成一個聯(lián)盟而作一次協(xié)調(diào)性的策略改變,那么就有可能降低每個聯(lián)盟成員各自的費用從而打破原來的穩(wěn)定狀態(tài).首先,如果在一個策略組合中不存在這樣的聯(lián)盟行動,我們就稱它為強納什均衡.而在一個納什均衡(非強納什均衡)中,一個工件一次背離(改變策略)的改進率定義為在其背離前與背離后的費用之比值.那么如果在該納什均衡中任何一個聯(lián)盟都不能只通過該聯(lián)盟的一次協(xié)調(diào)聯(lián)合背離而使每個聯(lián)盟成員都獲得一個大于ρ的改進率,則這個納什均衡就被稱為ρ-近似強納什均衡.顯然ρ越小則原來的排序就越穩(wěn)定.所以,對于該模型中納什均衡關于強納什均衡的近似性這一重要問題,我們在第二章中進行了一系列研究并且在分類法的幫助下最終證明了本模型中的任何一個納什均衡都是一個(5/4)-近似強納什均衡,并且這個近似界是緊的.第二個模型(第三章)是關于串行分批排序中在一致平行機上極小化總完工時間問題的.其中,加工速度成比例的串行批機器一共有m臺,在這里的m是一個固定的常數(shù)而不是輸入數(shù).我們研究該模型的兩個子問題:在第一個子問題中,所有的工件都不得不被安排在這m臺串行分批機器上進行加工,我們的目標是極小化工件們的總完工時間;在第二個子問題中,每個工件都可以被接受或者被拒絕,所有被接受的工件都必須被安排在那m臺機器上進行加工,而每一個被拒絕的工件都要求支付一個拒絕費用,這樣我們的目標就是極小化被接受工件的總完工時間和被拒絕工件的總拒絕費用之和.在第三章中,我們利用分類法設計了一個多項式時間算法來解決上述兩個子問題,該算法對這兩個問題的時間復雜性分別是:O(m~2n~(m+2))和O(m~2n~(m+5)).第三個模型(第四章)是關于在線排序中在平行機上極小化時間表長問題的.其中,所有的工件都是以在線over time的方式到達的.我們考慮該問題的兩個基本模型:在第一個模型里,一共有兩臺速度成比例的一致平行機,其中一臺速度為1,另一臺速度為s(s≥1);而在第二個模型里,一共有m臺速度一樣的等同機.在第四章中,我們用分類法分別研究了這兩個模型,證明了:一種在線LPT算法對于第一個模型的競爭比為(1+(?))/2≈1.6180,并且這個界對于本算法來說是緊的,而且如果在本模型中的參數(shù)s≥1.8020的話,在線LPT算法就是一個最好可能的算法;而對于本問題的第二個模型,任何一個確定型的在線算法的競爭比都要大于等于一個下界(15-(?))/8≈1.3596,這一結(jié)果改進了在早先文獻中已經(jīng)得到的下屆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

【相似文獻】

相關期刊論文 前10條

1 張智聰;鄭力;翁小華;;基于增強學習的平行機調(diào)度研究[J];計算機集成制造系統(tǒng);2007年01期

2 陳榮軍;唐國春;;平行機的供應鏈排序[J];系統(tǒng)科學與數(shù)學;2010年02期

3 陳榮軍;張峰;唐國春;;平行機及自由作業(yè)的排序與轉(zhuǎn)包[J];系統(tǒng)工程學報;2011年05期

4 陳榮軍;唐國春;;平行機的排序與轉(zhuǎn)包(英文)[J];數(shù)學季刊;2012年04期

5 蔣大奎;李波;;平行機作業(yè)環(huán)境下的訂單分配與排序[J];管理學報;2013年06期

6 王成堯,汪定偉;有模機配合約束的平行機臺調(diào)度方法[J];東北大學學報;1999年04期

7 曾歡歡,胡建華;可換速平行機工件帶起止值的搶先進度表[J];數(shù)學理論與應用;1999年02期

8 蔣大奎;李波;曹立思;;考慮轉(zhuǎn)包的平行機供應鏈排序[J];控制與決策;2014年05期

9 陳仕平,張國川;兩臺平行機的實時到達在線排序[J];應用數(shù)學學報;2000年01期

10 周偉剛;高成修;黃凱;;加工時間可控和簡單線性增長的平行機排序[J];應用數(shù)學學報;2010年04期

相關會議論文 前1條

1 聞振衛(wèi);;一類平行機上的任務指派問題及其動態(tài)規(guī)劃算法[A];中國運籌學會第九屆學術交流會論文集[C];2008年

相關博士學位論文 前7條

1 劉珊珊;一些單機和平行機排序情形的研究[D];華東理工大學;2015年

2 陳友軍;有運送協(xié)調(diào)性的最小化最大運送完成時間平行機排序[D];鄭州大學;2016年

3 何杰;預防性維護下的混合型平行機調(diào)度問題研究[D];湖南大學;2016年

4 李松松;現(xiàn)代排序理論中的三類重要問題：博弈排序，，分批可拒絕排序和在線排序[D];曲阜師范大學;2016年

5 程貞敏;平行機調(diào)度問題研究的若干結(jié)果[D];北京師范大學;2008年

6 蔡圣義;同類平行機在線半在線排序參數(shù)界的若干研究[D];浙江大學;2010年

7 何龍敏;一類平行機和批處理機組成的二階段柔性流水作業(yè)問題[D];上海大學;2006年

相關碩士學位論文 前10條

1 趙云;帶等級平行機調(diào)度和MapReduce調(diào)度問題的算法研究[D];浙江理工大學;2016年

2 張家寶;考慮維護和可中斷工件的混合型平行機調(diào)度問題研究[D];東華理工大學;2016年

3 洪文益;與平行機排序相關的幾個組合問題研究[D];清華大學;2013年

4 李松松;在平行機博弈排序中的近似強納什均衡問題[D];曲阜師范大學;2013年

5 王君麗;有加工權限平行機在線問題研究[D];浙江大學;2012年

6 財玉華;具有非交叉維修時間的平行機在線排序[D];鄭州大學;2007年

7 莫禎貞;改進粒子群算法在模糊環(huán)境下平行機批調(diào)度問題中的應用研究[D];中國科學技術大學;2010年

8 林琳;具有同時性約束的平行機排序問題[D];鄭州大學;2006年

9 徐武來;具有完工期和工裝數(shù)量約束的平行機調(diào)度方法[D];廣東工業(yè)大學;2012年

10 何曉瓊;一致平行機上在線排序[D];湖南師范大學;2009年

本文編號：1347632