【摘要】：排序調(diào)度問題是組合優(yōu)化領(lǐng)域里最受關(guān)注的問題之一,應(yīng)用于工業(yè)生產(chǎn),物流調(diào)度,設(shè)施選址等生活領(lǐng)域中。在大多數(shù)關(guān)于排序調(diào)度問題的文獻(xiàn)里,要求所有的任務(wù)必須被安排在機(jī)器上加工,目標(biāo)是尋找合適的調(diào)度方案,使得最大完工時間最小。隨后,許多研究人員提出并研究了帶懲罰費(fèi)用的排序調(diào)度問題。帶懲罰費(fèi)用的排序調(diào)度問題與經(jīng)典的排序調(diào)度問題的區(qū)別在于,所有的任務(wù)不要求全部被安排在機(jī)器上,每項(xiàng)任務(wù)或者被接受并安排在機(jī)器上加工,或者被拒絕并產(chǎn)生相應(yīng)的懲罰費(fèi)用,目標(biāo)是尋找合適的調(diào)度方案,使得機(jī)器上的最大完工時間與所有被拒絕任務(wù)的懲罰費(fèi)用之和達(dá)到最小。在帶懲罰費(fèi)用的排序調(diào)度問題的研究基礎(chǔ)上,第三章提出在單機(jī)上的帶懲罰費(fèi)用的多維任務(wù)調(diào)度問題,使用2-劃分問題證明此問題是一個NP困難性問題,并且提出一個運(yùn)行時間為O(nd)的d-近似算法。當(dāng)維數(shù)d為固定常數(shù)時,設(shè)計(jì)了一個運(yùn)行時間為O(n~(d+1)(d/ε)~d)的全多項(xiàng)式時間近似方案。引入隨機(jī)舍入思想,提出一個近似比為1.585的隨機(jī)算法。當(dāng)多維任務(wù)的信息未知時,提出一個競爭比為d的在線算法。第四章提出帶懲罰費(fèi)用的多重任務(wù)調(diào)度問題,設(shè)計(jì)了一個運(yùn)行時間為O(n~2logn)的2-近似算法。當(dāng)機(jī)器數(shù)為固定常數(shù)時,給出一個運(yùn)行時間為O((4/ε)~m(ntmax)~(m+1))的全多項(xiàng)式時間近似方案,其中tmax為所有用戶提交任務(wù)最多數(shù)值,ε為任意正數(shù)。當(dāng)用戶信息未知時,提出一個競爭為2.618的在線算法,當(dāng)機(jī)器數(shù)為2時,給出一個競爭比為1.618的最優(yōu)在線算法。用Matlab編程實(shí)現(xiàn)兩個章節(jié)中算法得到輸出解,用Cplex計(jì)算相應(yīng)實(shí)例的最優(yōu)解,比較兩個函數(shù)值,實(shí)驗(yàn)結(jié)果用條形圖表示。最后一章總結(jié)了本文所有的研究成果,并提出未來值得研究方向。
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O223
【圖文】：

維數(shù)分別為2,8

機(jī)器數(shù)量分別為10,20,50單位：秒

【相似文獻(xiàn)】

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

1 段們們;;基于云計(jì)算的艦船大規(guī)模任務(wù)調(diào)度優(yōu)化[J];艦船科學(xué)技術(shù);2019年06期

2 李軍;王鈞;陳健;陳慧中;郭玉華;;基于多目標(biāo)遺傳算法的衛(wèi)星成像任務(wù)調(diào)度技術(shù)[J];系統(tǒng)工程與電子技術(shù);2007年07期

3 梁浩,吳洲;電子商務(wù)中供應(yīng)鏈任務(wù)調(diào)度問題的研究[J];中國機(jī)械工程;2003年16期

4 陳軍;謝立;孫鐘秀;;分布式任務(wù)調(diào)度研究的新趨向[J];計(jì)算機(jī)研究與發(fā)展;1990年04期

5 ;簡訊[J];成都電訊工程學(xué)院學(xué)報;1988年02期

