具有樹和路約束的平行機排序問題*

程佳樂，李偉東

(云南大學數學與統計學院，云南昆明650504)

1 引言

以最小化最大機器負載為目標的平行機排序問題在網絡資源分配、工業工程和電信等領域被廣泛應用，是運籌學和理論計算機科學等領域研究的重點內容之一。由于科學與社會的迅速發展，給制造、服務和管理等不同領域帶來了許多新問題，單純的平行機排序問題已不適用于實際情況。對此，Wang等人［1］首次提出具有圖結構約束的平行機排序問題。本文主要考慮具有樹和路約束的平行機排序問題，其定義如下:給定一無向圖(有向圖)，機器集 M={1，…，m}和工件集J={1，…，n}，任務j的處理時間為pj，工件集與無向圖(有向圖)的邊(弧)一一對應。選定一工件子集分配到m臺機器上處理，每個工件只能分配一臺機器。

令Sl表示在機器l上處理的工件集，機器l上的負載定義為在其上加工的所有工件的權重之和。本文要求尋找一種分配方案使得被選中的工件子集滿足無向圖(有向圖)上的路或樹的約束，目標是機器的最大負載(記為Cmax)盡可能達到最小。

為更好地陳述相關的研究成果，下面給出理論計算機科學領域內與本文相關的基本定義。

定義1［2］令Π 表示一個最小化問題，I是該問題的任意一個實例，A表示問題Π的一個多項式時間算法，A(I)和OPT(I)分別表示算法A解決實例I所得到的可行解的目標函數值和最優值，則算法A的近似比定義為:

定義2［2］對于最小化問題Π，若對任意的實數ε＞0，算法簇Aε都有一個(1+ε)-近似解，且運行時間是關于輸入長度的多項式函數，則稱算法簇Aε是一個多項式時間近似方案PTAS(Polynomial Time Approximation Scheme)。如果算法簇Aε的運行時間為，則稱之為有效多項式時間近似方案EPTAS(Efficient Polynomial-Time Approximation Scheme)，其中，f(1/ε) 表示關于1/ε的函數表示關于輸入長度的多項式函數。

Wang等人［1］于2012年首次提出具有頂點覆蓋約束的平行機排序問題(簡記為P|vertex cover|Cmax)，其中，P表示在平行機器的環境下加工，Cmax表示機器的最大負載。對給定無向圖G=(V，E;w)，w:V→Q+(V、E分別是圖G的頂點集合和邊集合，w是對頂點集V的賦權)，要找一頂點子集V'V，使得圖上每條邊至少有一個頂點屬于集合V'，則稱此頂點子集V'是一個頂點覆蓋。作者研究了在m臺相同的平行機上調度一組加權頂點子集，使得該子集是一個頂點覆蓋，目標是使得機器的最大完工時間最小化。基于局部比率法和LPT(Largest Processing Time)算法，提出了近似比為3的算法。隨后，Wang等人［3］給出具有覆蓋約束的同類機排序問題的通用性算法，算法的近似比依賴于覆蓋問題的難度。2016年，Epstein等人［4］提出了關于Pm|vertex cover|Cmax問題(機器數m固定)的2-近似算法以及關于P|vertex cover|Cmax問題(機器數m不固定)的(2+ε)-近似算法(ε＞0為任意常數)。

與此同時，Nip 等人［5，6］研究在最短路約束下的流水車間調度問題，即選取工件集的一個子集使其是給定圖中的一條路，將該工件子集中的工件放在流水車間處理，目標是使其最大完工時間(makespan)盡可能小。對于具有最短路約束的流水車間調度問題，當機器數為2時(簡記為F2|shortest path|Cmax)，分別存在近似比為 2和(3/2)(1+ε) 的算法。隨后，Nip 等人［7］研究在最短路約束下的開放車間調度(Open Shop Scheduling)和作業車間調度(Job Shop Scheduling)問題(簡記為 Om|shortest path|Cmax，Jm|shortest path|Cmax)，即選取工件集的一個子集使其是給定圖中的一條路，將該工件子集中的工件放在開放車間或作業車間條件下處理，目標是使得最大完工時間(makespan)盡可能小。

