在線平行機(jī)排序問題研究.pdf

1、排序(調(diào)度)理論是近年來組合優(yōu)化方向很活躍的一個(gè)研究分支,受到眾多學(xué)者的關(guān)注.對(duì)于排序問題的研究已有幾十年的歷史.本文研究了近十幾年發(fā)展起來的若干在線排序問題.全書共分為六章,第一章主要介紹與排序問題相關(guān)的一些概念和預(yù)備知識(shí)。 第二章主要研究工件具有相同的加工時(shí)間1,有到達(dá)時(shí)間和交貨期且目標(biāo)函數(shù)為極大化按時(shí)完工的工件個(gè)數(shù)的兩臺(tái)機(jī)在線排序問題.首先,我們對(duì)于m臺(tái)機(jī)時(shí)的問題給出了該問題的一個(gè)下界；其次,我們對(duì)于m臺(tái)機(jī)的情形給出了一個(gè)

2、簡(jiǎn)單的具有競(jìng)爭(zhēng)比為2的在線算法；最后,對(duì)于兩臺(tái)機(jī)的情形,我們給出了一個(gè)最好的在線近似算法,而且算法滿足“立即通知”的性質(zhì)。 第三章研究上一章中當(dāng)m≥2時(shí)的問題.為方便起見,我們考慮工件具有相同的整數(shù)加工時(shí)間p,且有非負(fù)整數(shù)到達(dá)時(shí)間和交貨期,目標(biāo)函數(shù)為極大化按時(shí)完工的工件個(gè)數(shù)的m臺(tái)機(jī)在線排序問題.易知對(duì)于任意的p,該問題與上述問題具有等價(jià)性.對(duì)于該問題我們給出了一個(gè)具有“立即決定”性質(zhì)的在線算法,并證明了該算法的競(jìng)爭(zhēng)比為1/(1-

3、(m/(m+1))m),其中當(dāng)m趨向于無窮大時(shí),該競(jìng)爭(zhēng)比趨向于e/(e-1)≈1.582.另外,我們還給出了對(duì)于該問題具有“立即決定”性質(zhì)的在線算法的一些下界。 第四章研究工件的加工長(zhǎng)度任意,有到達(dá)時(shí)間和交貨期,且工件可以“中斷-重新”開始加工,目標(biāo)函數(shù)為極大化按時(shí)完工的工件個(gè)數(shù)的m臺(tái)機(jī)在線排序問題.這里的可“中斷-重新”開始加工指的是工件在加工過程中可以被中斷,但當(dāng)算法在下次執(zhí)行此工件時(shí)必須從頭開始加工.對(duì)于該問題,我們首先給

4、出了一個(gè)4/3的下界,然后給出了一個(gè)競(jìng)爭(zhēng)比為2的在線算法。 第五章研究工件具有“任意”的到達(dá)時(shí)間,目標(biāo)函數(shù)為最小化最大工件完工時(shí)間(makespan)的m(m≥2)臺(tái)機(jī)的在線排序問題.這里的問題模型指的是工件按一定先后順序出現(xiàn),只有當(dāng)前面的工件被安排后才知道下一個(gè)工件的信息.與經(jīng)典在線模型不同的是前面的工件的到達(dá)時(shí)間有可能比后面的工件到達(dá)時(shí)間要大.此問題可以看成是經(jīng)典的在線模型(Jobs Arrive over list)的推廣