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

【相似文獻(xiàn)】

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

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

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

3 李巖;田海龍;;總完工時(shí)間最短的恒速機(jī)排序[J];吉林化工學(xué)院學(xué)報(bào);2009年03期

4 曹國(guó)梅;石忠和;;加工時(shí)間相同的分族分批排序加權(quán)總完工時(shí)間問題[J];安陽(yáng)工學(xué)院學(xué)報(bào);2009年04期

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

6 李曙光;楊振光;亓興勤;;極小化最大完工時(shí)間的單機(jī)分批加工問題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2006年01期

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

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

9 郭曉;馮密羅;慕運(yùn)動(dòng);;時(shí)間錯(cuò)位限制下最小化總完工時(shí)間的繼列分批重新排序[J];鄭州大學(xué)學(xué)報(bào)(理學(xué)版);2012年01期

10 劉園園;許小艷;郝峗;慕運(yùn)動(dòng);;時(shí)間期望錯(cuò)位限制下完工時(shí)間和的隨機(jī)重新排序[J];河南科學(xué);2012年07期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8 謝芳;機(jī)器帶激活費(fèi)用的有限資源博弈排序[D];曲阜師范大學(xué);2012年

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

本文編號(hào)：2800367