一種基于動態決策塊的超啟發式跨單元調度方法

田云娜　李冬妮　劉兆赫　鄭丹

一種基于動態決策塊的超啟發式跨單元調度方法

田云娜1，2李冬妮1劉兆赫1鄭丹1

對運輸能力受限條件下的跨單元調度問題進行分析，提出一種基于動態決策塊和蟻群優化（Ant colony optimization，ACO）的超啟發式方法，同時解決跨單元生產調度和運輸調度問題.在傳統超啟發式方法的基礎上，采用動態決策塊策略，通過蟻群算法合理劃分決策塊，并為決策塊選擇合適的規則.實驗表明，采用動態決策塊策略的超啟發式方法比傳統的超啟發式方法具有更好的性能，本文所提的方法在最小化加權延遲總和目標方面有較好的優化能力并且具有較高的計算效率.

動態決策塊，超啟發式，蟻群算法，跨單元調度

引用格式田云娜，李冬妮，劉兆赫，鄭丹.一種基于動態決策塊的超啟發式跨單元調度方法.自動化學報，2016，42（4）: 524?534

單元制造系統（Cellular manufacturing system，CMS）的思想是將成組技術應用在生產制造業領域中，通過構建功能相對獨立的生產單元，將具有相同性質的一批工件集中在單元內加工，這種生產方式有效地降低了運輸時間、響應時間等生產成本［1］.然而在實際生產中，受到市場需求多樣化和生產經濟成本方面的約束，具有復雜工藝的工件需要通過多個單元協作加工，形成了跨單元協作的生產模式，由此產生了跨單元調度問題［2］.

在現有的跨單元問題研究中，由于元啟發式算法具備較強的優化能力，大部分學者采用這種方法解決跨單元調度問題.其中Solimanpur等［3］提出一種嵌套的禁忌搜索算法解決跨單元工件調度問題.Tang等［4］和Tavakkoli-Moghaddam等［5］采用分散搜索算法解決工件在多個單元間的跨單元調度問題.Zeng等［6］采用遺傳算法和局部搜索結合的方法解決單元內工件排序問題，以最小化最大完工時間為啟發式信息，采用輪盤賭方法解決單元間工件分派問題.Elmi等［7］采用模擬退火方法解決跨單元調度問題.Li等［8］采用蟻群優化算方法解決具有柔性路徑的跨單元調度問題.在當前被驗證過的最大問題規模下（60～80個工件/25～40臺機器/6～8個單元），元啟發式算法一般需要耗費數百秒（371s［8］、840s［5］）才能得到調度解.然而，在裝備制造業復雜產品的CMS中，通常有十余個單元、數百個工件、數百臺機器、數千道工序，元啟發式算法將無法承受如此大規模問題的計算壓力，因此從計算效率的角度考慮，不能直接使用元啟發式算法.

在上述跨單元問題的研究中，文獻［3，5］忽略了跨單元轉移時間，文獻［4，6?8］考慮了跨單元轉移時間.但是這些研究都隱含一個假設，即單元間運輸能力充足，工件在單元間運輸無需等待.而在裝備制造業的實際生產中，由于各個單元分布在不同位置，工件具有一定的重量和體積，因此需要由運輸工具完成跨單元轉移，但運輸工具的數量和容量卻有限.因此如何高效地利用有限的運輸工具成為實際生產中的重要問題.本文考慮運輸能力受限的跨單元調度問題，同時處理工序分派、工序排序和小車運輸三個子問題，問題在復雜度和規模兩方面都有所增加，調度算法需要同時滿足優化性能和計算效率兩方面的需求.

在實際生產中，啟發式規則在計算效率方面表現出良好的性能，因其簡單、快捷和易實施的特點而被廣泛應用［9］，特別適用于復雜、具有動態特性的制造環境［10］.但啟發式規則的缺陷在于它對調度環境和調度目標的依賴性較強，沒有哪個規則能在所有情況下都表現出良好的性能［11］，而且選用規則都是根據人為經驗事先指定的，優化能力較差，因此無法滿足復雜調度問題的優化性能需求.

超啟發式算法（Hyper-heuristic）作為一種“搜索啟發式方法”（Heuristics to search heuristics）［12］，相當于將啟發式規則和其他搜索方法或學習機制的優勢相結合，用優化能力較強的算法搜索或產生高效的規則，再用得到的規則求解.在已有的超啟發式算法研究中，遺傳算法被廣泛應用于選擇啟發式規則［13?16］.另外，Li等［17］采用基于蟻群優化算法的超啟發式方法解決混合流水車間調度問題.賈凌云等［18］提出一種基于混合蛙跳算法的超啟發式方法，并通過遺傳規劃產生的規則擴充超啟發式算法的規則集.劉兆赫等［19］提出一種基于離散蜂群算法的超啟發式方法.由于超啟發式算法的搜索對象是啟發式規則而不是問題的解，這樣既避免了人工指定啟發式規則的主觀性，提高了優化能力，同時也縮小了搜索空間，提高了計算效率.

