基于穴度的三維時空優(yōu)化問題的貪心調度算法*

朱　鵬，何　琨，曹偉剛，楊　歡華中科技大學 計算機科學與技術學院，武漢 430074

基于穴度的三維時空優(yōu)化問題的貪心調度算法*

朱鵬，何琨+，曹偉剛，楊歡
華中科技大學 計算機科學與技術學院，武漢 430074

ZHU Peng,HE Kun,CAO Weigang,et al.Caving-degree based greedy scheduling algorithm for threedimensional space-time optimization problem.Journal of Frontiers of Computer Science and Technology, 2016,10(8)：1051-1062.

摘要：研究了基于二維矩形Packing的三維時空優(yōu)化問題，即對給定的一個任意寬、高的大矩形框和有限個有連續(xù)加工時間要求的任意寬、高的小矩形塊，如何安排每個小矩形塊的入框時刻及其出框前每一時刻的位置和方向，使得所有小矩形塊的總加工時間即總調度長度makespan最短。與經典布局問題的不同之處在于，各矩形塊在框內可隨時間的綿延而改變其位置和方向，從而能更充分地利用矩形框的空間?；趯嵔桥c實占角動作的定義，設計了求解其子問題二維矩形Packing問題的增強穴度算法。然后，每步迭代優(yōu)先考慮剩余加工時間長的矩形塊，提出了求解此問題的貪心穴度調度算法（caving-degree based greedy scheduling algorithm，CGSA）。作為比較，同時設計了矩形塊在框內不可隨時間移動的將時間簡單類比為空間的對應Packing問題的調度算法 CGSA′。對于實驗中提出的滿足非閘斷模式的4個小型算例，它們在原問題上的最優(yōu)調度長度為2，但若將時間簡單地類比為空間，即矩形塊放入框內后不可隨時間移動其方位，則其最優(yōu)調度長度為3。實驗表明，算法CGSA在這4個非閘斷算例上均得到了最優(yōu)調度。進一步地研究出滿足閘斷模式的21組共210個自動生成算例，通過實驗驗證了算法CGSA的最優(yōu)解的數(shù)目明顯多于CGSA′，且CGSA的平均調度長度明顯短于CGSA′。

關鍵詞：時空優(yōu)化；貪心調度；裝箱；算例；布局

1　引言

本文研究以二維矩形Packing問題為子問題，進一步考慮時間因素的三維時空優(yōu)化問題。此類考慮時間與空間的復合優(yōu)化問題，在現(xiàn)實生活中有著廣泛的應用，例如內存空間的分配、處理機的調度[1-2]、數(shù)據(jù)庫存儲空間的分配、餅干的烘制、組裝線的調度[3]等。以內存空間的分配為例，將待分配的內存空間視為一個大的矩形框，將待調度的作業(yè)視為形狀大小給定的小矩形塊，將作業(yè)需要連續(xù)調度的時間區(qū)間長度視為矩形塊需要持續(xù)放入矩形框內的時間長度。如圖1所示，從而可將如何調度這些作業(yè)使其占用內存空間的時間跨度最短的問題轉化為如何調度和布局這些小矩形塊使大矩形框被占用的時間跨度最短的裝箱調度問題。

Fig.1　Memory scheduling schematic圖1　內存調度示意圖

黃文奇、何琨于2010年提出了考慮時間因素的三維裝箱工作的優(yōu)化調度問題[4]，并給出了其可計算性的完整證明[5-6]。到目前為止，國內外文獻中尚未見到其快速求解算法和相關算例的研究。

對于其二維退化情形即三維時空優(yōu)化問題，其子問題二維矩形Packing問題已被證明是強NP難度問題[7]。在此基礎上，三維時空優(yōu)化問題還需考慮連續(xù)量時間的變化，因此其計算復雜度非常高。目前國內外文獻中尚未見到相關快速求解算法和算例的研究。

對于其子問題即二維矩形Packing問題，自20世紀60年代以來，國內外學者做了大量的研究。目前，具有代表性的算法可以分為隨機型算法和確定型算法兩大類。其中隨機型算法主要包括遺傳算法[8-10]、模擬退火算法[11]、粒子群算法[12]、蟻群算法[13]等；確定型算法主要包括BL（bottom left）算法[14]、BLF（bottom left fill）算法[15]、BLD（bottom left decreasing）算法[16]、分支限界法[17]、擬物擬人法[18-21]等。

本文擬對三維時空優(yōu)化問題的快速求解算法進行研究。首先對于其子問題——二維矩形Packing問題，在基于動作空間的穴度算法[22]的基礎上，提出了基線與實角的概念，以提高算法的計算速度。然后，優(yōu)先考慮剩余加工時間長的矩形塊，設計了求解三維時空優(yōu)化問題的貪心算法。并進一步設計了結合問題特色和優(yōu)勢的若干小型算例和自動生成算例，以檢測算法的性能。

