排序(scheduling)問題是組合優(yōu)化問題的一個重要分支,在傳統(tǒng)的排序問題中,都是由一個中央集權(quán)代理人安排工件排序,而現(xiàn)在排序問題大多研究一個代理人管理一個工件的情況,由代理人安排工件到機器上加工.設(shè)計算法,如何安排工件加工,以減少社會資源的浪費具有重大的研究意義.本文主要研究有限資源的博弈排序問題,用POA(Price of Anarchy)來衡量一個納什均衡(Nash Equlibrium)排序的目標函數(shù)值與一個最優(yōu)排序的目標函數(shù)值的差異.本文結(jié)構(gòu)如下:第一章緒論主要介紹了問題的背景,相關(guān)概念及相關(guān)的研究現(xiàn)狀,并簡要介紹了本文研究的主要成果和創(chuàng)新點.第二章研究了 m臺同類機情況下的的資源分配問題,不妨假設(shè)機器的速度分別為s1 =s,s2 = s3= =s…=sm=1,目標函數(shù)為全部工件的完工時間和.證得當有一臺速度比1大,其余速度均為1時,POA的上界為4m-3+1/2,下界為3/4+1/4 m+1/m-1;當有一臺機器速度小于1,其余速度均為1時,PCA的上界為4m-3+1/2,下界為3m-3+(m2-3m+2)2m-1/(m2+4m+2)2m-1+2m2-m,這里的m都是指機器臺數(shù).第三章研究了m臺同型分批處理機下的資源分配問題,假設(shè)每臺機器的批容量為b,一批工件中的加工時間是該批中最長工件的加工時間.目標函數(shù)為全部工件的完工時間和.設(shè)計了一個LPT-貪婪算法,證得POA的上界為bn/m告.
【學位單位】：曲阜師范大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：O223

【參考文獻】

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

1 谷存昌;張玉忠;;兩臺平行機完工時間平方和最小的排序問題[J];運籌學學報;2015年01期

2 趙婷;農(nóng)慶琴;方奇志;;兩臺平行機排序博弈問題的協(xié)調(diào)機制[J];中國海洋大學學報(自然科學版);2013年07期

3 張玉忠,王忠志,王長鈺;分批排序的“轉(zhuǎn)換引理”及其應(yīng)用[J];系統(tǒng)科學與數(shù)學;2002年03期

本文編號：2821816