具有同時(shí)性約束的平行機(jī)排序問題.pdf

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

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

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

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

5、，包括三個(gè)方面：計(jì)算復(fù)雜性，多項(xiàng)式時(shí)間算法及近似算法。具體的說，本論文的主要結(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)的多項(xiàng)式時(shí)間算法，如G為樹、單圈圖、完