對于生產調度問題而言，超啟發式算法通常是為生產環境中的“實體”（比如工件）搜索底層的啟發式規則，然后對這些實體應用啟發式規則進行調度.本文將超啟發式算法中的決策單位稱為“決策塊”，決策塊的大小決定了為多大范圍的實體選擇同一個啟發式規則.按照決策塊大小為分類標準，可以將超啟發式算法的研究分為兩類.一類是決策塊大小均為1的情況，即為每個實體（機器/工件）選擇一個啟發式規則［13?14，17?18］.另一類是決策塊大小不全為1的情況，即為多個實體選擇同一個啟發式規則，Yang等［20］為每個階段的所有機器選擇一個啟發式規則.V′azquez-Rodr′?guez等［15?16］、劉兆赫等［19］將每次決策看作一個決策點，按時間順序將所有決策點劃分為多個決策塊，為每個決策塊選擇一個啟發式規則.

在上述兩類方法中，決策塊大小會直接影響算法的計算效率和優化性能.當決策塊較小時，能夠考慮到不同實體的狀態特征，更有可能為每個實體選到合適的規則，使得算法的優化性能有保證，但也會因此付出較大的計算開銷，反之亦然.因此，在解決大規模復雜問題時，決策塊的大小成為影響算法計算效率和優化性能的關鍵因素.

在現有的超啟發式算法研究中，決策塊大小一般都是事先指定的［13?15，17?18］，本文稱之為靜態決策塊策略.在這類方法中，決策塊大小在算法的運行過程中是確定不變的，這使算法的適應性受到限制.動態決策塊策略則是通過迭代不斷優化決策塊的大小，動態尋找合理的決策塊劃分方案.在目前的研究中，采用動態決策塊策略的文獻還很少，V′azquez-Rodr′?guez等［16］采用遺傳算法動態優化決策塊大小和啟發式規則序列，解決多目標作業車間調度問題.

基于以上分析，本文設計了一種基于動態決策塊和蟻群優化（Ant colony optimization，ACO）的超啟發式算法（Dynamic decision block and ACO-based hyper-heuristic，DABH）.在傳統超啟發式的框架上加入動態決策塊策略，通過ACO動態構建決策塊并搜索啟發式規則.本文的主要貢獻在于以下兩點：1）動態決策塊策略可以合理地縮小搜索空間，提高算法的計算效率；2）ACO算法作為一種構造型優化方法，通過信息素的引導，動態生成大小合適的決策塊，從而達到優化性能和計算效率之間的平衡.

1　問題模型

本文根據作業車間跨單元調度問題抽象出問題模型，以最小化加權延遲總和（Total weighted tardiness，TWT），為優化調度目標.本文問題模型同時考慮跨單元生產和跨單元運輸的協同.

1.1問題假設

本文研究運輸能力受限的跨單元調度問題假設描述如下：

1）所有工件零時刻到達；

2）每個工件的交貨日期已知；

3）工序在特定機器上的加工時間固定且已知，準備時間獨立于工序次序；

4）每臺機器在同一時刻只能加工一道工序；

5）工序一旦開始，便不允許中斷和搶占；

6）單元間存在加工能力重疊的機器，即工件跨單元加工路徑具有柔性，對于任意一道工序，單元內最多只有一臺可加工的機器；

7）考慮工件的跨單元轉移時間，忽略單元內轉移時間；

8）小車負責運輸由多個工件組成的一個批次，一個批次內的工件可以有不同的目的單元；

9）小車僅裝載本單元內工件，從本單元出發后不在沿途各單元裝載工件；

10）小車按照一定順序訪問目的單元并卸載相應工件，一旦所有工件卸載完畢，小車立即返回所屬單元；

11）忽略小車裝載和卸載工件的時間.

1.2符號列表

與本文問題相關的符號變量定義如下所示.

索引

i：工件索引（i=1，···，N）

j：工件i的工序索引（j=1，···，J（i））

m：機器索引（m=1，···，M）

c：單元及所屬小車索引（c=1，···，C）

b：小車c上批次索引（b=1，···，B（c））

q：第b個批次內工件的運輸順序索引

（q=1，···，Q（b））

系統變量

Oij：工件i的第j道工序

J（i）：工件i的工序總數

pijm：工序Oij在機器m上的加工時間

si：工件i的體積

di：工件i的交貨期

wi：工件i的權重

v：小車的容量

Tcc'：從單元c到單元c'所需要的轉移時間

tij：工序oij完工后所需要的轉移時間

Dij：工序oij完工后轉移的目的單元

sij：工序oij的開始時間

fij：工序oij的完工時間

1.3目標函數及約束條件

本文的調度目標是最小化加權延遲總和.目標函數的數學表達式如式（1）所示.

根據實際生產中的問題特性和約束，本文的約束條件描述如下.

