在線排序研究具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。近二十年來,在線排序得到國內(nèi)外同行的廣泛關(guān)注和深入研究,并促使其成為現(xiàn)代排序領(lǐng)域中發(fā)展最為迅速的方向之一。本文所說的“在線”是指時(shí)間在線(online over time)。也就是說,工件是隨著時(shí)間依次到達(dá)的,并且事先不知道它的一切信息。求解在線問題的算法稱為在線算法。對一個(gè)最小化目標(biāo)函數(shù)的在線排序問題,在線算法A的競爭比定義為ρA=sup{A(I)/OPT(I):I是滿足OPT(I)0的任一實(shí)例}.由此可見,競爭比越接近于1,就表明在線算法的性能越優(yōu)良。如果不存在其他的競爭比小于A的競爭比的在線算法,就稱在線算法A是最好可能的(best possible)。工件的加權(quán)完工時(shí)間和是排序的主要優(yōu)化指標(biāo)之一。本學(xué)位論文研究了若干與最小化工件的加權(quán)完工時(shí)間和相關(guān)的在線排序問題。學(xué)位論文共有六章:第一章主要介紹了一些與組合最優(yōu)化以及排序問題相關(guān)的概念,并介紹了在線排序的研究現(xiàn)狀,特別是最小化加權(quán)完工時(shí)間和的在線排序的研究現(xiàn)狀。第二章研究了工件可拒絕的在線排序,其中每個(gè)工件Jj或者被拒絕加工并支付拒絕費(fèi)用ej,或者被機(jī)器接收并加工。目標(biāo)是最小化接收工件的加權(quán)完工時(shí)間和加上被拒絕工件的拒絕費(fèi)用和。?對于一臺機(jī)器工件有相同的權(quán)重且加工時(shí)間和拒絕費(fèi)用滿足一致性條件的情形,給出了一個(gè)競爭比為2的最好可能的在線算法DSPTR。?對于一臺機(jī)器上問題的一般情形,給出了一個(gè)競爭比為2的最好可能的在線算法DSWPTR,推廣了Anderson和Potts發(fā)表于《Mathematics of Operations Research,2004》的結(jié)果。該結(jié)果也是本章上一個(gè)結(jié)果的推廣,但是論證技巧上截然不同。我們首先將在線算法柔性化,然后采用實(shí)例歸結(jié)的技巧進(jìn)行論證。?在多臺恒同機(jī)(identical machines)上,我們給出了一個(gè)競爭比至多為4+的在線算法,在多臺無關(guān)機(jī)(unrelated machines)上,我們給出了一個(gè)競爭比至多為8的在線算法。第三章研究了一臺機(jī)器最小化時(shí)間表長和加權(quán)完工時(shí)間和的在線折衷排序問題。我們引入了最小化f1和f2的在線折衷排序。稱一個(gè)在線算法A是(ρ1,ρ2)-競爭的,如果最小化f1時(shí)A是ρ1-競爭的而最小化f2時(shí)A是ρ2-競爭的。對于一個(gè)(ρ1,ρ2)-競爭的在線算法A,如果不存在(ρ1,ρ2)-競爭的在線算法A滿足(ρ1,ρ2)≤(ρ1,ρ2)并且有ρ1ρ1或者ρ2ρ2,則在線算法A被稱為是不可支配的(nondominated).?對于該問題,我們給出了一個(gè)參數(shù)在線算法,并利用兩種不同的方法分別證明了該算法對于滿足0α≤1的任意α是一個(gè)競爭比為(1+α,1+1/α)的不可支配的在線算法。此結(jié)果推廣了Anderson和Potts發(fā)表于《Mathematics of Operations Research,2004》的結(jié)果。第四章研究了多臺平行批機(jī)器上批容量有限目標(biāo)函數(shù)為最小化加權(quán)完工時(shí)間和的在線排序問題。?在一致機(jī)(uniform machines)上,當(dāng)機(jī)器臺數(shù)m為常數(shù)時(shí),我們得到了一個(gè)競爭比至多為4+的在線算法。?在恒同機(jī)上,當(dāng)機(jī)器臺數(shù)m任意時(shí),我們也得到了一個(gè)競爭比至多為4+的在線算法。該項(xiàng)工作改進(jìn)了Zhang等人發(fā)表于《Journal of Industrial and Management Optimization,2007》對此問題給出的競爭比至多為8的在線算法。第五章研究了一臺機(jī)器上工件加工時(shí)間可退化的最小化加權(quán)完工時(shí)間和的在線排序問題。在該問題中,工件Jj的加工時(shí)間為pj=αj(A+Bsj),其中A≥0,B≥0,A和B至少有一個(gè)非零,αj≥0是工件Jj的退化率,sj≥0是工件Jj的開工時(shí)間。?我們給出了一個(gè)競爭比為1+λ(A)+αmaxB的最好可能的在線算法,其中αmax=max1≤j≤nαj,而λ(A)=0或λ(A)=1取決于A=0或A0。該項(xiàng)工作將Liu等人發(fā)表于《Theoretical Computer Science,2012》的簡單線性退化并且工件權(quán)重都相等時(shí)的結(jié)果推廣到了線性退化并且工件權(quán)重不同的更一般的情形。第六章總結(jié)了本學(xué)位論文所研究的主要內(nèi)容和取得的一些主要結(jié)果,并指出了存在的一些問題以及未來的一些研究方向。
【學(xué)位單位】：鄭州大學(xué)
【學(xué)位級別】：博士
【學(xué)位年份】：2015
【中圖分類】：O223
【文章目錄】：
摘要
Abstract
第1章 緒論
    1.1 排序問題
    1.2 排序問題的三參數(shù)表示
    1.3 離線排序
    1.4 在線排序
    1.5 相關(guān)文獻(xiàn)綜述
        1.5.1 最小化加權(quán)完工時(shí)間和的時(shí)間在線排序問題
        1.5.2 帶工件拒絕的的機(jī)器排序
        1.5.3 分批排序
        1.5.4 工件加工時(shí)間可退化的機(jī)器排序
        1.5.5 本文結(jié)果