2　問題描述

三維時空優(yōu)化問題是指在二維歐氏空間中，已知一個寬W、高H分別任意給定的大矩形框和n個寬Wi、高Hi分別任意給定的需要連續(xù)加工的小矩形塊，各矩形塊的待加工時間Ti也任意給定。其中n為任意給定的正整數(shù)，其他參數(shù)均為正有理數(shù)。問如何在矩形框內安排所有的小矩形塊，使最后取出的那個矩形塊的出框時刻最小。即要求給出：

（1）每個矩形塊放入容器的時刻Si；

（2）每個矩形塊在時間區(qū)間[Si,Si+Ti)內的每一時刻所處的位置和方向。

目標是使得所有小矩形塊的總加工時間即總調度長度makespan最小，即使得公式 max(S1+T1,S2+ T2,…,Sn+Tn)－min(S1,S2,…,Sn)最小。

約束條件為任意時刻放入的矩形塊完全在框內，邊平行于大矩形框的邊，且各小矩形塊之間兩兩互不嵌入。

此問題雖然與二維歐氏空間中的Packing問題有關，但不是二維矩形Packing問題，也不是三維歐氏空間中的Packing問題，而是要隨著時間的改變在二維歐氏空間中規(guī)劃諸矩形塊在矩形框中的存放和運動。

若將此問題中的時間物理量簡單地類比為空間物理量，則此問題退化為高方向固定的三維Strip Packing問題[23]。三維Strip Packing問題是指給定一個底面長寬固定、高無限的長方體箱，如何將給定的有限個小長方體無嵌入地、正交地放入到長方體箱中，使得放入后小長方體的最高高度最小。若小長方體的高不可旋轉，則為高方向固定的Strip Packing問題。若將小矩形塊的加工時間視為小長方體的高，則矩形框的總體利用時間相當于長方體箱的最高高度，退化后兩個問題等價。

在三維時空優(yōu)化問題中，小矩形塊在大矩形框中每一時刻均可改變其位置和方向進行再調度，因此該問題的最優(yōu)解一定不劣于高方向固定的三維Strip Packing問題的最優(yōu)解。

3　算法描述

在調度過程中，如果每一時刻均能保證矩形框空間的利用率為100%，那么所得調度的makespan必然最短。因此首先需要設計矩形Packing問題的高效求解算法，使得每一時刻矩形框盡量布滿。首先給出基于實角的矩形Packing問題的增強穴度算法。在此基礎上，進一步設計了三維時空優(yōu)化問題的貪心穴度調度算法。

3.1矩形Packing問題的增強穴度算法

對于子問題二維矩形Packing問題，本文參考基于動作空間的穴度算法，定義了基線、實角和虛角等概念，并改進了穴度的內容，提出了基于實角的二維矩形Packing問題的增強穴度算法，包括基本穴度算法A0與增強穴度算法A1。

3.1.1相關概念的定義

定義1（格局）設某個時刻，矩形框內已經放入了若干個矩形塊，還有若干個矩形塊待放，這稱為一個格局。格局可分為初始格局、當前格局和終止格局?？騼任捶湃肴魏螇K時為初始格局。框內已經放滿或者容器外剩余的矩形塊無法再放入時為終止格局。對每一格局，可用布局X＝(x1,y1,o1,x2,y2,o2,…, xn,yn,on)來描述小矩形塊在大矩形框中的位置和方向。其中xi、yi表示塊i的左下角坐標，oi表示塊i的放入方向為橫放還是豎放。

定義2（基線）基線是指在當前格局下，所有已經放入的小矩形塊的邊以及大矩形框的邊。

初始格局只有4條基線，即大矩形框的4條邊。基線是一種描述邊界的方法，又細分為垂直基線和水平基線。

定義3（動作空間）在當前格局下，往矩形框中合法地放入一個虛擬的矩形塊。若該矩形塊的上、下、左、右均與已放入矩形塊的邊或框邊相貼（即重合的長度大于0），則該虛擬的矩形塊所占的空間稱為當前格局下的一個動作空間。

如圖2所示，矩形塊BCDQ和ABPF為動作空間。動作空間由4條基線或其延長線所圍成。

Fig.2　An example of action space and angle圖2　動作空間與角示例

定義4（實角與虛角）動作空間的每一個角由一個頂點和兩條基線或其延長線所圍成。又分為實角和虛角。實角由兩條基線所圍成，虛角的兩條邊中至少有一條是基線的延長線。

如圖2所示，在動作空間BCDQ中，角QBC、BCD、CDQ是實角，角BQD是虛角。

定義5（實占角動作）在當前的格局下，若將一個矩形塊放入到動作空間的一個實角，使放入塊的頂點和角的頂點重合，頂點對應的邊分別與角的兩條邊相貼，而且該放入塊不超出動作空間，則稱此動作為一個實占角動作。

