本文關(guān)鍵詞：機(jī)器具有學(xué)習(xí)效應(yīng)的博弈排序問題

  更多相關(guān)文章： 學(xué)習(xí)效應(yīng) 博弈排序 納什均衡 POA 協(xié)調(diào)機(jī)制

【摘要】：本文研究的是機(jī)器具有學(xué)習(xí)效應(yīng)的博弈排序問題,具體來說,我們研究了在機(jī)器環(huán)境為m臺同速機(jī)和m臺恒速機(jī)的情況下,目標(biāo)函數(shù)分別為極小化工件的最大完工時間和極小化總完工時間的問題,并分別對每個問題求出了POA的界.博弈排序問題在近年來受到了國內(nèi)外學(xué)者、專家、及企業(yè)家的高度關(guān)注,新的研究成果也是不斷出現(xiàn),機(jī)器具有學(xué)習(xí)效應(yīng)這一類型的排序問題也已被好多學(xué)者研究過,而博弈排序這一問題從未與學(xué)習(xí)效應(yīng)問題結(jié)合在一起被研究,本文的創(chuàng)新點(diǎn)和著力點(diǎn)就在于把機(jī)器具有學(xué)習(xí)效應(yīng)與博弈排序這兩個問題結(jié)合起來,針對每個目標(biāo)函數(shù)求出其相應(yīng)的POA的界.機(jī)器具有學(xué)習(xí)效應(yīng)是指隨著工件在機(jī)器上的加工,機(jī)器獲得了學(xué)習(xí)效應(yīng),從而使后面加工的工件實(shí)際加工時間逐漸縮短.本文研究的是與位置有關(guān)的學(xué)習(xí)效應(yīng),也就是說,所有工件都在零時刻到達(dá),每個工件都有一個本身的基本加工時間,工件在機(jī)器上加工都會有一個相對應(yīng)的位置.如果工件排在機(jī)器上第一個被加工,由于此時機(jī)器還未獲得學(xué)習(xí)效應(yīng),所以它的加工時間不變,而排在后面的工件被加工時,由于機(jī)器獲得了學(xué)習(xí)效應(yīng),它們的加工時間都會逐漸縮短.博弈排序是排序中的重要部分,是一類新型排序問題,有著很重要的應(yīng)用價(jià)值,在理論上也有重要的意義.一個納什均衡是一個工件的排序狀態(tài),納什均衡同樣是博弈論的一個重要概念.作為一個納什均衡,如果其它所有工件的策略都不變,任何一個工件如果單方面的去改變自己的策略,那么它自己的成本不會變的比原來的更好.但在博弈排序中,工件只追求自身利益的最大化,而不在乎社會資源的浪費(fèi),這往往導(dǎo)致所得解與最優(yōu)解偏差過大.為衡量納什均衡解的好壞,學(xué)者們提出了無秩序代價(jià)(POA)的概念,即最壞情況下最壞的納什均衡解對應(yīng)的目標(biāo)函數(shù)值與最優(yōu)解的目標(biāo)函數(shù)值的比值.本篇論文分為四章,主要結(jié)構(gòu)安排如下：第一章主要介紹了本文所需的基礎(chǔ)知識；第二章主要研究了目標(biāo)函數(shù)為極小化最大完工時間Cmax的博弈排序問題,并求出了在機(jī)器環(huán)境分別為m臺同速機(jī)和m臺恒速機(jī)下對應(yīng)的POA的界m·T2/T(?)(其中T1和T2分別表示所有工件按SPT序和LPT序排在一臺機(jī)器上加工時機(jī)器的負(fù)載)和(其中s1和sm分別表示恒速機(jī)中加工工件最慢和最快的機(jī)器的加工速度)；第三章研究了目標(biāo)函數(shù)為極小化總完工時間的博弈排序問題,同樣求出了在機(jī)器環(huán)境分別為m臺同速機(jī)和m臺恒速機(jī)下對應(yīng)的POA的界(其中n為工件的個數(shù),P為所有工件本身加工時間之和)和第四章對本文進(jìn)行了總結(jié)及前景展望.
【關(guān)鍵詞】：學(xué)習(xí)效應(yīng) 博弈排序 納什均衡 POA 協(xié)調(diào)機(jī)制
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O223
【目錄】：