集裝箱問題和圖結構約束組合的問題也受到研究人員的關注。Li等人［8］研究了一系列具有圖結構約束的特殊材料的構建問題，作者于2014年首先考慮以下問題:給定一有向圖D=(V，A;w)以及長度為L的特定材料，要求在D中構造一個具有特殊結構的子圖D'，使得D'中的每一條弧都由特定材料構成，目標是使得在D'中構建所有弧的材料根數盡可能少(若弧長超過L，可用多根材料“拼接”而成)。對子圖D'的構建可等價于裝箱問題(箱子容量為L，對被選中物品(弧)構建相應的裝箱實例，目標是使得所需箱子數目最少)。隨后，Li等人［9］研究了具有支撐樹 CST(Constructing Spanning Tree)、單源最短路徑樹CSSPT(Constructing Single-source Shortest Path Tree)和滿足三角不等式的Steiner樹CMST(Constructing Metric Steiner Tree)等結構約束的裝箱問題。對于此三類問題，，其中k表示用長度為L的材料對K-tree TK中的邊集合進行構建所需要的材料根數。作者證明此問題是NP-hard的，且對于ε＞0，此問題的最優算法的近似比為3/2－ε，除非P=NP，并利用最小費用支撐K-樹的相關性質可得一個2-近似算法。

受上述文獻的啟發，本文主要研究如下四個問題:(1)在無向圖上分別具有路和K-樹約束的平行機排序問題;(2)在有向圖上分別具有單源點最短路徑樹和兩點間最短路約束的平行機排序問題。

本文結構如下:第2節給出四種問題的定義;第3節描述了解決無向圖上具有K-樹約束的平行機排序問題的α-近似算法(若平行機排序算法Α的近似比為α)，從而可有一個EPTAS;第4節給出一個解決無向圖上具有路的約束的平行機排序問題的(2－1/m)-近似算法;第5節提出解決有向圖上具有單源點最短路徑樹約束的平行機排序問題的α-近似算法(若平行機排序算法Α的近似比為α)，從而也可以得到一個EPTAS;第6節給出一個解決有向圖上兩點間最短路約束的平行機排序問題的1．618-近似算法;第7節對全文進行總結，并指出未來值得研究的方向。最好的算法近似比皆為3/2－ε，除非P=NP(ε＞0)。并對于CST問題和CSSPT問題分別提出了近似比都為3/2的算法，針對CMST問題，設計了一個近似比為4的算法。最近，Lichen等人［10］研究了具有K-樹約束的最小費用裝箱問題。對于無向圖G=(V，E;w，c)以及長度為L且費用為c0的特定材料，滿足w:E→Q+，c:E→(w為長度函數，c為費用函數)，新的目標為

2 問題描述

經典的平行機排序問題定義為:給定n個互相獨立的工件J={1，…，n}，m臺完全相同的機器M={1，…，m}(并行運行)，每個工件只需在一臺機器上不中斷地加工一次，并設m ＜n;工件j的處理時間為pj，所有工件在零時刻到達且所有機器在零時刻即可加工，并要求工件一旦在某個機器上加工就必須加工完畢，不允許中斷，目標是盡快加工完所有工件。如果工件j在時刻Cj被加工完成，則目標是找到一種調度使得機器的最大完工時間 Cmax盡可能地小，即 Cmax=maxj=1，…，nCj。本文主要考慮具有樹或路約束的平行機排序問題，涉及的定義如下:

定義3［11］(K-樹) 給定一無向圖 G=(V，E;w)，|V|=n+1，K-樹就是在圖G中找一個連通的支撐子圖TK=(V，ETK)，并且K=0時，0-樹就是支撐樹。

定義4(P|K-tree|Cmax) 給定無向圖G=(V，E;w)，|V|=n+1，|E|條邊分別為 e1，…，e|E|，w:E→Z+，K為固定正整數;m臺機器，每一條邊ej∈E對應一個工件j∈J，加工時間為pj=wj;要找一棵K-樹TK=(V，ETK)，將其邊集合ETK對應的工件集放在平行機下處理，目標是使其最大完工時間(makespan)盡可能小。

定義5(P|s-t path|Cmax) 給定無向圖G=(V，E;w)，兩個固定頂點 s，t∈ V，w:E → Z+，|V|個頂點分別為v1，…，v|V|，|E|條邊分別為e1，…，e|E|;m臺機器，每一條邊ej∈E對應一個工件j∈J，加工時間為 pj=wj，要找一條 s-t路 Pst=(V(Pst)，E(Pst))，將其邊集合E(Pst)對應的工件集放在平行機下處理，目標是使其最大完工時間(makespan)盡可能小。

定義6最短路徑樹(the shortest path tree) 給定一有向圖D=(V，A;s;w)，s為固定頂點，w:A→Z+;要找一棵以s為根的最短路徑樹T=(V，As)，使得在T中從根s到其他任何頂點u∈V－{s}的距離是原圖D上從s到u的最短路徑距離。

