幾類新型在線分批排序問題.pdf

1、分類號：O22學校單位代碼：10446博士學位論文論文題目論文題目論文題目論文題目：：：：幾類新型在線分批排序幾類新型在線分批排序幾類新型在線分批排序幾類新型在線分批排序問題問題問題問題研究生姓名：王成飛學科、專業(yè)：數(shù)學、應用數(shù)學研究方向：組合最優(yōu)化導師姓名、職稱：張玉忠教授論文完成時間：2011年10月摘要本文提出并研究一些新型的排序問題，其模型是經(jīng)典排序問題和現(xiàn)有的排序問題的推廣。經(jīng)典排序問題中，工件的加工時間是不變的，我們研究工件

2、的加工時間依賴開工時間或者開工位置變化的模型；目前幾乎沒有研究在線與惡化效應結合的排序問題文獻，我們提出相關模型并研究；經(jīng)典的在線問題（overtime模型）是指工件只有到達后才知道信息，也就是說要做決策必須要等到工件到達，我們研究的在線模型是提前一段時間就知道工件的信息。本文研究的工件信息到達時間是依時間（overtime）的，分批模型是指平行批模型，即工件同一時刻最多加工B個工件，B為機器的容量，批的加工時間為該批工件中最大的加工時

3、間。本文主要由四個部分組成。第一章，我們介紹排序問題和算法復雜性的一些基本知識，并對在線排序、分批排序、帶惡化效應的排序的研究進行了綜述。第二章研究加工時間是一般函數(shù)的排序問題，主要考慮了兩類有一般加工時間函數(shù)的排序問題，工件的加工時間分別為基本加工時間與開工時間函數(shù)、位置函數(shù)的和。對于加工時間依賴開工時間的模型，證明一定條件下極小化最大完工時間和極小化總完工時間是多項式可解的。對于加工時間依賴開工位置的模型，給出極小化最大完工時間和總

4、完工時間的最優(yōu)序，同時證明了極小化加權總完工時間的一個最優(yōu)排序性質并給出一個貪婪算法。第三章研究加工時間是具有線性惡化效應的在線排序問題，工件Jj的實際加工時間為Pj=bjαt其中bj為基本加工時間α0為惡化率t是開工時間，目標為極小化最大完工時間。證明不分批的單機在線問題的下界至少為12α1α；對批容量無限的單機在線問題給出一個在線算法βH∞并證明其競爭比和問題的下界相同為(1α)β1，其中β=α?1√α22α52(1α)，進而算法是

5、最優(yōu)的；對于批容量無限的同型機排序問題，給出在線算法βmH∞并證明其競爭比為(1α)βm1，其中βm=m(α?1)√m2(1?α)24(α1)2(1α)。第四章研究工件具有提前預知信息的在線排序問題，從預知時間到工件可加工的時間之間間隔為a還知道工件的最大加工是為pmax，目標為極小化最大完工時間，對于批容量無限的單機在線問題給出一個在線算法γH∞并證明其競爭比和問題的下界相同為1γ，其中γ=(?1√14pmaxpmaxa)2，進而算法