具有相容約束條件的單機(jī)平行分批排序問題.pdf

1、本論文主要就以下兩方面的問題進(jìn)行了研究。首先，目標(biāo)函數(shù)是最大完工時間情形，當(dāng)圖G是一般二部圖、完全二部圖、完全m部圖、直徑不超過4的樹以及分裂圖時，分別給出了排序問題的多項式時間的算法。具體結(jié)論如下： (1)排序問題1|p-batch；G|Cmax的判定問題是NP-完全的。 (2)當(dāng)把圖G限定為一般二部圖G=(X，Y；E)，X={p1,…，pm}，Y={q1,…，qn}時，其中pi，qj(對所有的i，j)也表示相應(yīng)工件的

2、加工時間，則對問題1|p-batch；bipartite|Cmax給出了多項式算法，使得在O(n3)時間內(nèi)給出問題的最優(yōu)排序。 (3)給定完全二部圖G=(X，Y；E)，其中X={p1,…，pm}，Y={q1,…，qn}，而pi，qj也分別代表相應(yīng)的工件的加工時間。不失一般性，我們假定m≤n。這種情況下給出了時間界為D(nlogn)的多項式算法，使得在該時間內(nèi)給出排序問題1|p-batch；completebipartite|Cm