對于每個小矩形塊的放入，不是單純地考察當前矩形框的面積利用率，而是盡量希望能從整體層面來進行評價。直觀地來講，如果小矩形塊放入后，剩余空間參差不齊，則不利于后續(xù)塊的放入；如果放入后，剩余空間比較平整，那么對后續(xù)的放置就留下了較大的余地。

定義6（重合度co）重合度是指放入矩形塊與已放入矩形塊以及大矩形框相貼的邊長與矩形塊的周長之比。

定義7（相近度ed）相近度與最小距離dmin有關，記為ed=exp(-dmin)，最小距離是指放入矩形塊與所有未相貼的已放入矩形塊之間的最小距離。

定義8（穴度）穴度是一個三元組，為 。其中，k表示貼邊數(shù)，即放入矩形塊與當前動作空間相貼的邊的數(shù)目；co表示重合度；ed表示相近度。

穴度表示實占角動作與當前動作空間的緊密程度，穴度的比較即依字典序比較此三元組的大小。穴度越大，說明放入塊與動作空間相貼的邊越多，與其他放入塊或框相貼的比率越大，與其他放入塊距離越近，從而與實動作空間的吻合程度越好。

定義9（評判準則）受到圍棋里面“金角銀邊草肚皮”思想的啟發(fā)，在進行實占角動作選取時，對每個實占角動作，采取以下評判標準。

（1）穴度：大優(yōu)先；

（2）放入塊的面積：大優(yōu)先；

（3）塊的長邊長：大優(yōu)先；

（4）塊左下頂點的x坐標：小優(yōu)先；

（5）塊左下頂點的y坐標：小優(yōu)先；

（6）塊的方向：躺優(yōu)先。

按照上述評判準則，可唯一地確定一個好的實占角動作。

3.1.2基本穴度算法

基于以上定義，設計A0算法作為二維矩形Packing的基本穴度算法。基本穴度算法描述如下。

算法1基本穴度算法A0

輸入：大矩形框的寬和高；每個小矩形塊的寬和高。

輸出：布局以及面積利用率。

1.初始化動作空間以及實角，初始化實占角動作

2.While存在實占角動作do

3.根據(jù)評判準則，選擇最優(yōu)的實占角動作

4.If大矩形框被小矩形框完全填充

5.保存布局，退出

6.Else

7.更新動作空間以及實角

8.更新實占角動作

9.End while

10.輸出布局以及面積利用率

3.1.3增強穴度算法

A0屬于貪心算法，在當前最優(yōu)的情況下不一定保證總體上達到最優(yōu)。這里對基本穴度算法進行改進，加入搜索過程以提升解的質量。增強穴度算法A1是指從初始格局出發(fā)，每一步考查穴度最大的前N個實占角動作，然后通過向前看并回溯的方法最終選擇一個實占角動作。

對于N值的設定，遵循下列規(guī)則：

N=[當前格局下所有實占角動作的數(shù)目×k%]

若N lowerbound，則N=upperbound。

為避免搜索的范圍過小，對N的取值設定了一個下界；考慮到計算時間，只選擇穴度較大的固定數(shù)量的動作進行回溯。

增強穴度算法描述如下：

算法2增強穴度算法A1

輸入：大矩形框的寬和高；每個小矩形塊的寬和高。

輸出：布局以及面積利用率。

1.初始化動作空間，初始化實角，初始化實占角動作

2.While存在實占角動作do

3.實占角動作排序，選擇前N個最優(yōu)的實占角動作

4.對前N個實占角動作的每一個動作執(zhí)行A0至終止格局，選擇面積利用率最大的實占角動作來做

5.更新動作空間

6.End while

7.輸出布局以及面積利用率

3.2貪心穴度調度算法

3.2.1基本思想和相關概念的定義

在求解子問題矩形Packing問題的增強穴度算法的基礎上設計求解原問題的貪心穴度調度算法。此算法每一步基于某種貪心策略，在選擇當前候選放入塊子集時，優(yōu)先考慮剩余加工時間較長的矩形塊，再利用算法A1對該子集安排盡可能多的矩形塊到框內進行加工，直至某個時刻有至少一個塊加工完成；取出加工完成的塊，在保證未加工完成的塊仍在框內的前提下，重新選擇候選塊子集，并繼續(xù)安排放入盡可能多的矩形塊到框內加工，如此反復，直至所有塊加工完成。每一步安排放入塊至框內的過程稱為一次調度。

定義10（加工區(qū)間）一次調度完成后，從t1時刻開始對安排放入的小矩形塊進行加工，直至某一時刻t2有至少一個矩形塊加工完畢，其對應的時間段[t1,t2)稱為一個加工區(qū)間。