6 劉心松,李健;分布式計(jì)算機(jī)系統(tǒng)中的任務(wù)調(diào)度[J];計(jì)算機(jī)應(yīng)用;1989年01期

7 呂英,李教材,房其敏;周期性混合任務(wù)調(diào)度[J];計(jì)算機(jī)工程與設(shè)計(jì);1989年01期

8 李晨蕾;;云計(jì)算環(huán)境下基于蟻群算法的任務(wù)調(diào)度研究[J];科技創(chuàng)新導(dǎo)報;2019年02期

9 丁志鋒;;云計(jì)算環(huán)境下用戶任務(wù)調(diào)度效率優(yōu)化仿真[J];計(jì)算機(jī)仿真;2017年04期

10 陳利安;肖明清;高峰;趙亮亮;;人工蜂群算法在并行測試任務(wù)調(diào)度中的應(yīng)用[J];計(jì)算機(jī)測量與控制;2012年06期

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

1 張磊;馬軍;;描述短時資源混雜占用型任務(wù)調(diào)度的數(shù)學(xué)模型與算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2005年

2 劉培培;李連;叢海鵬;謝勇;;基于多代理協(xié)商機(jī)制的任務(wù)調(diào)度系統(tǒng)研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會——通信與信息技術(shù)會議論文集（下）[C];2006年

3 張曉云;岳繼光;楊麟祥;;零星任務(wù)調(diào)度在多控制任務(wù)系統(tǒng)中的應(yīng)用[A];第16屆中國過程控制學(xué)術(shù)年會暨第4屆全國故障診斷與安全性學(xué)術(shù)會議論文集[C];2005年

4 常中祥;楊文沅;陳宇寧;周忠寶;姚鋒;;成像時長可變的視頻衛(wèi)星成像任務(wù)調(diào)度問題分析[A];第六屆高分辨率對地觀測學(xué)術(shù)年會論文集（上）[C];2019年

5 韓云;于炯;張偉;王命全;;基于負(fù)載均衡的任務(wù)調(diào)度改進(jìn)算法[A];2010年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會議論文集[C];2010年

6 王全民;王靚;許智宏;;網(wǎng)格環(huán)境中基于蟻群算法的批量任務(wù)調(diào)度的研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會——通信與信息技術(shù)會議論文集（上）[C];2006年

7 劉宇;劉玉榮;周冰;;基于WCF的環(huán)境減災(zāi)星座運(yùn)控任務(wù)調(diào)度系統(tǒng)[A];第二十五屆全國空間探測學(xué)術(shù)研討會摘要集[C];2012年

8 羅斯寧;王化龍;李弘宇;彭蔚;;基于改進(jìn)蟻群算法的云計(jì)算用戶任務(wù)調(diào)度算法[A];生態(tài)互聯(lián) 數(shù)字電力——2019電力行業(yè)信息化年會論文集[C];2019年

9 楊艦;黃道平;李小亞;;GDCS任務(wù)調(diào)度的SPN模型研究[A];第二十六屆中國控制會議論文集[C];2007年

10 唐琴琴;劉旭;張亞生;何辭;李誠成;謝人超;黃韜;;邊緣計(jì)算在星地協(xié)同網(wǎng)絡(luò)中的應(yīng)用探討[A];2019全國邊緣計(jì)算學(xué)術(shù)研討會論文集[C];2019年

相關(guān)重要報紙文章 前10條

1 記者 常娜;全市城市基層黨建重點(diǎn)工作任務(wù)調(diào)度會召開[N];鄂爾多斯日報;2019年

2 曲芳 戴江勇 龔界文 院宣 肖文正 楊麗;堅(jiān)決落實(shí)型號任務(wù)調(diào)度令[N];中國航天報;2008年

3 記者 秦娜;我省建立大氣污染防治目標(biāo)任務(wù)調(diào)度預(yù)警通報制度[N];甘肅日報;2015年

4 綜合編譯 劉琦;Windows HPC Server 2008新特性解讀[N];中國計(jì)算機(jī)報;2009年

