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

  更多相關(guān)文章： 排序 平行機(jī)博弈 近似強(qiáng)納什均衡 串行批 可拒絕 多項(xiàng)式時(shí)間算法 在線算法 下界

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

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

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

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

9 陳仕平,張國(guó)川;兩臺(tái)平行機(jī)的實(shí)時(shí)到達(dá)在線排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2000年01期

10 周偉剛;高成修;黃凱;;加工時(shí)間可控和簡(jiǎn)單線性增長(zhǎng)的平行機(jī)排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2010年04期

相關(guān)會(huì)議論文 前1條

1 聞?wù)裥l(wèi);;一類平行機(jī)上的任務(wù)指派問(wèn)題及其動(dòng)態(tài)規(guī)劃算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

相關(guān)博士學(xué)位論文 前7條

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

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

3 何杰;預(yù)防性維護(hù)下的混合型平行機(jī)調(diào)度問(wèn)題研究[D];湖南大學(xué);2016年

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

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

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

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

相關(guān)碩士學(xué)位論文 前10條

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

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

3 洪文益;與平行機(jī)排序相關(guān)的幾個(gè)組合問(wèn)題研究[D];清華大學(xué);2013年

4 李松松;在平行機(jī)博弈排序中的近似強(qiáng)納什均衡問(wèn)題[D];曲阜師范大學(xué);2013年

5 王君麗;有加工權(quán)限平行機(jī)在線問(wèn)題研究[D];浙江大學(xué);2012年

6 財(cái)玉華;具有非交叉維修時(shí)間的平行機(jī)在線排序[D];鄭州大學(xué);2007年

7 莫禎貞;改進(jìn)粒子群算法在模糊環(huán)境下平行機(jī)批調(diào)度問(wèn)題中的應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

8 林琳;具有同時(shí)性約束的平行機(jī)排序問(wèn)題[D];鄭州大學(xué);2006年

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

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

本文編號(hào)：1347632