本文關(guān)鍵詞： 同速機(jī)排序 惡化效應(yīng) 納什均衡 PoA　出處：《曲阜師范大學(xué)》2015年碩士論文　論文類型：學(xué)位論文

【摘要】：博弈排序問題是排序論與博弈論的一個交叉問題,就是從一個博弈的觀點研究排序問題.每個參與者在博弈中的個人目標(biāo)都是極小化自己的個人成本,我們把這個定義為此工件所在機(jī)器的負(fù)載.極大化社會價值是我們所考慮的社會目標(biāo).納什均衡時的總時間往往不是最小的,有時候與最優(yōu)值相差很大,所以,我們常用PoA這個參數(shù)來衡量納什均衡的目標(biāo)函數(shù)值與最優(yōu)值之間的差距.其中,PoA是指納什均衡排序中的任意一個排序的社會目標(biāo)值與最優(yōu)值的比率的最壞情況界.本文主要研究了工件帶有惡化效應(yīng)的博弈排序問題.工件具有惡化效應(yīng)即工件的實際加工時間會隨著工件的開工時間的增加而增加,即工件的實際加工時間除了工件本身的基本加工時間外還需要加上工件的開工時間與惡化率的乘積.本文研究了機(jī)器環(huán)境為m臺同速機(jī)的情況.第一章主要介紹了排序問題和博弈排序的相關(guān)概念,以及相關(guān)領(lǐng)域的進(jìn)展,并簡要概括了文章的主要工作和創(chuàng)新點.第二章我們主要考慮了工件的加工時間是開工時間的線性增加函數(shù)的同速機(jī)排序問題.目標(biāo)函數(shù)分別為極小化工件的總完工時間和極小化機(jī)器的總負(fù)載.當(dāng)工件具有不同的基本加工時間和相同的惡化率時,我們給出了目標(biāo)函數(shù)的PoA值.第三章我們研究了工件帶有惡化效應(yīng)的同速機(jī)排序問題.目標(biāo)函數(shù)為極小化總完工時間.當(dāng)每個工件都具有相同的基本加工時間和相同的惡化率時,我們得到了目標(biāo)函數(shù)的PoA值.
[Abstract]:The ordering problem of game is a cross problem between the theory of ranking and the theory of game, which is to study the problem of ordering from the point of view of a game. The individual goal of each participant in the game is to minimize their own personal cost. We define this as the load on the machine in which the workpiece is located. Maximizing social value is the social goal we consider. The total time of Nash equilibrium is often not the smallest, sometimes very different from the optimal value, so, We use PoA as a parameter to measure the difference between the objective function value and the optimal value of Nash equilibrium, where PoA is the worst-case bound of the ratio of the social target value to the optimal value of any sort in the Nash equilibrium ranking. In this paper, we mainly study the problem of game ordering of workpiece with aggravation effect, that is, the actual processing time of workpiece increases with the start time of workpiece. That is, the actual processing time of the workpiece needs to be added to the product of the starting time and the deterioration rate of the workpiece in addition to the basic processing time of the workpiece itself. In this paper, the related concepts of ordering problem and game ordering are discussed. And progress in related areas, In the second chapter, we mainly consider that the processing time of the workpiece is the linear increasing function of the starting time and the same speed machine sort problem. The objective function is the total of the minimal chemical parts, respectively. Completion time and minimization of the total load of the machine. When the workpiece has different basic processing times and the same deterioration rate, We give the PoA value of the objective function. In chapter 3, we study the scheduling problem of the same speed machine with deterioration effect. The objective function is to minimize the total completion time. When each workpiece has the same basic processing time and. At the same rate of deterioration, We get the PoA value of the objective function.
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O223

【相似文獻(xiàn)】

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

1 姜振多;孫世杰;吳志剛;;排序問題的穩(wěn)定性分析(英文)[J];Journal of Shanghai University(English Edition);2008年01期

2 譚素平;;排序問題的分類與特點[J];科技信息;2012年36期

3 越民義,韓繼業(yè);排序問題中的一些數(shù)學(xué)問題[J];數(shù)學(xué)的實踐與認(rèn)識;1976年03期

4 越民義,韓繼業(yè);同順序m×n排序問題的一個新方法[J];科學(xué)通報;1979年18期

5 吳家強(qiáng);用分段選優(yōu)法求解“排序問題”[J];武漢水利電力學(xué)院學(xué)報;1979年03期