定義11（剩余加工時間）當前時刻某矩形塊尚需的持續(xù)加工時間長度稱為其剩余加工時間，塊在未加工前，其剩余加工時間等于該塊的待加工時間。

下面給出兩種平均剩余加工時間tavg的定義，每一種定義對應一種策略。

定義12（平均剩余加工時間tavg1）考慮當前時刻剩余加工時間大于0的矩形塊集合，設tmax、tmin為該集合中最大、最小剩余加工時間，平均剩余加工時間tavg1定義為tavg1=(tmax+tmin)/2。

定義13（平均剩余加工時間tavg2）僅考慮當前時刻尚未開始加工的框外的矩形塊集合，其平均剩余加工時間tavg2定義為該集合剩余加工時間的平均值。

3.2.2貪心穴度調度算法

三維時空優(yōu)化問題的調度算法是在二維矩形Packing求解算法的基礎上，進行多次調度與加工，直至所有矩形塊加工完畢。

調度時可以考慮時間上的貪心，即優(yōu)先考慮剩余加工時間較長的矩形塊。因為如果加工時間長的矩形塊放到了最后執(zhí)行，則易導致最后的空間有較多的浪費，從而導致時間消耗的上升。但如果僅優(yōu)先考慮剩余加工時間長的矩形塊，可能會導致調度后矩形框的空間利用率不是很理想，最終也會導致時間消耗上升。因此，調度算法需要綜合考慮時間與空間?；谏鲜隹紤]，設計了貪心穴度調度算法（caving-degree based greedy scheduling algorithm，CGSA），該算法有兩種調度類型，分別稱為常規(guī)調度和修正調度。

令LF為所有剩余加工時間大于0的矩形塊集合，令V1為集合LF中剩余加工時間大于等于平均剩余加工時間tavg的矩形塊集合，令V2為集合LF中前一加工區(qū)間內未加工完成的矩形塊集合，令集合V=V1∪V2。

常規(guī)調度使用算法A1，在實占角動作的選取上，對每個實占角動作，優(yōu)先考慮集合V1中的矩形塊，否則依據(jù)評判準則（定義9）選擇塊及放入方位。常規(guī)調度有可能會出現(xiàn)集合V2中的矩形塊不在框內的情況，這時不滿足塊需要連續(xù)加工的要求，稱為一次異常調度。此時需要進行修正調度。

修正調度有兩個處理步驟：

步驟1忽略異常調度的布局，使用算法A1，在實占角動作的選取上，對每個實占角動作，優(yōu)先考慮集合V中的矩形塊，否則依據(jù)評判準則（定義9）選擇塊及放入方位。

步驟2若步驟1仍出現(xiàn)異常調度，則忽略該異常調度的結果，將集合V2中的矩形塊緊湊平移到框的左下角。平移后，更新動作空間，然后在框的未填充區(qū)域進行常規(guī)調度。

貪心穴度調度算法CGSA描述如下：

算法3貪心穴度調度算法CGSA

輸入：大矩形框的寬、高；每個小矩形塊的寬、高與待加工時間。

輸出：每次加工區(qū)間內的布局與總調度長度。

1.初始化所有小矩形塊的剩余加工時間

2.While矩形框外有未加工完的矩形塊do

3.進行常規(guī)調度

4.If出現(xiàn)異常調度

5.進行修正調度

6.保留加工區(qū)間內的布局，對框內小矩形塊進行加工

7.更新未加工完的小矩形塊的剩余加工時間

8.End while

9.輸出每個加工區(qū)間內的布局及總調度長度

常規(guī)調度綜合考慮了時間與空間的因素。若在常規(guī)調度后，集合V2中的矩形塊沒有完全在框內，則進行修正調度。

修正調度只在常規(guī)調度出現(xiàn)異常時使用，其步驟1也綜合考慮了時間與空間的因素，如果步驟1調度不是異常調度，則不執(zhí)行步驟2。修正調度步驟1與常規(guī)調度的唯一區(qū)別是在實占角動作的選取上優(yōu)先考慮集合V，調度后集合V2中的塊都在框內的幾率會大于常規(guī)調度，但是框的利用率也許沒有常規(guī)調度的理想。修正調度的步驟1仍然有可能出現(xiàn)異常調度，比如調度后未將集合V中所有矩形塊放入框中，而集合V中未放入框內的塊恰好有至少一個屬于集合V2。此時需要執(zhí)行步驟2。步驟2沒有將集合V2中的塊拿到框外，可以確保調度的合理性。

作為比較，設計了矩形塊在框內不可隨時間移動的將時間簡單類比為空間的相應問題的調度算法CGSA′。具體過程如下。

算法4貪心穴度調度算法CGSA′

輸入：大矩形框的寬、高；每個小矩形塊的寬、高與待加工時間。

輸出：每次加工區(qū)間內的布局與總調度長度。

1.初始化所有小矩形塊的剩余加工時間

