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

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

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

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

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

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