有維護(hù)時(shí)段的機(jī)器排序問(wèn)題研究.pdf

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

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

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

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