6 戴志勇;;一類排序問題最優(yōu)工序定義的等價性[J];武漢鋼鐵學(xué)院學(xué)報;1979年02期

7 韓繼業(yè);排序問題的一個判別條件和一類特殊的m×n排序問題[J];應(yīng)用數(shù)學(xué)學(xué)報;1980年04期

8 吳在德;梁學(xué)信;;排序問題計算加工時間的一種方法及其一個應(yīng)用[J];華僑大學(xué)學(xué)報;1981年01期

9 葉懋冬;;關(guān)于過竿問題與多臺機(jī)床上零件加工的排序問題(Ⅰ)[J];浙江大學(xué)學(xué)報;1982年04期

10 徐本順;有提前和延誤損失的一類排序問題[J];華中工學(xué)院學(xué)報;1983年04期

相關(guān)會議論文 前10條

1 柏孟卓;唐國春;;加工時間可控的同時加工排序問題[A];2006年中國運籌學(xué)會數(shù)學(xué)規(guī)劃分會代表會議暨第六屆學(xué)術(shù)會議論文集[C];2006年

2 張蓮珠;;關(guān)于六角鏈的極值和排序問題的一些結(jié)果[A];中國運籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問題[A];2001年全國數(shù)學(xué)規(guī)劃及運籌研討會論文集[C];2001年

5 張玉忠;;分批排序問題研究[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

6 張玉忠;;分批排序問題研究[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

7 譚萬達(dá);;二元對比排序中的最少逆序原理[A];中國系統(tǒng)工程學(xué)會模糊數(shù)學(xué)與模糊系統(tǒng)委員會第五屆年會論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問題的歸并算法及其性能比研究[A];中國運籌學(xué)會第六屆學(xué)術(shù)交流會論文集（下卷）[C];2000年

9 樊保強(qiáng);;帶倉儲約束的準(zhǔn)時排序問題[A];中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

10 陳榮軍;唐國春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問題[A];中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

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

1 高強(qiáng);一些現(xiàn)代排序問題的算法設(shè)計與分析[D];華東理工大學(xué);2015年

2 仲維亞;供應(yīng)鏈管理中的若干排序問題研究[D];浙江大學(xué);2008年

3 尹曉;基因組重組排序問題的算法研究[D];山東大學(xué);2010年

4 余煒;若干網(wǎng)絡(luò)排序問題的算法和復(fù)雜性研究[D];華東理工大學(xué);2010年

5 張安;帶服務(wù)等級的在線排序問題及相關(guān)問題研究[D];浙江大學(xué);2009年

6 鄭睿;鋼鐵生產(chǎn)中的批處理機(jī)作業(yè)排序問題算法研究[D];復(fù)旦大學(xué);2009年

7 季敏;當(dāng)代工業(yè)中的若干排序問題研究[D];浙江大學(xué);2006年

8 李好好;若干排序問題研究[D];浙江大學(xué);2014年

9 丁國生;多代理競爭排序問題的研究[D];上海大學(xué);2009年

10 葉德仕;通訊網(wǎng)絡(luò)中排序問題的若干在線和高性能算法[D];浙江大學(xué);2005年

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

1 李韋萱;兩類帶有維修的排序問題[D];沈陽師范大學(xué);2015年

2 周雨波;與工件釋放時間和交貨時間有關(guān)的排序問題及近似算法[D];蘭州大學(xué);2015年

3 張龍;優(yōu)化交貨期窗口的單機(jī)供應(yīng)鏈排序問題[D];曲阜師范大學(xué);2015年

4 于萌萌;工件帶有惡化效應(yīng)的博弈排序問題[D];曲阜師范大學(xué);2015年

5 李雨潔;恒速機(jī)下的有限資源博弈排序最優(yōu)性研究[D];曲阜師范大學(xué);2015年

6 尚明明;帶有GDD假設(shè)的幾類重新排序問題研究[D];鄭州大學(xué);2015年

7 胡愛麗;幾個不同參數(shù)可控的排序問題的討論[D];蘇州大學(xué);2009年

8 孫葉平;誤工排序問題[D];重慶師范大學(xué);2008年

9 董柳毅;與誤工有關(guān)的多目標(biāo)排序問題[D];重慶師范大學(xué);2009年

10 王迅娣;成組加工排序和供應(yīng)鏈在線排序問題[D];曲阜師范大學(xué);2010年

，

本文編號：1495780