其中，式（2）表示一個工序只能在一個機器上進行加工；式（3）表示一個工序在同一時刻只能被加工一次；式（4）和式（5）分別表示工序的開始加工時間和完工時間；式（6）表示工序只能被分派到具有相應加工能力的機器上；式（7）保證被分派到機器上的工件的順序性；式（8）表示工件的完工時間大于或等于其任意一道工序的完工時間；式（9）表示小車的一個批次只能被運輸一次；式（10）表示一個工件只能被分派到一個小車的一個批次；式（11）表示需要跨單元的工件只能被分派到本單元的小車；式（12）定義小車運輸目標單元；式（13）和式（14）表示任意批次的所有工件只有在小車到達其目的單元才能被卸載；式（15）表示每個批次必須等到批次內所有工件的前一道工序完成才能開始運輸；式（16）表示任意工序只能在其前一道工序完成，并被運輸至目的單元才能開始加工；式（17）表示每個小車運輸完一個批次內所有工件并返回所在單元后才能開始下一批次運輸；式（18）表示所有被分派到同一小車的同一批次的工件體積總和小于或等于小車容量.

2　DABH算法

在運輸能力受限的跨單元調度問題中，需要考慮多個子問題以及它們之間的協同.在解決這一類大規模復雜調度問題時，需要兼顧算法的優化性能和計算效率.DABH在超啟發式的框架上加入動態決策塊策略，通過合理的縮小搜索空間，從而達到提高算法計算效率的目的.同時，DABH采用ACO作為超啟發式算法的高層優化方法，通過信息素的引導動態尋找合理的決策塊劃分方案，并為不同的決策塊選擇合適的啟發式規則，通過得到的啟發式規則進行調度產生完整解.

2.1基于動態決策塊的算法框架

本文問題模型包含三個子問題，其中工序分派為每道工序選擇一臺加工機器；工序排序確定機器緩沖隊列中待加工工件的加工次序；小車運輸包含對工件的組批和路徑決策，組批確定小車每個批次運送哪些工件，路徑決策確定工件的運輸次序. DABH算法解決以上三個問題的流程描述如圖1.

圖1　DABH算法的整體流程圖Fig.1　General algorithm of DABH

在圖1中，所有決策塊大小在初始階段隨機生成，在迭代過程中根據解的優化性能更新部分最優解的信息素，然后根據信息素逐步優化決策塊的大小，使決策塊趨向于更加合理的劃分.同時，根據候選規則的信息素濃度為每個決策塊選擇規則.在調度過程中，每個決策塊內的實體采用相同的規則，生成最終調度解.

2.2基于動態決策塊的編碼

在DABH算法中，每個決策塊的大小代表所包含實體的數量，這里實體指工件、機器和小車，決策塊的大小決定一個啟發式規則所作用的范圍，本節對決策塊以及基于決策塊的編碼進行形式化的描述.

本文將實體集合記為E=｛e1，···，eN｝，其中N表示實體的數量.將啟發式規則集合記為代表工序分派規則集合，代表工序排序規則集合代表小車運輸規則集合.在規則選取過程中，分別從H'、H''、H'''中為工件決策塊、機器決策塊和小車決策塊選取規則，最終得到基于決策塊的規則編碼.

定義 1.將所有實體劃分成若干個決策塊，所有決策塊構成的集合定義為B，B=｛b1，···，bi，···，bL｝，集合中元素須同時滿足兩個條件：S

在定義1中，條件1）表示所有實體都被劃分到各個決策塊中，條件2）表示一個實體不能重復出現在多個決策塊中.

例1.假設在工件分派子問題中有4個工件，這些工件被劃分成兩個決策塊.那么兩個決策塊的大小之和為4，并且決策塊之間沒有重復的工件出現.

定義 2.對于決策塊集合B=｛b1，···，bi，···，bL｝，基于決策塊的規則編碼定義為A=｛a1，···，ai，···，aL｝.

例2.假設測試問題有8個實體，包括2個工件，4臺機器和2個單元，即E=｛e1，···，e8｝，啟發式規則集合

當決策塊大小均為1時，即為每個實體選擇一個規則.如圖2所示，虛框內為基于8個實體的規則編碼A=｛a1，···，ai，···，a8｝，在H中分派、排序和運輸規則分別有2個，那么對應編碼的搜索空間大小為22×24×22.

圖2　決策塊大小均為1的編碼Fig.2　Representation of decision blocks whose size is 1

當決策塊大小不全為1時，即存在為多個實體選擇一個規則的情況.如圖3所示，將8個實體劃分為4個決策塊，即B=｛b1，b2，b3，b4｝.其中b1=｛e1，e2｝，b2=｛e3｝，b3=｛e4，e5，e6｝，b4=｛e7，e8｝，它們分別是1個工件決策塊、2個機器決策塊和1個小車決策塊.

圖3　決策塊大小不全為1的編碼Fig.3　Representation of decision blocks with different sizes

由此可見，當決策塊大小不全為1時，決策塊策略能夠有效縮小搜索空間，在計算效率方面會有所提高.但是當決策塊大小過大時，問題求解空間將過于單一，有可能遺漏掉優質解，導致算法的優化性能受到限制.因此確定合理的決策塊大小，將有利于在提高計算效率的同時保證算法的優化性能.