2.While矩形框外有未加工完的矩形塊do

3.在框的未填充區(qū)域進行常規(guī)調度

4.保持加工區(qū)間內的布局，對框內小矩形塊進行加工

5.取出框內加工完成的塊。保留框內未加工完成的塊的放置方位，更新其剩余加工時間

6.更新動作空間

7.End while

8.輸出每個加工區(qū)間內的布局及總調度長度

4　算例設計與運行結果

將貪心穴度調度算法用C++語言編程，并在CPU主頻為2.80 GHz，內存為4 GB的微型計算機上進行計算。對于矩形Packing問題，國際上有公開的代表性算例進行校驗。然而，三維時空優(yōu)化問題，是近年來學術界提出的新問題，目前國際上還沒有公開的算例。因此，如何設計出公平公正并具代表性的算例，是本文首先需要解決的問題。本文共有兩大類算例：第一大類為滿足非閘斷模式的小型算例；第二大類為滿足閘斷模式的自動生成算例。然后對這兩大類算例進行實驗計算和結果分析。

4.1小型算例及其運行結果

本節(jié)設計了4個小型算例，它們的理論最優(yōu)解即最優(yōu)調度長度均為2，但如果退化為相應的Strip Packing問題，其理論最優(yōu)調度長度均為3。表1到表4分別描述了這4個算例中小矩形塊的相應參數(shù)，其中Ri代表小矩形塊，Wi、Hi分別代表小矩形塊的寬、高，Ti代表小矩形塊的待加工時間。

Table 1　Small scale case 1(the shape of rectangle:10×10)表1　小型算例1（框的形狀為10×10）

Table 2　Small scale case 2(the shape of rectangle:10×10) 表2　小型算例2（框的形狀為10×10）

Table 3　Small scale case 3(the shape of rectangle:5×5) 表3　小型算例3（框的形狀為5×5）

Table 4　Small scale case 4(the shape of rectangle:6×6) 表4　小型算例4（框的形狀為6×6）

當取tavg=tavg1時，算法CGSA對這4個算例均計算出了總調度長度為2的最優(yōu)解，而算法CGSA′得到的總調度長度都為3。表5給出了小型算例2在不同加工區(qū)間內的布局。

Table 5　Coordinates of packing layouts for small scale case 2表5　小型算例2的布局坐標

在用算法CGSA測試時，每個算例的每個加工區(qū)間內大矩形框的面積利用率都是100%。圖3～圖6分別給出了這4個測試算例在每個加工區(qū)間內的布局圖。圖中陰影部分為矩形塊在不同加工區(qū)間內持續(xù)加工的位置與方向。

Fig.3　Packing layouts for small scale case 1圖3　小型算例1的布局圖案

Fig.4　Packing layouts for small scale case 2圖4　小型算例2的布局圖案

Fig.5　Packing layouts for small scale case 3圖5　小型算例3的布局圖案

Fig.6　Packing layouts for small scale case 4圖6　小型算例4的布局圖案

4.2自動生成算例及其運行結果

由小型算例的布局圖可知，4個算例在每個單位長度的加工區(qū)間內都保證了空間利用率為100%，最終的布局圖的數(shù)目表明它們均達到了總調度長度為2的最優(yōu)解。由此啟發(fā)在設計自動生成算例時，可針對每個加工區(qū)間自動生成放入塊的尺寸，若在連續(xù)i個加工區(qū)間都包含某個相同尺寸的矩形塊，則可將其視為同一個矩形塊，并將此矩形塊需要連續(xù)加工的時間設為這i個加工區(qū)間長度之和。

以小型算例4為例，如圖6所示，兩個單位長度的加工區(qū)間布局圖表明總調度長度是兩個單位時間。矩形塊4×4在兩個加工區(qū)間中均有出現(xiàn)，則將其視為一個矩形塊且其連續(xù)加工時間為2，其余塊的加工時間設為1。

根據(jù)上述分析，設計算例的自動生成算法。首先將每個加工區(qū)間進行單獨分割，然后合并相鄰加工區(qū)間中尺寸相同的矩形塊，并計算合并后不同矩形塊的待加工時間。

在分割過程中，可能會出現(xiàn)某一層分割后的尺寸很大（接近矩形框的尺寸大?。?，而某一層分割后的矩形塊大部分尺寸都是單位矩形塊（尺寸為1×1），這樣的算例對于問題的研究沒有意義。為了使生成后的算例更具代表性，設定需要生成的小矩形塊的數(shù)目nl=(W+H)/2×(L±1)，設定每個加工區(qū)間內需要切割的矩形塊的數(shù)目n0=nl/L×(1±0.2)，其中W、H為大矩形框的寬、高，L為需要分割的加工區(qū)間個數(shù)，nl與n有關，將分割后nl個小矩形塊中具有相鄰加工區(qū)間且尺寸相同的塊進行合并，得到的值為給定的小矩形塊的數(shù)目n。

