具有同時性約束的平行機排序問題.pdf

1、排序理論是組合最優(yōu)化學(xué)科中一個蓬勃發(fā)展的研究方向。平行機排序是其中一個重要組成部分。在經(jīng)典的平行機排序文獻中，人們往往研究工件間的序約束。這種序約束是用一個有向圖D描述的先后順序關(guān)系，即一個工件必須在它的先行工件完工后才能開始加工。本論文研究工件間的另一種相互關(guān)系一—同時性關(guān)系，即一個工件必須與享有同一資源的其他工件同時加工。這種同時性約束用一個無向圖G來描述。例如對城市間的通道進行檢疫消毒時，圖G的頂點表示城市，邊表示城市間的通道；每

2、條邊都有一個檢疫任務(wù)，即一個工件。若干個平行作業(yè)的醫(yī)療隊用m臺平行機表示。為對疫情的傳播進行嚴格封鎖，同一城市引出的通道必須由相應(yīng)的醫(yī)療隊同時進行防疫處理。這就是說，關(guān)聯(lián)于圖G的一個頂點的邊工件必須同時加工。又如在對一個通訊網(wǎng)絡(luò)進行檢測時，從一個節(jié)點(交換臺站)發(fā)出檢測信號，在其引出的所有線路中，檢測人員必須同時進行操作。在其它系統(tǒng)中，當一些任務(wù)要共享一些資源(信息資源或物資資源)時，都有這種同時性約束。這樣一來，我們得到有同時性約束的

3、平行機排序問題如下：給定m臺平行機及一個無向圖G，其中G的邊代表工件(稱為“邊工件”)；若一個邊工件e=uv安排在時刻t開始加工，則關(guān)聯(lián)于u(或v)的全部未加工的邊工件必須也在時刻t開始加工。至于目標函數(shù)，仍與通常的平行機排序一樣，如最大完工時間Cmax或完工時間和∑Cj等等。按照傳統(tǒng)的三參數(shù)分類記號，此問題記為Pm|G-SMT|f，其中SMT為同時性(simultaneity)的簡寫，G表示工件間鄰接關(guān)系的圖，f為正則的目標函數(shù)，如C

4、max及∑Cj等等。這將稱為“一般模型”。在這個模型中，同一個時刻可以有多于一個頂點關(guān)聯(lián)的邊工件同時被加工(只要機器數(shù)足夠多)。但是，有些實際問題提出更苛刻的要求：任何時刻只有一個頂點關(guān)聯(lián)的邊工件可以被同時加工，也就是被處理的頂點呈一個序列形式，所以我們稱之為“序列模型”。 無論一般模型或序列模型，同時性約束的特點是：工件的安排受到機器數(shù)m及圖G的頂點度的雙重限制，所以此類問題的一般形式是困難的。本論文將從算法的觀點研究此類問題

5、，包括三個方面：計算復(fù)雜性，多項式時間算法及近似算法。具體的說，本論文的主要結(jié)果如下： 1.NP-完全性證明。對序列模型及一般模型，證明Pm|pi：1，G-SMT|Cmax及Pm|pj=1，G-SMT|∑Cj的判定形式是NP-完全問題。 2.對Pm|pj=1，G-SMT|Cmax給出(2-1/m)-近似算法。 3.對特殊圖G給出Pm|pj=1，G-SMT|Cmax(或∑Cj)的多項式時間算法，如G為樹、單圈圖、完