2.3基于動態決策塊的規則選取

在DABH算法中，通過信息素引導動態生成決策塊，以決策塊為單位選擇啟發式規則，對決策塊內的所有實體應用規則得到調度解.算法根據生成的調度解的優劣更新信息素，從而達到尋優的目標.

2.3.1信息素結構

在構造信息素結構時，DABH包含兩類信息素矩陣，即決策塊劃分矩陣和啟發式規則選擇矩陣.

針對分派、排序、運輸三個子問題，決策塊劃分矩陣分別為工件、機器和小車三個決策塊劃分矩陣.三個矩陣的大小分別為N×D'、M×D''和C×D'''，其中N、M 和C分別表示工件、機器和小車的數量，D'、D''和D'''分別表示工件、機器和小車決策塊大小的上限，上限取值通過參數實驗獲得，在第3.2節中有詳細描述.矩陣中元素τi，p表示第i個決策塊的大小為p的信息素濃度.

同上分析，啟發式規則矩陣分別為工件、機器和小車三個分派規則矩陣.矩陣大小為分別為N×R'、M×R''和C×R'''，其中R'、R''和R'''分別表示分派規則、排序規則和運輸規則的數量.矩陣中元素τi，q表示第i個決策塊選取第q個啟發式規則的信息素濃度.

2.3.2候選規則集

針對三個子問題，候選規則分別對應分派、排序和運輸三種規則.另外，由于工件交貨期（Due date）直接影響TWT，因此在候選排序規則集中加入與交貨期相關的規則，其中包含公認效果顯著的Apparent tardiness cost、Cost over time、Minimum slack、Slack per remaining processing time等規則［9］.

1）候選分派規則

First available（FA）：選擇最先可用機器.

Earliest finish time（EFT）：選擇加工該工序后具有最早完成時間的機器.

Least utilization（LU）：選擇加工該工序后具有最低占用率的機器.

Most available（MA）：選擇當前緩沖區內待加工工件最少的機器.

Shortest processing time（SPT）：選擇加工時間最短的機器.

2）候選排序規則

Shortest processing time（SPT）：選擇具有最短加工時間的工件.

Smallest processing time ratio（SPTR）：選擇具有最小加工時間比率的工件.

Shortest remaining processing time（SRPT）：選擇具有最短剩余加工時間的工件.

Weighted shortest processing time（WSPT）：選擇具有最小加權加工時間的工件.

Time in shop（TIS）：選擇在當前機器緩沖隊列中等待時間最長的工件.

Earliest due date（EDD）：選擇具有最早交貨期的工件.

Weighted earliest due date（WEDD）：選擇具有最小加權交貨期的工件.

Minimum slack（MS）：選擇具有最小松弛時間的工件.

Apparent tardiness cost（ATC）：選擇ATC值最大的工件，具體計算見式（19）.

Cost over time（COVERT）：選擇COVERT值最大的工件，具體計算見式（20）.

Slackperremainingprocessingtime（S/RPT）：選擇S/RPT值最小的工件，具體計算見式（21）.

3）候選運輸規則

Earliest due date（EDD）：選擇具有最早交貨期的工件.

Shortest processing time（SPT）：選擇具有最短加工時間的工件.

Smallest processing time ratio（SPTR）：選擇具有最小加工時間比率的工件.

Shortest remaining processing time（SRPT）：選擇具有最短剩余加工時間的工件.

Weighted earliest due date（WEDD）：選擇具有最小加權交貨期的工件.

Weighted shortest processing time（WSPT）：選擇具有最小加權加工時間的工件.

Time in shop（TIS）：選擇當前機器緩沖隊列中等待時間最長的工件.

2.3.3確定決策塊大小和規則

在DABH算法中，采用ACO算法來確定決策塊的大小，并為每個決策塊選取規則.每只螞蟻通過信息素濃度計算選擇決策塊大小和啟發式規則的概率.

1）當螞蟻選擇決策塊大小時，第i個決策塊的大小為p的概率由式（22）計算可得.

其中，τip表示第i個決策塊的大小為i的信息素濃度.D表示決策塊大小的上限，當選擇工件決策塊大小時，D為D'；當選擇機器決策塊大小時，D為D''；當選擇小車決策塊大小時，D為D'''.

2）當螞蟻選擇啟發式規則時，第i個決策塊選取第q個啟發式規則的概率由式（23）計算可得.

其中，τiq表示第i個決策塊的選取第q個啟發式規則的信息素濃度.R表示啟發式規則的數量，為工件決策塊選擇規則時，R為R'；為機器決策塊選擇規則時，R為R''；為小車決策塊選擇規則時，R為