定義7(P|the shortest path tree|Cmax) 給定一有向圖 D=(V，A;s;w)，|V|=n+1，s為固定頂點，w:A→Z+;m臺機器，每一條弧ej∈A對應一個工件j∈J，加工時間為pj=wj，要找一最短路徑樹Ts=(V，A's)，將其弧集合A's對應的工件集放在平行機下處理，目標是使其最大完工時間(makespan)盡可能小。

定義8(P|the shortest s-t path|Cmax) 給定一有向圖 D=(V，A;s，t;w)，s，t為固定頂點，w:A →Z+，|V| 個頂點分別為 v1，…，v|V|，條弧分別m臺機器，每一條弧ej∈A對應一個工件j∈J，加工時間為pj=wj，要找一條最短s-t路 SPst= (V(SPst)，A(SPst))，將 其 弧 集 合A(SPst)對應的工件集放在平行機下處理，目標是使其最大完工時間(makespan)盡可能小。

3 P|K-tree|Cmax問題

在本節中，考慮在K-樹約束下的平行機排序問題。對于此問題，我們的策略是:(1)調用Fisher算法［11］在圖 G中尋找一棵最小支撐 K-樹 TK=(V，ETK);(2)將邊集合ETK對應的工件集運用平行機調度算法Α進行排序。

問題P|K-tree|Cmax的近似算法描述如下:

算法1問題P|K-tree|Cmax的近似算法

Input:無向圖G=(V，E;w)及非負整數K。

Output:S1，S2，…，Sm和 Cmax。

Begin

Step 1在圖G中調用Fisher算法［11］尋找一棵最小支撐 K-樹 TK=(V，ETK) ，其邊集合 ETK={ei1，ei2，…，ein+K} ，對應工件集為 {i1，i2，…，in+K}。

Step 2應用算法Α調度工件集{i1，i2，…，in+K}。

Step 3輸出 S1，S2，…，Sm和 Cmax，這里 Si表示分配給機器i的工件集。

End

要證明算法1的近似比，首先引入如下引理:

引理1給定無向圖G=(V，E;w)，|V|=n+1，w:E→Z+，K 為非負整數;TK=(V，ETK)是圖 G的一棵最小支撐 K-樹，其邊集 ETK={ei1，ei2，…，ET*K)是對應于問題P|K-tree|Cmax最優解的一棵最優支撐K-樹，其邊集且有…，n+K。

考慮以下兩種情形，每種情形都將導致矛盾，從而證明該引理。

情形1至少存在一條邊 eit'∈{eit，eit+1，…，ein+K}，使得eit'不是圖G的割邊。

情形2每一條邊都是圖G的割邊。

由算法1，我們得到P|K-tree|Cmax問題的以下結果:

定理1對于P|K-tree|Cmax問題，若子算法Α是α-近似，則算法1是α-近似的;且算法1的時間復雜度為O(n2+T(m，n))，其中T(m，n)是調度算法Α的運行時間。

證明設TK=(V，ETK)是由算法1得到的最小支撐 K-樹，其邊集合且 w，輸出解為 S1，S2，…，Sm，輸出值 C是對應于最優值的最優支撐K-樹，其邊集合

由于平行機排序問題存在EPTAS［12］，所以有:

推論1P|K-tree|Cmax問題有EPTAS。

4 P|s-t path|Cmax問題

在本節中，考慮在路的約束下的平行機排序問題。對于此問題，我們的策略是:(1)給定原圖G=(V，E;s，t;w)，兩個固定頂點 s，t∈ V，w:E →Z+，對圖G上的每一條邊ek，構建新圖Gk=(V，Ek;w)(邊e∈Ek當且僅當w(e)≤w(ek))，在圖Gk中調用 prim's算法［13］尋找一條最短 s-t路對應的工件運用LS(List Scheduling)算法進行平行機上的排序，得到可行解及其目標函數值Ckmax;(2)比較|E|個可行解的目標函數值，取其最小值作為輸出值。

問題P|s-t path|Cmax的近似算法描述如下:

算法2問題P|s-t path|Cmax的近似算法

Input:無向圖 G=(V，E;s，t;w);s，t∈ V。

Output:S1，S2，…，Sm和 Cmax。

Begin

Step 1置S1=S2=… =Sm=，Cmax=+∞。

Step 3輸出 S1，S2，…，Sm和 Cmax。

End

由算法2，我們得到P|s-t path|Cmax問題的以下結果:

定理2算法2是一個復雜度為O(|E|(|V|2+|E|m))的(2－1/m)-近似算法。

5 P|the shortest path tree|Cmax問題

在本節中，考慮在最短路徑樹的約束下的平行機排序問題。對于此問題，我們的策略是:(1)對于有向圖D=(V，A;s;w)的源頂點s，使用Dijkstra算法［14］構造一個輔助無圈有向圖Ds=(V，As;s);(2)對每個頂點u∈V－{s}，在Ds中選擇一條進入u且其權重最小的入弧，得到以s為根的樹形圖Ts=(V，A's);(3)將弧集合A's對應的工件集運用平行機調度算法Α進行排序。

問題P|the shortest path tree|Cmax的近似算法描述如下:

算法3 問題P|the shortest path tree|Cmax的近似算法

Input:有向圖 D=(V，A;s;w)。

Output:S1，S2，…，Sm和 Cmax。

Begin

Step 1對D中的源頂點s，使用Dijkstra算法［14］構造一輔助無圈有向圖Ds=(V，As;s)。

Step 2對于每個頂點u∈V－{s}，在Ds中選擇一條進入u且其權重最小的入弧，得到一個以s為根的樹形圖 Ts=(V，A's) ，其中 A's={ei1，…，ein} ，對應工件集為{i1，…，in}。

Step 3應用算法Α調度工件集{i1，…，in}。

Step 4輸出 S1，S2，…，Sm和 Cmax。

End

由算法3，我們得到P|the shortest path tree|Cmax問題的以下結果:

定理3對于P|the shortest path tree|Cmax問題，若子算法 Α是 α-近似的，則算法3是 α-近似的;且算法3的時間復雜度為O(n2+T(m，n))，其中T(m，n)是調度算法Α的運行時間。

對于圖Ts=(V，A's)和圖，有s定義為進入頂點vk+1(k=1，…，n)的入弧 (在圖定義為進入頂點vk+1的入弧)，因為在圖 Ds= (V，As;s) 中，滿足 dG(s，x) =dDs(s，x)(x∈ V) ，由 Step 2有:

(1)Ts是以s為根的最小樹形圖(TsDs)。

(2)dDs(s，x)=dTs(s，x)(x ∈ V)。

6 P|the shortest s-t path|Cmax問題

在本節中，考慮在最短s-t路的約束下的平行機排序問題。對于此問題，我們的策略是:(1)運用Dijkstra算法［14］求得所有最短s-t路構成的子圖(其中 A'是構成所有最短 s-t路的弧集合，必有其權重值w(e)保持不變)及其最短路長度(記為L);(2)對圖上的每一條邊ek，構建新圖，(在這里(3)在圖 Dk中調用 prim’s算法［13］尋找一條權重為 w'(e)時的最短 s-t路SPk

st=(V(SPst)k，A(SPst)k) ，將 A(SPst)k對應的運用LPT算法進行平行機上的排序，得到可行解及其目標函數值個可行解的目標函數值，取其最小值作為輸出值。

P|the shortest s-t path|Cmax問題的近似算法描述如下:

算法4 P|the shortest s-t path|Cmax問題的近似算法

Input:有向圖 D=(V，A;s，t;w)。

Output:S1，S2，…，Sm和 Cmax。

Begin

Step 1置S1=S2=… =Sm=，Cmax=+∞。

Step 2運用Dijkstra算法［14］求得所有s-t最短路構成的子圖D'=(V，A';s，t;w)及其最短路長度(記為L)。

Step 4輸出 S1，S2，…，Sm和 Cmax。

End

引理2在所有可行解中，當k=τ時，大工件數目最少。

證明在圖D'中，由權重w'的構造知，上的大工件數目最少。證畢。 □

引理3在可行解中，最多有2m個大工件，即對于任意的(l=1，…，m) ，加工的大工件數最多為2。

證明(反證法) 若可行解中的大工件數超過2m，則對所有工件完成時間之和T有:T，不構成s-t最短路的可行解，矛盾，從而結論成立。證畢。 □

由算法4，我們可得P|the shortest s-t path|Cmax問題的以下結果:

定理4算法4是一個復雜度為O(|V|2+的-近似算法。

情形1大工件數不超過m。

情形2大工件數超過m。

7 結束語

本文具體研究了四種在樹和路約束下的平行機排序問題，設計了相應的多項式時間算法，并分析了算法的近似比。其中，在無(有)向圖上具有(最短)路約束的平行機排序問題，能否設計一個更好的近似算法是值得研究的問題。

文獻［3］給出了具有覆蓋約束的平行機排序問題的通用算法。Wang等人［3］指出，對于特定的圖結構約束，能否設計更好的近似算法值得探討。本文中所提到的四個問題正是特定的圖結構約束下的平行機排序問題，但是，還有許多圖結構(如樹形圖等)約束的平行機排序問題的近似算法設計問題未得到解決。