具有樹和路約束的平行機(jī)排序問(wèn)題*

程佳樂(lè)，李偉東

(云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南昆明650504)

1 引言

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

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

為更好地陳述相關(guān)的研究成果，下面給出理論計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)與本文相關(guān)的基本定義。

定義1［2］令Π 表示一個(gè)最小化問(wèn)題，I是該問(wèn)題的任意一個(gè)實(shí)例，A表示問(wèn)題Π的一個(gè)多項(xiàng)式時(shí)間算法，A(I)和OPT(I)分別表示算法A解決實(shí)例I所得到的可行解的目標(biāo)函數(shù)值和最優(yōu)值，則算法A的近似比定義為:

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

Wang等人［1］于2012年首次提出具有頂點(diǎn)覆蓋約束的平行機(jī)排序問(wèn)題(簡(jiǎn)記為P|vertex cover|Cmax)，其中，P表示在平行機(jī)器的環(huán)境下加工，Cmax表示機(jī)器的最大負(fù)載。對(duì)給定無(wú)向圖G=(V，E;w)，w:V→Q+(V、E分別是圖G的頂點(diǎn)集合和邊集合，w是對(duì)頂點(diǎn)集V的賦權(quán))，要找一頂點(diǎn)子集V'V，使得圖上每條邊至少有一個(gè)頂點(diǎn)屬于集合V'，則稱此頂點(diǎn)子集V'是一個(gè)頂點(diǎn)覆蓋。作者研究了在m臺(tái)相同的平行機(jī)上調(diào)度一組加權(quán)頂點(diǎn)子集，使得該子集是一個(gè)頂點(diǎn)覆蓋，目標(biāo)是使得機(jī)器的最大完工時(shí)間最小化?；诰植勘嚷史ê蚅PT(Largest Processing Time)算法，提出了近似比為3的算法。隨后，Wang等人［3］給出具有覆蓋約束的同類機(jī)排序問(wèn)題的通用性算法，算法的近似比依賴于覆蓋問(wèn)題的難度。2016年，Epstein等人［4］提出了關(guān)于Pm|vertex cover|Cmax問(wèn)題(機(jī)器數(shù)m固定)的2-近似算法以及關(guān)于P|vertex cover|Cmax問(wèn)題(機(jī)器數(shù)m不固定)的(2+ε)-近似算法(ε＞0為任意常數(shù))。

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

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

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

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

2 問(wèn)題描述

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

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

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

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

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

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

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

3 P|K-tree|Cmax問(wèn)題

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

問(wèn)題P|K-tree|Cmax的近似算法描述如下:

算法1問(wèn)題P|K-tree|Cmax的近似算法

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

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

Begin

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

Step 2應(yīng)用算法Α調(diào)度工件集{i1，i2，…，in+K}。

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

End

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

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

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

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

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

由算法1，我們得到P|K-tree|Cmax問(wèn)題的以下結(jié)果:

定理1對(duì)于P|K-tree|Cmax問(wèn)題，若子算法Α是α-近似，則算法1是α-近似的;且算法1的時(shí)間復(fù)雜度為O(n2+T(m，n))，其中T(m，n)是調(diào)度算法Α的運(yùn)行時(shí)間。

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

由于平行機(jī)排序問(wèn)題存在EPTAS［12］，所以有:

推論1P|K-tree|Cmax問(wèn)題有EPTAS。

4 P|s-t path|Cmax問(wèn)題

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

問(wèn)題P|s-t path|Cmax的近似算法描述如下:

算法2問(wèn)題P|s-t path|Cmax的近似算法

Input:無(wú)向圖 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問(wèn)題的以下結(jié)果:

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

5 P|the shortest path tree|Cmax問(wèn)題

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

問(wèn)題P|the shortest path tree|Cmax的近似算法描述如下:

算法3 問(wèn)題P|the shortest path tree|Cmax的近似算法

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

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

Begin

Step 1對(duì)D中的源頂點(diǎn)s，使用Dijkstra算法［14］構(gòu)造一輔助無(wú)圈有向圖Ds=(V，As;s)。

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

Step 3應(yīng)用算法Α調(diào)度工件集{i1，…，in}。

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

End

由算法3，我們得到P|the shortest path tree|Cmax問(wèn)題的以下結(jié)果:

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

對(duì)于圖Ts=(V，A's)和圖，有s定義為進(jìn)入頂點(diǎn)vk+1(k=1，…，n)的入弧 (在圖定義為進(jìn)入頂點(diǎn)vk+1的入弧)，因?yàn)樵趫D 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問(wèn)題

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

st=(V(SPst)k，A(SPst)k) ，將 A(SPst)k對(duì)應(yīng)的運(yùn)用LPT算法進(jìn)行平行機(jī)上的排序，得到可行解及其目標(biāo)函數(shù)值個(gè)可行解的目標(biāo)函數(shù)值，取其最小值作為輸出值。

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

算法4 P|the shortest s-t path|Cmax問(wèn)題的近似算法

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

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

Begin

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

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

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

End

引理2在所有可行解中，當(dāng)k=τ時(shí)，大工件數(shù)目最少。

證明在圖D'中，由權(quán)重w'的構(gòu)造知，上的大工件數(shù)目最少。證畢。 □

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

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

由算法4，我們可得P|the shortest s-t path|Cmax問(wèn)題的以下結(jié)果:

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

情形1大工件數(shù)不超過(guò)m。

情形2大工件數(shù)超過(guò)m。

7 結(jié)束語(yǔ)

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

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