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

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

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

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