本文關(guān)鍵詞：極小化總完工時間的帶服務(wù)等級平行機在線排序問題

  更多相關(guān)文章： 排序 服務(wù)等級 競爭比 下界 總完工時間 在線算法

【摘要】：排序(scheduling)問題是運籌學領(lǐng)域中一個非�；钴S的分支,它廣泛應(yīng)用于計算機科學、管理科學和工程技術(shù)等眾多領(lǐng)域。本文主要研究帶服務(wù)等級約束的同型機在線排序問題,目標是極小化總完工時間全文共分為四個章節(jié)。第一章簡要介紹排序的基本理論及帶服務(wù)等級約束排序問題的相關(guān)知識。第二章主要研究帶兩個服務(wù)等級約束的m臺平行機排序問題,所有工件的加工時間均為單位時間且服務(wù)等級為1或2,服務(wù)等級為1的工件只能在服務(wù)等級為1的機器上加工,服務(wù)等級為2的工件可以在m臺機器中任意一臺上加工。目標是極小化總完工時間。本章主要考慮以下兩種情形:對機器臺數(shù)為臺,其中第1臺機器服務(wù)等級為1,后臺機器服務(wù)等級為2的情形給出了競爭比為的在線算法,且該結(jié)果好于已有結(jié)果;對前臺機器服務(wù)等級為1,后臺機器服務(wù)等級為2的情形給出了問題的下界第三章主要研究帶服務(wù)等級約束的3臺平行機排序問題,目標是極小化總完工時間。本章主要考慮以下兩種情形:當一臺機器等級為1,兩臺機器等級為2時,給出了競爭比為17/14的最優(yōu)在線算法;當兩臺機器等級為1,一臺機器等級為2時,給出了競爭比為43/36的最優(yōu)在線算法。第四章總結(jié)全文內(nèi)容并提出可進一步研究的方向。
【學位授予單位】：浙江理工大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O223

【相似文獻】

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

1 李曙光,李國君,趙浩;無限批量調(diào)度中最小化加權(quán)完工時間和問題的一個線性時間近似方案(英文)[J];運籌學學報;2004年04期

2 王玉青;孫世杰;;單機最小化加權(quán)總完工時間的產(chǎn)品加工問題(英文)[J];Journal of Shanghai University(English Edition);2007年02期

3 李巖;田海龍;;總完工時間最短的恒速機排序[J];吉林化工學院學報;2009年03期

4 曹國梅;石忠和;;加工時間相同的分族分批排序加權(quán)總完工時間問題[J];安陽工學院學報;2009年04期

5 李曙光;李國君;趙洪鑾;;極小化完工時間和的有界批調(diào)度問題(英文)[J];應(yīng)用數(shù)學;2006年02期

6 李曙光;楊振光;亓興勤;;極小化最大完工時間的單機分批加工問題(英文)[J];運籌學學報;2006年01期

7 王珍;曹志剛;張玉忠;;極小化最大完工時間及拒絕費用的單機可拒絕分批排序[J];曲阜師范大學學報(自然科學版);2007年02期

8 金霽;顧燕紅;唐國春;;最大完工時間排序的兩人合作博弈[J];上海第二工業(yè)大學學報;2011年01期

9 郭曉;馮密羅;慕運動;;時間錯位限制下最小化總完工時間的繼列分批重新排序[J];鄭州大學學報(理學版);2012年01期

10 劉園園;許小艷;郝峗;慕運動;;時間期望錯位限制下完工時間和的隨機重新排序[J];河南科學;2012年07期

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

1 張樹霞;曹志剛;張玉忠;;極小化最大完工時間的離散可控排序(英文)[A];中國運籌學會第八屆學術(shù)交流會論文集[C];2006年

2 陳克兵;高成修;;可變加工時間的單機排序(英文)[A];中國運籌學會第七屆學術(shù)交流會論文集（上卷）[C];2004年

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

1 趙曉麗;多代理生產(chǎn)調(diào)度問題的理論研究[D];東北大學;2015年

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

3 李曙光;批調(diào)度與網(wǎng)絡(luò)問題的組合算法[D];山東大學;2007年

4 馬冉;最小化加權(quán)完工時間和的在線排序研究[D];鄭州大學;2015年

5 何程;多目標分批排序及其相關(guān)課題[D];鄭州大學;2009年

6 張國輝;柔性作業(yè)車間調(diào)度方法研究[D];華中科技大學;2009年

7 鄭俊麗;船舶分段制造車間的模塊空間調(diào)度模型及算法[D];上海交通大學;2011年

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

1 孔祥玉;作業(yè)時空受限的生產(chǎn)與運輸調(diào)度問題研究[D];沈陽大學;2015年

2 柴幸;最小化最大加權(quán)完工時間的平行分批在線排序問題[D];鄭州大學;2015年

3 邱言玲;工件加工中的排序博弈方法[D];西安電子科技大學;2014年

4 朱曉燦;基于Hadoop的試驗檢測計劃總完工時間極小化研究[D];西安電子科技大學;2015年

5 林琳;基于分枝定界的動態(tài)流水車間最大完工時間問題研究[D];東北大學;2015年

6 王玉艷;極小化總完工時間的帶服務(wù)等級平行機在線排序問題[D];浙江理工大學;2017年

7 衛(wèi)志剛;可自由離線批處理機最小化加權(quán)完工時間和排序[D];鄭州大學;2011年

8 尹婷;鋼鐵生產(chǎn)中連續(xù)批調(diào)度的策略研究[D];武漢科技大學;2011年

9 夏勁偉;GPU中針對任務(wù)完工時間最小化問題的研究[D];東北大學;2012年

10 曹志剛;分批排序、可拒絕排序及離散可控排序中的若干問題[D];曲阜師范大學;2006年

，

本文編號：1297221