算例自動生成算法如下。

算法5算例自動生成算法

輸入：大矩形框的寬和高，需要分割的加工區(qū)間個數(shù)，需要生成的小矩形塊數(shù)目。

輸出:小矩形塊的寬和高以及待加工時間。

1.For每個加工區(qū)間do

2.隨機生成需要分割的小矩形塊的數(shù)目

3.While小矩形塊數(shù)目少于需要分割的數(shù)目do

4.隨機選擇一個該加工區(qū)間已有的矩形塊

5.調用矩形塊分割算法將隨機選擇的矩形塊進行分割

6.儲存分割后生成的小矩形塊

7.End while

8.End for

9.將相鄰加工區(qū)間中尺寸相同的矩形塊視為一個塊，合并其加工時間

10．將所有小矩形塊的順序隨機排列

算法5中調用了矩形塊分割算法，把一個矩形塊隨機分割成兩個小的矩形塊，且兩個小矩形塊的邊長為整數(shù)。矩形塊分割算法描述如下，其中random (U)指從U集合中隨機選擇一個元素輸出。

算法6矩形塊分割算法

輸入：待分割矩形塊的寬和高w、h。

輸出:分割后兩個小矩形塊的寬和高(w1,h1)、(w2,h2)。

1.初始化：w1←w,w2←w,h1←h,h2←h

2.隨機選擇分割寬或高

3.If分割寬

4.w1←random({1,2,…,w-1})

5.w2←w-w1

6.If分割高

7.h1←random({1,2,…,h-1})

8.h2←h-h1

9.輸出(w1,h1)、(w2,h2)

用算法5生成了G21算例集，該算例集共有21種類型算例，且每種類型有10個算例。依據(jù)最優(yōu)調度長度的不同，將G21算例集分為7組，分別為Gi(i=1,2,3,4,5,6,7)，每組算例內的最優(yōu)調度長度相同，分別為i+1(i=1,2,3,4,5,6,7)個單位時間，例如G3算例組中所有算例的最優(yōu)調度長度為3+1=4個單位時間。在統(tǒng)計算例的運行結果時，以算例組為單位。

每組算例包含3種類型，分別為Gi_10、Gi_12、Gi_15，如G2_12表示G2算例組中的第2類算例，該類算例共有10個。表6給出了Gi算例組的特征。

Table 6　Features ofGigroup表6　Gi算例組的特征

G21算例集中的每個矩形塊都有其對應的待加工時間，表7統(tǒng)計了每種類型算例在不同待加工時間中擁有矩形塊的平均數(shù)目。平均數(shù)目是取每種類型算例中10個算例的平均值。

對于算法CGSA，其平均剩余加工時間tavg可以選取tavg1、tavg2，分別對應兩種貪心策略。圖7描述了算法CGSA在G21算例集上不同貪心策略下求得的平均調度長度。平均調度長度是取每個算例組中30個算例求得的總調度長度的平均值。

由結果可知，在測試G21算例集上，算法GCSA 取tavg=tavg1時得到的結果明顯優(yōu)于取tavg=tavg2時的結果，且在運行時間上前者明顯比后者運行時間短。在接下來的測試中，算法CGSA與CGSA′都取tavg=tavg1。

算法CGSA在測試G21算例集時，使用修正調度的概率很低，執(zhí)行修正調度步驟2的概率更低，且如果每次調度都用修正調度，算法得到的總調度長度和運行時間都遠高于使用常規(guī)調度的情況。

Table 7　Average number of rectangles表7　矩形塊的平均數(shù)目統(tǒng)計

Fig.7　Average scheduling length in different greedy strategies for CGSA圖7CGSA在不同貪心策略下的平均調度長度

分別用算法CGSA與CGSA′對G21算例集進行測試，圖8描述了算法CGSA與CGSA′在Gi算例組中達到最優(yōu)解的算例數(shù)。

Fig.8　Number of optimal solutions inGigroup圖8　Gi算例組中達到最優(yōu)解的算例數(shù)

圖9描述了算法CGSA與CGSA′在算例組Gi中所得的平均調度長度。

Fig.9　Average scheduling length for CGSAand CGSA′圖9CGSA與CGSA′的平均調度長度

4.3運行結果分析

