在線平行機排序問題研究.pdf

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

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

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

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