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

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

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

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