對于設計的4個小型算例，貪心穴度調度算法CGSA在測試時均得到了總調度長度為2的最優(yōu)解。若將時間簡單地類比為空間，則問題退化為高方向固定的Strip Packing問題，其最優(yōu)調度長度為3；若限定矩形塊在放入矩形框的時間段內不能移動，則貪心調度的總調度長度也為3。對于自動生成的G21算例集，算法CGSA在測試時均能獲得半數(shù)及半數(shù)以上的最優(yōu)解。當最優(yōu)調度長度分別為2、3、4時，相應算例組中很多算例都能達到最優(yōu)解。當最優(yōu)調度長度由5增加到8，相應算例組中達到最優(yōu)解的算例數(shù)目逐漸減少。對比算法CGSA與CGSA′的測試結果可知，矩形塊在放入矩形框的時間段內可以移動的情況下，貪心調度在每個算例組中得到最優(yōu)解的算例數(shù)明顯多于矩形塊在放入矩形框的時間段內不能移動的情況，且前者得到的總調度長度也短于后者。由此表明，將時間特殊處理時，加強了時空利用的靈活性，提高了矩形框的時間空間利用率。

5　結束語

本文對三維時空優(yōu)化問題的算例和近似求解算法進行了研究，提出了優(yōu)先考慮矩形塊的剩余加工時間的貪心穴度調度算法CGSA。設計了基于問題特點與優(yōu)勢的滿足非閘斷模式和閘斷模式的兩類算例。實驗結果表明，算法CGSA在非閘斷模式算例上均得到了最優(yōu)調度，在多數(shù)非閘斷模式的算例上得到了最優(yōu)調度。在今后的研究中，將生成更高復雜度的代表性算例，進一步改進算法以提高其計算優(yōu)度和效率。

References:

[1]Coffman E G Jr,Garey M R,Johnson D S.An application of bin-packing to multiprocessor scheduling[J].SIAM Journal on Computing,1978,7(1):1-17.

[2]Chekuri C,Khanna S.On multi-dimensional packing problems[C]//Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms,Baltimore,USA,Jan 17-19,1999. Philadelphia,USA:SIAM,1999:185-194.

[3]Wee T S,Magazine M J.Assembly line balancing as generalized bin-packing[J].Operational Research Letters,1982, 1:56-58.

[4]Huang Wenqi,He Kun.Optimal time scheduling on the three-dimensional space packing[J].Journal of Huazhong University of Science and Technology:Natural Science Edition,2010,38(12):102-104.

[5]Huang Wenqi,He Kun.An optimal time scheduling problem on cuboids packing over four-dimensional space-time and its computability proof[J].Chinese Journal of Computer, 2013,36(9):1880-1888.

[6]Huang Wenqi,He Kun.On the weak computability of a four dimensional orthogonal packing and time scheduling problem[J].Theoretical Computer Science,2013,501:1-10.

[7]Michael R G,David S J.Computers and intractability:a guide to the theory of NP-completeness[M].San Francisco, USA:WH Freeman&Co,1979.

[8]Hopper E,Turton B.A genetic algorithm for a 2D industrial packing problem[J].Computers&Industrial Engineering, 1999,37(1):375-378.

[9]Kr?ger B.Guillotineable bin packing:a genetic approach[J]. European Journal of Operational Research,1995,84(3): 645-661.

[10]Bortfeldt A.A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces[J].European Journal of Operational Research,2006,172(3):814-837.

[11]Leung T W,Chan C K,Troutt M D.Application of a mixed simulated annealing-genetic algorithm heuristic for the twodimensional orthogonal packing problem[J].European Journal of Operational Research,2003,145(3):530-542.

[12]Jiang Jiaqian,Liang Youcheng.A hybrid algorithm based on PSO and SA and its application for two-dimensional non-guillotine cutting stock problem[C]//LNCS 3037:Proceedings of the 4th International Conference on Computational Science,Kraków,Poland,Jun 6-9,2004.Berlin,Heidelberg:Springer,2004:666-669.

[13]Dorigo M,Blum C.Ant colony optimization theory:a survey [J].Theoretical Computer Science,2005,344(2):243-278.

[14]Baker B S,Coffman E G Jr,Rivest R L.Orthogonal packings in two dimensions[J].SIAM Journal on Computing,1980,9 (4):846-855.

[15]Chazelle B.The bottomn-left bin-packing heuristic:an efficient implementation[J].IEEE Transactions on Computers, 1983,100(8):697-707.

[16]H opper E.Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods[D].Cardiff: University of Wales,2000.

[17]Cui Yaodong,Yang Yuli,Cheng Xian,et al.A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J].Computers&Operations Research, 2008,35(4):1281-1291.

[18]Huang Wenqi,Liu Jingfa.A deterministic heuristic algorithm based on Euclidian distance for solving the rectangles packing problem[J].Chinese Journal of Computer,2006,29 (5):734-739.

[19]Wu Yuliang,Huang Wenqi,Lau S,et al.An effective quasihuman based heuristic for solving the rectangle packing problem[J].European Journal of Operational Research, 2002,141(2):341-358.

[20]Huang Wenqi,Chen Duanbing,Xu Ruchu.A new heuristic algorithm for rectangle packing[J].Computers&Operations Research,2007,34(11):3270-3280.