R'''.

2.3.4信息素更新

本文采用最大最小螞蟻系統（Max-min ant system，MMAS）的信息素更新方法，更新信息素的值限定在區間［τmin，τmax］內，τmin取值為0.1，τmax取值為5.在每次循環中，所有螞蟻均完成調度解的構造后進行信息素更新，參與更新的僅為本次循環中的σ個最優解.這種方法既能使蟻群搜索的范圍集中在較優解附近，又不會因使用循環中的單個最優解或全局最優解更新信息素而使收斂速度過慢［21］.

信息素更新規則如下：

1）決策塊大小信息素更新規則.若第i'個決策塊大小確定為k，則決策塊劃分矩陣中的元素τi'k根據式（24）進行更新.

2）啟發式規則的信息素更新規則.若第i'個決策塊選擇第l個分派規則，則啟發式規則選擇矩陣中的元素τi'l根據式（25）進行更新.

在式（24）和（25）中，?τ=Q/Score，Q為信息素更新量影響因子，Score為更新信息素的調度解對應的目標函數值.

2.4基于動態決策塊的解碼

DABH算法通過ACO算法為決策塊選擇啟發式規則，得到一組規則編碼序列，系統將其轉換成具體的調度解，即解碼過程.解碼算法描述如下：

步驟1.參數初始化，置離散事件模擬器（Discrete event simulation，DES）時鐘t=0.

步驟2.分別把排序規則分配至各機器，分派規則分配至各工件，運輸規則分配至各單元小車.

步驟3.如果所有工件都已完工，轉步驟11.

步驟4.對于可分派工件，若存在單元間柔性路徑，則根據分派規則選擇加工機器，更新被選機器的緩沖隊列；否則，說明其下一道工序的加工機器是確定的，直接分派到該機器的緩沖隊列上.

步驟5.如果單元c的小車是空閑可用的且有要運輸的工件，則轉步驟6；否則，轉步驟7.

步驟6.根據運輸規則計算單元c中待運輸工件的優先級，在不超過小車容量的情況下根據優先級進行組批并確定小車的運輸路徑.

步驟7.如果機器m變空閑，則轉步驟8；否則，轉步驟10.

步驟8.根據排序規則調度一個工件.

步驟9.記錄該工件調度工序的開工時間，完工時間和對應的加工機器.

步驟10.t=t+1，轉到步驟3.

步驟11.利用步驟9的記錄信息，根據式（1）計算相應的目標函數值TWT.算法結束.

3　實驗與分析

為了驗證DABH算法的優化性能和計算效率，本文進行了多組對比實驗，仿真實驗采用JAVA語言實現，運行在3.10GHz Core i5-2400 CPU，4GB RAM的PC機上.

3.1實驗設計

在運輸能力受限的跨單元調度問題研究中，目前尚沒有相關的Benchmark，因此設計了不同規模下的多組測試用例.測試用例的性能評價指標為目標函數值TWT，按照式（1）計算可得，與TWT相關的工件交貨期di按式（26）進行計算.

其中ri是工件i的到達時間，由于本文問題假設所有工件零時刻到達，因此是工件i在可選機器上的平均加工時間pij的總和，k為交貨期因子，表示交貨期的緊急程度，默認取值為6.

實驗包括20個不同大小的規模，機器和工件相關屬性的取值如表1所示.每個規模下根據表1的參數隨機產生10個不同測試用例，對每個不同的測試用例進行5次獨立的仿真實驗.每個測試問題采用pn1mn2cn3的記法，表示該測試問題中包含n1個工件、n2臺機器和n3個單元.

表1　生成算例屬性值Table 1　Attributes for generating test problems

為了驗證算法的有效性，實驗分別在不同問題規模下獲取多個測試用例的目標函數TWT的平均值，通過DABH方法與其他方法之間的Gap值進行對比分析.

3.2參數分析

本文參數設計采用全因子設計方法［22］，使用ANOVA（Analysis of variance）方法從單因子效應和雙因子交互作用兩個方面進行分析，觀測多個因素對算法優化目標TWT的影響，從而確定算法最優參數的設置.

由于DABH采用ACO算法搜索規則，因此信息素揮發因子ρ、信息素更新量影響因子Q和信息素濃度最大值τmax等參數會對算法的優化性能有所影響.由于信息素更新量與Q直接相關，在若干次迭代更新后優質解路徑上的信息素濃度將達到τmax，因此將Q/τmax作為實驗參數，其中τmax取值為5，ρ和Q/τmax的參數取值分4個級別，如表2所示.

表2　DABH參數Table 2　Parameters in DABH

本文以最小化TWT為優化目標值，圖4展示了單因子主效應.由于影響算法性能包含兩個因子，因此還需要分析因子之間的交互作用，圖5展示了雙因子的交互影響.從圖4和圖5可看出，當ρ=0.01，Q/τmax=0.05時，DABH都具有最優解性能.

圖4　最小化TWT目標下的單因子主效應圖Fig.4　Influence of each factor with respect to minimizing TWT

圖5　最小化TWT目標下的雙因子交互作用圖Fig.5　Influence of 2-factor interaction with respect to minimizing TWT

在決策塊大小上限的參數實驗中，工件、機器和小車決策塊數量的上限D'、D''、D'''分別根據三種實體數量的百分比｛10%，20%，···，100%｝進行取值，測試10種不同規格的參數設置，最終效果最好的上限參數為100%，因此D'、D''、D'''分別被設為三種實體的數量.

