【摘要】：在經(jīng)典的離線排序問題中,在排序之前已經(jīng)知道工件的所有信息.本文主要研究的是按時在線排序.也就是指工件的各種信息在加工之前并不清楚,而是隨著時間推移逐個到達之后才被了解.在本文中,主要研究平行分批在線排序的若干問題.平行分批排序是排序研究領(lǐng)域中一類非常重要的問題.平行機排序模型中共有m臺機器.一臺分批機器可以一批同時加工至多b個工件.批的加工時長由該批中的最長工件決定.按照批的容量,可以分為兩類平行分批排序：有界的情形和無界的情形.在第二章中,對單機上最小化最大加權(quán)完工時間的分批在線排序問題,當批容量為1時,給出競爭比為2的最好可能的在線算法.在第三章中,考慮平行機上單位長度工件最小化最大加權(quán)完工時間的分批在線排序問題.對批容量有界情形,引用三參數(shù)表示法可以表示為：Pm|online,p-batch,b∞,Pj= 1|WCmax我們給出競爭比為攀#≈1.618的最好可能的在線算法.同時證明了該問題稠密算法競爭比的下界為2,給出了達到該競爭比的稠密算法.批容量無界時,對問題Pm|online,p-batch,prec,b=∞,Pj=1|WCmax和Pm|online,p-batch,prec,b=∞,Pj=1|∑wjcj,我們給出競爭比為(?)的最好可能的稠密算法,這個結(jié)果在工件間無序約束關(guān)系時同樣成立.在第四章中,考慮平行機上權(quán)重相同的單位工件具有不相容工件組和前瞻區(qū)間的無界分批在線排序問題.具有前瞻區(qū)間表示,在時刻t,在線算法可以看到在㈦t+序]時間內(nèi)到達的工件信息.不相容工件組表示來自不同工件組的工件不可以在同一批次加工.當所有工件的權(quán)重相同時,最大加權(quán)完工時間即轉(zhuǎn)化為最大完工時間.對問題Pm|online,p-batch,b= ∞,Pj=1,LKβ,f-families,β≥[f/m]Cmax,我們給出最優(yōu)的在線算法.對問題Pm|online, p-batch,b=∞,Pj=1,LKβk,f_families,f=km,βk∈[k-1,k)|Cmax,我們給出競爭比為1+α七的最好可能的在線算法,其中α七是方程kαk2+αk(βk+1)+βk-k=0的正根.對更一般的情形,我們證明了稠密算法的下界,并給出了最好可能的稠密算法.
【學位授予單位】：鄭州大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O223

【相似文獻】

相關(guān)期刊論文 前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期

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

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

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

相關(guān)博士學位論文 前6條

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

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

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

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

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

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

相關(guān)碩士學位論文 前9條

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

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

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

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

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

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

7 曹順娟;同類機半在線機器覆蓋問題研究[D];浙江大學;2006年

8 謝芳;機器帶激活費用的有限資源博弈排序[D];曲阜師范大學;2012年

9 苗許娜;關(guān)于重新排序的一些結(jié)果[D];鄭州大學;2006年

本文編號：2800367