帶有時間窗口約束的排序及相關(guān)問題研究.pdf

1、排序問題一直以來是經(jīng)典組合優(yōu)化問題之一，近幾十年來，正被越來越廣泛地應(yīng)用于生產(chǎn)與制造領(lǐng)域。本論文研究了帶有時間窗口約束的排序問題，可以被看作是一個新的資源約束模型，其在柔性制造系統(tǒng)和印刷電路板組件等方面具有潛在的應(yīng)用。論文分為四章，重點研究了近似算法的設(shè)計與分析。
　　第一章主要簡要介紹了排序問題的一些相關(guān)知識和國內(nèi)外研究的現(xiàn)狀，提供了幾個經(jīng)典排序問題的復(fù)雜性及其算法，同時也對啟發(fā)式算法與近似算法進行了一些簡單介紹。
　　第

2、二章研究了帶單位時間窗口約束的單機排序問題。要求任意單位時間內(nèi)最多只允許B個工件進行加工，對B2與B3兩種情況分別設(shè)計了近似算法，并證明當(dāng)B=2時，算法目標(biāo)值(此次公式省略)；當(dāng)B=3,4時，（此次公式省略），當(dāng)B≧5時，（此次公式省略）。
　　第三章在第二章的基礎(chǔ)上，討論了帶單位時間窗口約束的兩臺平行機排序問題。要求任意單位時間內(nèi)兩臺機器上最多允許B個工件進行加工。分析了LPT與LS兩個經(jīng)典算法的近似性能，當(dāng)B=2時，對LS算法

3、有（此次公式省略）；對LPT算法（此次公式省略）；而當(dāng)B≧3時，對LS算法有（此次公式省略）
　　第四章研究了一類帶外包選擇的單機排序問題。假設(shè)僅有一臺本地機器和一個外包承包商，每個工件既可以在本地機器上加工又可以外包商處加工。本地加工的費用為總誤工工件數(shù)，外包加工的費用與外包工件有關(guān)。對于極小化總加工費用這一NP難問題，給出偽多項式時間動態(tài)規(guī)劃算法。如果外包費用正比于外包工件的加工時間，設(shè)計出近似算法并給出最壞情況分析。