第2章 工件可拒絕的在線排序問題
    2.1 引言
    2.2 本章的結(jié)構(gòu)
    2.3 一致條件下權(quán)重相同的情形
    2.4 一般情形
        2.4.1 準(zhǔn)備工作
        2.4.2 算法和分析
    2.5 平行機(jī)情形
        2.5.1 準(zhǔn)備知識
        2.5.2 算法和分析
第3章 在線折衷排序問題研究
    3.1 引言
    3.2 準(zhǔn)備工作
    3.3 實(shí)例歸結(jié)方法證明
        3.3.1 準(zhǔn)備知識
        3.3.2 競爭比分析
    3.4 組合方法證明
        3.4.1 兩個(gè)輔助問題的定義
        3.4.2 缺口工件的性質(zhì)
        3.4.3 為問題 （E） 創(chuàng)建一個(gè)可行排序
        3.4.4 主要結(jié)果的證明
    3.5 算法的非支配性證明
第4章 最小化加權(quán)完工時(shí)間和的平行機(jī)在線分批排序
    4.1 引言
    4.2 相關(guān)工作
    4.3 問題MSWP（Qm-batch） 的對偶FPTAS
    4.4 問題MSWP（P -batch） 的對偶PTAS
第5章 工件線性退化的在線排序研究
    5.1 引言
    5.2 相關(guān)工作
    5.3 準(zhǔn)備工作
    5.4 算法及分析
第6章 結(jié)論與展望
參考文獻(xiàn)
個(gè)人簡歷、在學(xué)期間完成的學(xué)術(shù)論文與研究成果
致謝

【相似文獻(xiàn)】

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

1 李曙光,李國君,趙浩;無限批量調(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 曹國梅;石忠和;;加工時(shí)間相同的分族分批排序加權(quán)總完工時(shí)間問題[J];安陽工學(xué)院學(xué)報(bào);2009年04期

5 李曙光;李國君;趙洪鑾;;極小化完工時(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 金霽;顧燕紅;唐國春;;最大完工時(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)博士學(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 張國輝;柔性作業(yè)車間調(diào)度方法研究[D];華中科技大學(xué);2009年

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

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

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

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

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

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

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

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

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

本文編號：2876881