發(fā)布時間：2020-11-09 19:40

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

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關博士學位論文 前6條

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

2 李曙光;批調度與網絡問題的組合算法[D];山東大學;2007年

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

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

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

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

相關碩士學位論文 前7條

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

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

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

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

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

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

7 苗許娜;關于重新排序的一些結果[D];鄭州大學;2006年

本文編號：2876881