5 記者 謝霄凌;我市部署清理整治奢華浪費(fèi)建設(shè)及專項(xiàng)整治任務(wù)[N];邢臺日報;2014年

6 何川 方興;運(yùn)籌帷幄決勝千里[N];計(jì)算機(jī)世界;2001年

7 記者 張雷峰;貫徹落實(shí)好省相關(guān)會議精神 確保活動取得更大成效[N];張家口日報;2014年

8 文海燕;統(tǒng)一認(rèn)識 強(qiáng)化責(zé)任 確保完成目標(biāo)任務(wù)[N];永州日報;2006年

9 記者 王彬;全力促增收 確保完成全年目標(biāo)[N];濟(jì)南日報;2012年

10 王波;Linux與服務(wù)器集群技術(shù)[N];中國計(jì)算機(jī)報;2002年

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

1 劉林東;分布式異構(gòu)環(huán)境中任務(wù)調(diào)度算法研究[D];華南理工大學(xué);2019年

2 徐海燕;帶有學(xué)習(xí)與惡化效應(yīng)的任務(wù)調(diào)度優(yōu)化方法[D];東南大學(xué);2017年

3 柳運(yùn)昌;多媒體云資源提供與任務(wù)調(diào)度技術(shù)研究[D];武漢理工大學(xué);2016年

4 何華;云計(jì)算的調(diào)度策略研究與性能分析[D];天津大學(xué);2017年

5 魯亮;大數(shù)據(jù)流式計(jì)算框架的任務(wù)調(diào)度優(yōu)化方法研究[D];新疆大學(xué);2018年

6 賓雪蓮;實(shí)時系統(tǒng)中的任務(wù)調(diào)度技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2004年

7 吳琦;嵌入式操作系統(tǒng)功耗管理技術(shù)研究[D];電子科技大學(xué);2006年

8 王濤;實(shí)時系統(tǒng)任務(wù)調(diào)度若干關(guān)鍵技術(shù)的研究[D];哈爾濱工程大學(xué);2006年

9 陸平;云計(jì)算應(yīng)用中的任務(wù)調(diào)度與資源分配的協(xié)同優(yōu)化[D];中國科學(xué)技術(shù)大學(xué);2017年

10 黃萬偉;基于服務(wù)屬性區(qū)分的可重構(gòu)任務(wù)調(diào)度研究[D];解放軍信息工程大學(xué);2009年

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

1 劉粟;基于Storm平臺的離線任務(wù)調(diào)度優(yōu)化方法研究[D];新疆大學(xué);2019年

2 陳天;深度強(qiáng)化學(xué)習(xí)在網(wǎng)絡(luò)資源管理問題中的應(yīng)用[D];電子科技大學(xué);2019年

3 王雪;基于分布式優(yōu)化的移動邊緣計(jì)算任務(wù)調(diào)度和設(shè)備協(xié)同算法研究[D];北京交通大學(xué);2019年

4 汪麗娟;Flink下的K-Means優(yōu)化并行與任務(wù)調(diào)度研究[D];新疆大學(xué);2019年

5 高超超;基于PSO改進(jìn)的云計(jì)算任務(wù)調(diào)度研究[D];湖南師范大學(xué);2019年

6 崔倩娜;帶懲罰費(fèi)用的多維（重）任務(wù)調(diào)度問題[D];云南大學(xué);2018年

7 楊宏霄;自動電池化成車間中基于多標(biāo)準(zhǔn)評價的揀選調(diào)度算法研究[D];電子科技大學(xué);2019年

8 彭永強(qiáng);分布式綜合任務(wù)調(diào)度平臺的設(shè)計(jì)與應(yīng)用[D];北京交通大學(xué);2019年

9 劉文隆;MapReduce任務(wù)調(diào)度和洗牌調(diào)度問題的研究[D];合肥工業(yè)大學(xué);2019年

10 袁天偉;容器云平臺下任務(wù)調(diào)度策略研究[D];桂林理工大學(xué);2019年

本文編號：2719695