• 摘要3-5
• Abstract5-8
• 第1章 緒論8-13
• 1.1 排序問題8-9
• 1.2 博弈排序和納什均衡9-10
• 1.3 無秩序代價(jià)(POA)10-11
• 1.4 學(xué)習(xí)效應(yīng)11
• 1.5 協(xié)調(diào)機(jī)制11-13
• 第2章 極小化最大完工時間的博弈排序問題13-18
• 2.1 引言13
• 2.2 問題描述13-14
• 2.3 主要結(jié)果14-18
• 2.3.1 P_m|p_(jr)=p_j·r~a,a≤0|C_(max)14-16
• 2.3.2 Q_m|p_(jr)=p_j·r~a,a≤0|C_(max)16-18
• 第3章 極小化總完工時間的博弈排序問題18-25
• 3.1 引言18
• 3.2 問題描述18-19
• 3.3 主要結(jié)果19-25
• 3.3.1 P_m|p_(jr)=p_j·r~a,a≤0|(?)C_j19-21
• 3.3.2 Q_m|p_(jr)=p_j·r~a,a≤0|(?)C_j21-25
• 第4章 總結(jié)25-26
• 參考文獻(xiàn)26-28
• 在讀期間發(fā)表的學(xué)術(shù)論文及研究成果28-29
• 致謝29

【共引文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 袁芬;谷云東;塵非;;關(guān)于模糊工期平行機(jī)調(diào)度問題的若干結(jié)果[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期

2 張忠文;李四海;;一類離散型多資源排序算法[J];長春大學(xué)學(xué)報(bào);2009年12期

3 陳小林;任子亭;;誤工工件個數(shù)最少的多目標(biāo)排序問題(英文)[J];重慶工學(xué)院學(xué)報(bào)(自然科學(xué)版);2009年01期

4 李蒙;唐萬梅;唐國春;;機(jī)器不同時開工平行機(jī)排序問題的原始閾值算法[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

5 唐國春;;誤工排序問題的研究[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年02期

6 彭洪潔;蘇永英;唐國春;;部分工件必須不誤工的誤工排序問題[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年02期

7 彭洪潔;唐國春;;兩個多重目標(biāo)排序問題的多項(xiàng)式時間算法[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年02期

8 楊明明;張淑娟;韓翔凌;;具有學(xué)習(xí)效應(yīng)的間歇批生產(chǎn)的單機(jī)排序問題[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

9 王松麗;趙玉芳;崔苗苗;;帶有釋放時間的半連續(xù)型批處理機(jī)調(diào)度問題[J];重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年02期

10 陳榮軍;兩機(jī)器自由作業(yè)稠密時間表的優(yōu)勢集研究[J];常州工學(xué)院學(xué)報(bào);2005年01期

中國重要會議論文全文數(shù)據(jù)庫 前1條

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

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 馬英;考慮維護(hù)時間的機(jī)器調(diào)度問題研究[D];合肥工業(yè)大學(xué);2010年

2 鐘雪靈;帶強(qiáng)制工期非正則目標(biāo)函數(shù)的排序問題研究[D];暨南大學(xué);2010年

3 柳春鋒;工程項(xiàng)目中技能型員工調(diào)度問題研究[D];合肥工業(yè)大學(xué);2011年

4 王磊;面向訂單生產(chǎn)的供應(yīng)鏈排序問題研究[D];暨南大學(xué);2011年

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

6 白芳;民航發(fā)動機(jī)機(jī)群調(diào)度優(yōu)化與視情維修決策方法研究[D];南京航空航天大學(xué);2009年

7 鄭斐峰;占線訂單排序問題及其競爭策略研究[D];西安交通大學(xué);2006年

8 付旭云;機(jī)隊(duì)航空發(fā)動機(jī)維修規(guī)劃及其關(guān)鍵技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2011年

9 楊名;若干流水作業(yè)排序問題的算法研究[D];華東理工大學(xué);2011年

10 方陽;關(guān)于一些在線分批排序問題的研究[D];華東理工大學(xué);2011年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 吳麗華;服裝零售供應(yīng)配送中的若干問題研究[D];浙江理工大學(xué);2010年

2 任立莉;可拒絕平行批平行機(jī)與在線平行批兩臺一致機(jī)排序[D];鄭州大學(xué);2010年

3 孟令玉;基于網(wǎng)絡(luò)流的開放式車間調(diào)度問題研究[D];哈爾濱工程大學(xué);2010年

4 于慶蓮;基于靜態(tài)并行時間確定可增加瓶頸設(shè)備的研究[D];哈爾濱理工大學(xué);2010年

5 蘇勝龍;帶一個服務(wù)器的兩臺平行機(jī)半在線排序問題[D];華東理工大學(xué);2011年

6 陳杰;總延誤問題的一種貪婪啟發(fā)式算法分析[D];華東理工大學(xué);2011年

7 史媛媛;兩類雙目標(biāo)排序問題研究[D];武漢科技大學(xué);2010年

8 何少龍;具有安裝時間和變量加工時間的單機(jī)排序問題[D];沈陽師范大學(xué);2011年

9 林騁;多目標(biāo)網(wǎng)絡(luò)計(jì)劃圖的機(jī)動時間特性研究[D];華北電力大學(xué)（北京）;2011年

10 楊明明;具有學(xué)習(xí)效應(yīng)的間歇批生產(chǎn)的單機(jī)排序問題[D];曲阜師范大學(xué);2011年

，

本文編號：705359