[21]Huang Wenqi,Chen Duanbing.An efficient heuristic algorithm for rectangle-packing problem[J].Simulation Modelling Practice and Theory,2007,15(10):1356-1365.

[22]He Kun,Huang Wenqi,Jin Yan.Efficient algorithm based on action space for solving the 2D rectangular packing problem[J].Journal of Software,2012,23(5):1037-1044.

[23]Allen S D,Burke E K,Kendall G.A hybrid placement strategy for the three-dimensional strip packing problem[J].European Journal of Operational Research,2011,209(3):219-227.

附中文參考文獻：

[4]黃文奇,何琨.三維裝箱工作的優(yōu)化調度問題[J].華中科技大學學報:自然科學版,2010,38(12):102-104.

[5]黃文奇,何琨.四維時空高效利用的裝箱調度問題及其可計算性證明[J].計算機學報,2013,36(9):1880-1888.

[18]黃文奇,劉景發(fā).基于歐氏距離的矩形Packing問題的確定性啟發(fā)式求解算法[J].計算機學報,2006,29(5):734-739.

[22]何琨,黃文奇,金燕.基于動作空間求解二維矩形Packing問題的高效算法[J].軟件學報,2012,23(5):1037-1044.

ZHU Peng was born in 1990.He received the M.S.degree in computer science and technology from Huazhong University of Science and Technology in 2015.His research interests include algorithm design and combinatorial optimization,etc.

朱鵬（1990—），男，2015年于華中科技大學計算機科學與技術專業(yè)獲得碩士學位，主要研究領域為算法設計與分析，組合優(yōu)化等。

HE Kun was born in 1972.She is an associate professor and Ph.D.supervisor at School of Computer Science and Technology,Huazhong University of Science and Technology.Her research interests include algorithm design, combinatorial optimization and data mining,etc.

何琨（1972—），女，華中科技大學計算機科學與技術學院副教授、博士生導師，主要研究領域為算法設計與分析，組合優(yōu)化，數(shù)據(jù)挖掘等。

CAO Weigang was born in 1987.He is an M.S.candidate at School of Computer Science and Technology,Huazhong University of Science and Technology.His research interests include algorithm design and combinatorial optimization，etc.

曹偉剛（1987—），男，華中科技大學計算機科學與技術學院碩士研究生，主要研究領域為算法設計與分析，組合優(yōu)化等。

YANG Huan was born in 1992.She is an M.S.candidate at School of Computer Science and Technology,Huazhong University of Science and Technology.Her research interests include algorithm design and combinatorial optimization,etc.

楊歡（1992—），女，華中科技大學計算機科學與技術學院碩士研究生，主要研究領域為算法設計與分析，組合優(yōu)化等。

*The National Natural Science Foundation of China under Grant Nos.61472147,61173180(國家自然科學基金). Received 2015-07,Accepted 2015-11.

CNKI網絡優(yōu)先出版:2015-11-12,http://www.cnki.net/kcms/detail/11.5602.TP.20151112.1658.010.html

文獻標志碼：A

中圖分類號：TP301

doi:10.3778/j.issn.1673-9418.1507045

Caving-Degree Based Greedy SchedulingAlgorithm for Three-Dimensional Space-Time Optimization Problem?

ZHU Peng,HE Kun+,CAO Weigang,YANG Huan
School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China +Corresponding author:E-mail:brooklet60@gmail.com

Abstract:This paper addresses the three-dimensional space-time optimization(3D-STO)problem based on twodimensional rectangular packing problem.Given a large rectangular sheet and a set of rectangular items,each item needs to be continuously processed with a time length on the sheet.The question is how to arrange each item?s loading time and its location and orientation during the processing period,and the goal is to minimize the total utilization time of the sheet,i.e.the makespan of the schedule.Differing from classical packing problems,each item?s location and orientation on the sheet can be changed over time such that the sheet is utilized more fully.Based on the definitions of real corner and real corner action,this paper designs an enhanced caving-degree algorithm for the sub-problem,the twodimensional rectangular packing problem.Then by assigning a higher priority to items with longer remaining processing time at each step,this paper proposes a caving-degree based greedy scheduling algorithm(CGSA)for the 3D-STO. For comparison,this paper also proposes a scheduling algorithm called CGSA′in which each item?s location and orientation on the sheet can?t be changed over time.Four small benchmarks with no guillotine cut constraint presented in the experiments,CGSA achieves optimal solutions whose makespan is 2.But if the experiments regard the time as a space dimension,indicating that the items can?t move over time,the shortest makespan is 3.Further,this paper gener-ates 21 groups with a total of 210 guillotine cut constraint benchmarks.Experiments show that CGSA not only achieves more optimal solutions than CGSA′,but also obtains shorter average scheduling length than CGSA′.

Key words:space-time optimization;greedy scheduling;packing;benchmarks;placement