發(fā)布時(shí)間：2020-09-18 15:13

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

【參考文獻(xiàn)】

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

1 谷存昌;張玉忠;;兩臺(tái)平行機(jī)完工時(shí)間平方和最小的排序問題[J];運(yùn)籌學(xué)學(xué)報(bào);2015年01期

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

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

本文編號(hào)：2821816