有維護時段的機器排序問題研究.pdf

1、本文主要研究有維護時段的平行機排序問題的近似算法設(shè)計及其最壞情況界分析．對多個不同機器環(huán)境和目標(biāo)函數(shù)下的機器帶有維護時段的排序問題及其他相關(guān)問題，討論了這些問題的復(fù)雜性或難近似性，設(shè)計了相應(yīng)的近似算法并證明了其最壞情況界．
　　 全文共分為五章，第一章介紹了組合優(yōu)化問題，計算復(fù)雜性和近似算法以及與排序問題相關(guān)的一些預(yù)備知識，并敘述了機器有維護時段排序問題的背景．研究現(xiàn)狀和相關(guān)概念．
　　 第二章研究有維護時段的m臺同型機

2、排序問題，目標(biāo)為極小化工件總完工時間，工件加工為不可恢復(fù)情形．若每臺機器上均有多個維護時段，證明了該問題不存在最壞情況界為常數(shù)的多項式時間近似算法，若每臺機器上恰有一個維護時段且各臺機器上的維護時段互不重疊，該問題不存在最壞情況界小于m/m-1的多項式時間近似算法，除非P=NP.隨后考慮了前k(1≤k≤m-1)臺機器上均有多個維護時段的情形，證明了算法SPT的最壞情況界至多為m/m-k．當(dāng)前k（1≤k≤m）臺機器中每臺機器恰有一個維護時

3、段且各臺機器上的維護時段互不重疊時，證明了算法SPT的最壞情況界不超過2+k-1/m-1．
　　 第三章考慮有維護時段的兩臺同型機排序問題，目標(biāo)為極小化工件總完工時間，工件加工為不可恢復(fù)情形．若其中一臺機器上沒有維護時段而另一臺機器上恰有一個維護時段，證明了算法SPT的最壞情況界為3/2且該界是緊的．若兩臺機器上均恰有一個維護時段且兩臺機器上的維護時段互不重疊，算法SPT的最壞情況界為2且此時算法SPT是求解該問題的最壞情況界最

4、小的多項式時間近似算法，除非P=NP.
　　 第四章討論有維護時段的單機排序問題，工件加工為半可恢復(fù)情形．當(dāng)目標(biāo)函數(shù)為makespan時，給出了算法LPT的最壞情況界并得到了該問題的FPTAS.當(dāng)目標(biāo)為加權(quán)總完工時間時，設(shè)計了一個最壞情況界不超過2的多項式時間近似算法．此外，對于該目標(biāo)的兩個特殊情形，文中也分別給出了相應(yīng)的近似算法或近似方案的設(shè)計與分析．
　　 第五章研究一個與有維護時段相關(guān)的問題：有禁止操作時段的單機排