3.3與基于靜態決策塊的方法比較

為了檢驗DABH算法中動態決策塊劃分策略的有效性，本節對比實驗基于采用DABH的算法框架，將動態決策塊劃分策略與三種不同的靜態決策塊劃分策略進行比較.為了保證實驗的公平性，三組對比實驗采取相同的運行時間作為終止條件.

1）每個決策塊的范圍是調度中的一個實體

在調度中每個決策塊包含一個實體，將這種方法記為DABH-ONE.

實驗按照式（27）計算DABH與DABH-ONE之間的Gap值，記為GapONE.由于計算方法類似，在后續的對比實驗中，DABH與其它算法之間的Gap值計算方法均參考式（27）.

其中，scoreONE和scoreDABH分別代表決策塊大小均為1的方法和DABH的目標函數值.

實驗結果如表3所示，在不同規模的測試問題下，DABH均優于DABH-ONE的優化性能，Gap平均值為11.5%.這組實驗表明，隨著問題規模增大，實體的數量增多，DABH-ONE的解編碼長度也增大，因此搜索空間變大.而DABH根據問題規模將所有實體劃分為若干個決策塊，每個決策塊最少包含一個實體，決策塊的數量小于或等于實體的數量，相應的解編碼長度減少，從而適當地縮小了搜索空間.由此可見，DABH-ONE雖然能關注每個實體的狀態，但由于搜索空間過大，使得在相同條件下前者的計算能力下降，所以綜合求解能力與DABH相比較差.

2）每個決策塊的范圍是調度中的一類實體

在調度中每個決策塊包含一類實體，將這種方法記為DABH-ALL.本文的問題針對工件、機器和小車三類實體.DABH與DABH-ALL之間的Gap值記為GapALL.如表3所示，DABH相比于DABH-ALL在平均性能上提升了26.8%.實驗表明，DABH-ALL過度縮小了搜索空間，使解的多樣性受到限制，從而影響解的質量.而DABH通過動態尋找合理的決策塊劃分方案，既保留了解的多樣性，又使得計算時間處于合理的范圍.

3）每個決策塊的范圍是調度中的多個實體

為了避免決策塊過大或過小，本節針對1）和2）提出的決策塊劃分方案，將決策塊的大小設置為決策塊候選取值的中間值，記為DABH-AVG.DABH與DABH-AVG之間的Gap值記為GapAVG.如表3所示，DABH相比于DABH-AVG在平均性能上提升了14.2%.為了直觀地進行對比，將DABH與三種策略對比的Gap值繪制成折線圖，如圖6所示.

圖6　DABH與不同決策塊劃分策略之間的Gap比較Fig.6　Gap values between DABH and different decision block strategies

結合表3與圖6分析發現，從平均性能來看，DABH-AVG處于中間的位置，這主要與DABHAVG的決策塊大小適中有關.從圖6可以看出，當問題規模較小時，DABH-ALL的相對性能最差，當問題規模較大時，DABH-ONE的性能最差，而DABH-AVG的表現相對平穩.

表3　DABH與靜態決策塊劃分策略的性能比較Table 3　Comparison between DABH and static decision block strategies

綜合實驗1）～3）進行分析，決策塊大小過小或過大都會影響算法的計算效率和優化性能，即使DABH-AVG的決策塊大小適中，但由于決策塊大小確定不變，因此性能也會受到影響.而DABH在每次迭代中根據信息素引導更新決策塊大小，然后為每個決策塊選擇合適有效的啟發式規則.這樣不但在一定程度上減少了搜索空間，而且尋優能力也得到了保障.通過本節的實驗可看出，動態決策塊策略相比與靜態決策塊策略體現出多方面的優勢.

3.4與基于動態決策塊的方法比較

在現有的研究中，V′azquez-Rodr′?guez等［16］采用基于動態決策塊和GA的超啟發式方法（Dynamic decision block GA-based hyper-heuristic），以解決作業車間調度問題，本文將其稱作DGBH. DGBH針對調度中的決策，將所有決策劃分為若干個大小不等的決策塊.而DABH是將所有實體劃分為多個決策塊.本節將進行DABH與DGBH的對比實驗.

為了保證實驗的公平性，對比實驗采用相同的問題模型和候選規則集，種群數目為100，終止條件為DGBH算法運行200代所需要的時間.

本實驗DABH與DGBH之間Gap值記為GapDGBH.實驗結果如表4所示，在不同問題規模下，DABH在TWT性能方面平均提升了5.0%.在收斂性方面，圖7展示了在問題規模p40m25下兩種方法運行200代的收斂情況.

表4　DABH與DGBH的性能比較Table 4　Comparison between DABH and DGBH

圖7　DABH與DGBH的收斂過程比較Fig.7　Evolutionary processes of DABH and DGBH

從圖7中可以看出，DABH在第80代之后趨于穩定，DGBH在第150代后趨于穩定，DABH的收斂速度快于DGBH方法，體現出DABH在尋優能力方面上的優勢.

