本文關鍵詞：機器具有學習效應的博弈排序問題

  更多相關文章： 學習效應 博弈排序 納什均衡 POA 協(xié)調機制

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

• 摘要3-5
• Abstract5-8
• 第1章 緒論8-13
• 1.1 排序問題8-9
• 1.2 博弈排序和納什均衡9-10
• 1.3 無秩序代價(POA)10-11
• 1.4 學習效應11
• 1.5 協(xié)調機制11-13
• 第2章 極小化最大完工時間的博弈排序問題13-18
• 2.1 引言13
• 2.2 問題描述13-14
• 2.3 主要結果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 主要結果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章 總結25-26
• 參考文獻26-28
• 在讀期間發(fā)表的學術論文及研究成果28-29
• 致謝29

【共引文獻】

中國期刊全文數據庫 前10條

1 袁芬;谷云東;塵非;;關于模糊工期平行機調度問題的若干結果[J];北京師范大學學報(自然科學版);2006年03期

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

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

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

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

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

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

8 楊明明;張淑娟;韓翔凌;;具有學習效應的間歇批生產的單機排序問題[J];重慶師范大學學報(自然科學版);2011年03期

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

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

中國重要會議論文全文數據庫 前1條

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

中國博士學位論文全文數據庫 前10條

1 馬英;考慮維護時間的機器調度問題研究[D];合肥工業(yè)大學;2010年

2 鐘雪靈;帶強制工期非正則目標函數的排序問題研究[D];暨南大學;2010年

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

4 王磊;面向訂單生產的供應鏈排序問題研究[D];暨南大學;2011年

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

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

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

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

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

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

中國碩士學位論文全文數據庫 前10條

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

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

3 孟令玉;基于網絡流的開放式車間調度問題研究[D];哈爾濱工程大學;2010年

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

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

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

7 史媛媛;兩類雙目標排序問題研究[D];武漢科技大學;2010年

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

9 林騁;多目標網絡計劃圖的機動時間特性研究[D];華北電力大學（北京）;2011年

10 楊明明;具有學習效應的間歇批生產的單機排序問題[D];曲阜師范大學;2011年

，

本文編號：705359