分析實驗結果，DGBH主要存在兩方面局限性.一方面，DGBH的決策塊編碼中每位數字代表一個決策塊的大小，所有基因位上的數值總和應與決策總數相等.然而在編碼交叉變換時，DGBH通過對兩條父代染色體上隨機位置上的編碼進行交叉變換產生子代染色體，這可能會產生基因位上的數值總和小于或大于決策總數的情況，需要通過若干次加1或減1的調整獲得可行解，這個過程不但破壞了父代的優秀的遺傳信息，而且降低了計算效率.另一方面，在突變過程中，DGBH的決策塊編碼隨機選擇兩個元素交換，啟發式規則編碼則是采取單點變換，解的多樣性受到限制.相比而言，DABH編碼是通過信息素引導生成，能更好地處理動態決策塊大小的不確定性.在每次迭代過程中，所有螞蟻根據信息素重新構建決策塊及啟發式規則，增加了解的多樣性，保證了算法的尋優能力.由此可見，ACO算法在動態決策塊劃分方面具有一定優勢.

4　結論

本文針對運輸能力受限的跨單元調度問題的特點，從實際應用的要求出發，提出一種基于動態決策塊的超啟發式方法，解決運輸能力受限的跨單元調度問題.在該方法中，決策塊的組成和大小通過迭代優化產生，將傳統方法中為每個實體或所有實體選擇一個規則的形式轉化為為每個決策塊選擇一個規則，從而獲得計算效率和優化能力之間的平衡.實驗結果表明，與靜態決策塊相比，動態決策塊能夠產生更合適的搜索空間，既節省了計算時間，又保留了合適的多樣性.與基于動態決策塊的超啟發式方法相比，ACO比GA具有更好的性能.這種差異的原因在于，構造型算法與改進型算法相比，能更好地處理動態決策塊大小的不確定性，而改進型算法則需要用更多的操作來處理進化過程中的不可行解.由此可見，DABH同時兼備計算效率和優化性能的優勢，因此非常適合在實際應用中解決規模大、復雜性高的跨單元調度問題.

考慮到不同的實體具有不同的屬性，在今后的工作中可以考慮根據實體之間的相關性劃分決策塊，使決策塊的劃分過程與問題的特性相互適應，從而提升算法的性能.

References

1 Wemmerlov U，Johnson D J.Cellular manufacturing at 46 user plants:implementation experiences and performance improvements.International Journal of Production Research，1997，35（1）:29?49

2 Garza O，Smunt T L.Countering the negative impact of intercell flow in cellular manufacturing.Journal of Operations Management，1991，10（1）:92?118

3 Solimanpur M，Elmi A.A tabu search approach for cell scheduling problem with makespan criterion.International Journal of Production Economics，2013，141（2）:639?645

4 Tang J，Wang X，Kaku I，Yung K L.Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach.Journal of Intelligent Manufacturing，2009，21（4）:525?537

5 Tavakkoli-MoghaddamR，JavadianN，KhorramiA，Gholipour-Kanani Y.Design of a scatter search method for a novel multi-criteria group scheduling problem in a cellularmanufacturing system.Expert Systems with Applications，2010，37（3）:2661?2669

6 Zeng C K，Tang J F，Yan C J.Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles. Journal of Intelligent Manufacturing，2015，26（5）:845?859

7 Elmi A，Solimanpur M，Topaloglu S，Elmi A.A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts.Computers& Industrial Engineering，2011，61（1）:171?178

8 Li D N，Wang Y，Xiao G X，Tang J F.Dynamic parts scheduling in multiple job shop cells considering intercell moves and flexible routes.Computers&Operations Research，2013，40（5）:1207?1223

9 Vepsalainen A P J，Morton T E.Priority rules for job shops with weighted tardiness costs.Management Science，1987，33（8）:1035?1047

10 Ruiz R，V′azquez-Rodr′?guez J A.The hybrid flow shop scheduling problem.European Journal of Operational Research，2010，205（1）:1?18

11 Park S C，Raman N，Shaw M J.Adaptive scheduling in dynamic flexible manufacturing systems:a dynamic rule selection approach.IEEE Transactions on Robotics and Automation，1997，13（4）:486?502

12 Burke E K，Gendreau M，Hyde M，Kendall G，Ochoa G，zcan E，Qu R.Hyper-heuristics:a survey of the state of the art.Journal of the Operational Research Society，2013，64（12）:1695?1724

13 Huang J，S¨uer G A.A dispatching rule-based genetic algorithm for multi-objective job shop scheduling using fuzzy satisfaction levels.Computers&Industrial Engineering，2015，86:29?42

14 Zhang R，Song S J，Wu C.A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem.The International Journal of Advanced Manufacturing Technology，2013，67（1?4）:5?17

15 V′azquez-Rodr′?guez J A，Petrovic S，Salhi A.An investigation of hyper-heuristic search spaces.In:Proceeding of the 2007 IEEE Congress on Evolutionary Computation.Singapore:IEEE，2007.3776?3783

16 V′azquez-Rodr′?guez J A，Petrovic S.A new dispatching rule based genetic algorithm for the multi-objective job shop problem.Journal of Heuristics，2010，16（6）:771?793

17 Li D N，Li M，Meng X W，Tian Y N.A hyperheuristic approach for intercell scheduling with single processing machines and batch processing machines.IEEE Transactions on Systems，Man，and Cybernetics:Systems，2015，45（2）: 315?325

18 Jia Ling-Yun，Li Dong-Ni，Tian Yun-Na.An Intercell scheduling approach using shuffled frog leaping algorithm and genetic programming.Acta Automatica Sinica，2015，41（5）:936?948（賈凌云，李冬妮，田云娜.基于混合蛙跳和遺傳規劃的跨單元調度方法.自動化學報，2015，41（5）:936?948）

19 Liu Zhao-He，Li Dong-Ni，Wang Le-Heng，Tian Yun-Na. An inter-cell scheduling approach considering transportation capacity constraints.Acta Automatica Sinica，2015，41（5）:885?898（劉兆赫，李冬妮，王樂衡，田云娜.考慮運輸能力限制的跨單元調度方法.自動化學報，2015，41（5）:885?898）

20 Yang T，Kuo Y，Cho C.A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem.European Journal of Operational Research，2007，176（3）:1859?1873

21 Huang K L，Liao C J.Ant colony optimization combined with taboo search for the job shop scheduling problem.Computers&Operations Research，2008，35（4）:1030?1046

22 Montgomery D C.Design and Analysis of Experiments（6th Edition）.New York:John Wiley&Sons，2005.

田云娜北京理工大學計算機學院智能信息技術北京市重點實驗室博士研究生，延安大學數學與計算機科學學院講師.主要研究方向為進化計算與智能優化方法.E-mail:ydtianyunna@163.com

（TIAN Yun-NaPh.D.candidate at the Beijing Key Laboratory of Intelligent Information Technology，School of Computer Science，Beijing Institute of Technology and lecturer at the College of Mathematics and Computer Science，Yan'an University.Her research interest covers evolutionary computation and intelligent optimization approaches.）

李冬妮北京理工大學計算機學院智能信息技術北京市重點實驗室副教授.主要研究方向為智能優化方法及其在制造業的應用.本文通信作者.E-mail:ldn@bit.edu.cn

（LI Dong-NiAssociate professor at the Beijing Key Laboratory of Intelligent Information Technology，School of Computer Science，Beijing Institute of Technology.Her research interest covers intelligent optimization approaches and their applications to the manufacturing industry.Corresponding author of this paper.）

劉兆赫北京理工大學計算機學院智能信息技術北京市重點實驗室碩士研究生.主要研究方向為進化計算和生產調度.E-mail:719042341@qq.com

（LIU Zhao-HeMaster student at the Beijing Key Laboratory of Intelligent Information Technology，School of Computer Science，Beijing Institute of Technology.His research interest covers evolutionary computation and production scheduling.）

鄭 丹北京理工大學計算機學院智能信息技術北京市重點實驗室碩士研究生.主要研究方向為進化計算和生產調度.E-mail:zhengdan04@163.com

（ZHENG DanMaster student at the Beijing Key Laboratory of Intelligent Information Technology，School of Computer Science，Beijing Institute of Technology.Her research interest covers evolutionary computation and production scheduling.）

A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling

TIAN Yun-Na1，2LI Dong-Ni1LIU Zhao-He1ZHENG Dan1

In this paper，the inter-cell scheduling problem with a transportation capacity constraint is analyzed.An ant colony optimization（ACO）-based hyper-heuristic with dynamic decision blocks is proposed，which selects appropriate heuristic rules for production and transportation simultaneously.On the basis of traditional hyper-heuristics，a dynamic decision block strategy is proposed，in which several entities are grouped into a decision block under the guidance of pheromones，and appropriate heuristic rules are selected for each decision block.Comparisons between the proposed method and other hyper-heuristics with different decision block strategies are conducted.Computational results show a satisfying performance of the proposed method in minimizing total weighted tardiness with less computational costs.

Dynamic decision block，hyper-heuristic，ant colony optimization（ACO），inter-cell scheduling

Manuscript June 25，2015；accepted December 28，2015

10.16383/j.aas.2016.c150402

Tian Yun-Na，Li Dong-Ni，Liu Zhao-He，Zheng Dan.A hyper-heuristic approach with dynamic decision blocks for inter-cell scheduling.Acta Automatica Sinica，2016，42（4）:524?534

2015-06-25錄用日期2015-12-28

國家自然科學基金（71401014）資助

Supported by National Natural Science Foundation of China（71401014）

本文責任編委趙千川

Recommended by Associate Editor ZHAO Qian-Chuan

1.北京理工大學計算機學院智能信息技術北京市重點實驗室 北京1000812.延安大學數學與計算機科學學院延安716000

1.Beijing Key Laboratory of Intelligent Information Technology，School of Computer Science，Beijing Institute of Technology，Beijing 1000812.College of Mathematics and Computer Science，Yan'an University，Yan'an 716000