一種基于動(dòng)態(tài)決策塊的超啟發(fā)式跨單元調(diào)度方法

田云娜　李冬妮　劉兆赫　鄭丹

一種基于動(dòng)態(tài)決策塊的超啟發(fā)式跨單元調(diào)度方法

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

對(duì)運(yùn)輸能力受限條件下的跨單元調(diào)度問(wèn)題進(jìn)行分析，提出一種基于動(dòng)態(tài)決策塊和蟻群優(yōu)化（Ant colony optimization，ACO）的超啟發(fā)式方法，同時(shí)解決跨單元生產(chǎn)調(diào)度和運(yùn)輸調(diào)度問(wèn)題.在傳統(tǒng)超啟發(fā)式方法的基礎(chǔ)上，采用動(dòng)態(tài)決策塊策略，通過(guò)蟻群算法合理劃分決策塊，并為決策塊選擇合適的規(guī)則.實(shí)驗(yàn)表明，采用動(dòng)態(tài)決策塊策略的超啟發(fā)式方法比傳統(tǒng)的超啟發(fā)式方法具有更好的性能，本文所提的方法在最小化加權(quán)延遲總和目標(biāo)方面有較好的優(yōu)化能力并且具有較高的計(jì)算效率.

動(dòng)態(tài)決策塊，超啟發(fā)式，蟻群算法，跨單元調(diào)度

引用格式田云娜，李冬妮，劉兆赫，鄭丹.一種基于動(dòng)態(tài)決策塊的超啟發(fā)式跨單元調(diào)度方法.自動(dòng)化學(xué)報(bào)，2016，42（4）: 524?534

單元制造系統(tǒng)（Cellular manufacturing system，CMS）的思想是將成組技術(shù)應(yīng)用在生產(chǎn)制造業(yè)領(lǐng)域中，通過(guò)構(gòu)建功能相對(duì)獨(dú)立的生產(chǎn)單元，將具有相同性質(zhì)的一批工件集中在單元內(nèi)加工，這種生產(chǎn)方式有效地降低了運(yùn)輸時(shí)間、響應(yīng)時(shí)間等生產(chǎn)成本［1］.然而在實(shí)際生產(chǎn)中，受到市場(chǎng)需求多樣化和生產(chǎn)經(jīng)濟(jì)成本方面的約束，具有復(fù)雜工藝的工件需要通過(guò)多個(gè)單元協(xié)作加工，形成了跨單元協(xié)作的生產(chǎn)模式，由此產(chǎn)生了跨單元調(diào)度問(wèn)題［2］.

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

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

在實(shí)際生產(chǎn)中，啟發(fā)式規(guī)則在計(jì)算效率方面表現(xiàn)出良好的性能，因其簡(jiǎn)單、快捷和易實(shí)施的特點(diǎn)而被廣泛應(yīng)用［9］，特別適用于復(fù)雜、具有動(dòng)態(tài)特性的制造環(huán)境［10］.但啟發(fā)式規(guī)則的缺陷在于它對(duì)調(diào)度環(huán)境和調(diào)度目標(biāo)的依賴(lài)性較強(qiáng)，沒(méi)有哪個(gè)規(guī)則能在所有情況下都表現(xiàn)出良好的性能［11］，而且選用規(guī)則都是根據(jù)人為經(jīng)驗(yàn)事先指定的，優(yōu)化能力較差，因此無(wú)法滿(mǎn)足復(fù)雜調(diào)度問(wèn)題的優(yōu)化性能需求.

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

對(duì)于生產(chǎn)調(diào)度問(wèn)題而言，超啟發(fā)式算法通常是為生產(chǎn)環(huán)境中的“實(shí)體”（比如工件）搜索底層的啟發(fā)式規(guī)則，然后對(duì)這些實(shí)體應(yīng)用啟發(fā)式規(guī)則進(jìn)行調(diào)度.本文將超啟發(fā)式算法中的決策單位稱(chēng)為“決策塊”，決策塊的大小決定了為多大范圍的實(shí)體選擇同一個(gè)啟發(fā)式規(guī)則.按照決策塊大小為分類(lèi)標(biāo)準(zhǔn)，可以將超啟發(fā)式算法的研究分為兩類(lèi).一類(lèi)是決策塊大小均為1的情況，即為每個(gè)實(shí)體（機(jī)器/工件）選擇一個(gè)啟發(fā)式規(guī)則［13?14，17?18］.另一類(lèi)是決策塊大小不全為1的情況，即為多個(gè)實(shí)體選擇同一個(gè)啟發(fā)式規(guī)則，Yang等［20］為每個(gè)階段的所有機(jī)器選擇一個(gè)啟發(fā)式規(guī)則.V′azquez-Rodr′?guez等［15?16］、劉兆赫等［19］將每次決策看作一個(gè)決策點(diǎn)，按時(shí)間順序?qū)⑺袥Q策點(diǎn)劃分為多個(gè)決策塊，為每個(gè)決策塊選擇一個(gè)啟發(fā)式規(guī)則.

在上述兩類(lèi)方法中，決策塊大小會(huì)直接影響算法的計(jì)算效率和優(yōu)化性能.當(dāng)決策塊較小時(shí)，能夠考慮到不同實(shí)體的狀態(tài)特征，更有可能為每個(gè)實(shí)體選到合適的規(guī)則，使得算法的優(yōu)化性能有保證，但也會(huì)因此付出較大的計(jì)算開(kāi)銷(xiāo)，反之亦然.因此，在解決大規(guī)模復(fù)雜問(wèn)題時(shí)，決策塊的大小成為影響算法計(jì)算效率和優(yōu)化性能的關(guān)鍵因素.

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

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

1　問(wèn)題模型

本文根據(jù)作業(yè)車(chē)間跨單元調(diào)度問(wèn)題抽象出問(wèn)題模型，以最小化加權(quán)延遲總和（Total weighted tardiness，TWT），為優(yōu)化調(diào)度目標(biāo).本文問(wèn)題模型同時(shí)考慮跨單元生產(chǎn)和跨單元運(yùn)輸?shù)膮f(xié)同.

1.1問(wèn)題假設(shè)

本文研究運(yùn)輸能力受限的跨單元調(diào)度問(wèn)題假設(shè)描述如下：

1）所有工件零時(shí)刻到達(dá)；

2）每個(gè)工件的交貨日期已知；

3）工序在特定機(jī)器上的加工時(shí)間固定且已知，準(zhǔn)備時(shí)間獨(dú)立于工序次序；

4）每臺(tái)機(jī)器在同一時(shí)刻只能加工一道工序；

5）工序一旦開(kāi)始，便不允許中斷和搶占；

6）單元間存在加工能力重疊的機(jī)器，即工件跨單元加工路徑具有柔性，對(duì)于任意一道工序，單元內(nèi)最多只有一臺(tái)可加工的機(jī)器；

7）考慮工件的跨單元轉(zhuǎn)移時(shí)間，忽略單元內(nèi)轉(zhuǎn)移時(shí)間；

8）小車(chē)負(fù)責(zé)運(yùn)輸由多個(gè)工件組成的一個(gè)批次，一個(gè)批次內(nèi)的工件可以有不同的目的單元；

9）小車(chē)僅裝載本單元內(nèi)工件，從本單元出發(fā)后不在沿途各單元裝載工件；

10）小車(chē)按照一定順序訪(fǎng)問(wèn)目的單元并卸載相應(yīng)工件，一旦所有工件卸載完畢，小車(chē)立即返回所屬單元；

11）忽略小車(chē)裝載和卸載工件的時(shí)間.

1.2符號(hào)列表

與本文問(wèn)題相關(guān)的符號(hào)變量定義如下所示.

索引

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

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

m：機(jī)器索引（m=1，···，M）

c：?jiǎn)卧八鶎傩≤?chē)索引（c=1，···，C）

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

q：第b個(gè)批次內(nèi)工件的運(yùn)輸順序索引

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

系統(tǒng)變量

Oij：工件i的第j道工序

J（i）：工件i的工序總數(shù)

pijm：工序Oij在機(jī)器m上的加工時(shí)間

si：工件i的體積

di：工件i的交貨期

wi：工件i的權(quán)重

v：小車(chē)的容量

Tcc'：從單元c到單元c'所需要的轉(zhuǎn)移時(shí)間

tij：工序oij完工后所需要的轉(zhuǎn)移時(shí)間

Dij：工序oij完工后轉(zhuǎn)移的目的單元

sij：工序oij的開(kāi)始時(shí)間

fij：工序oij的完工時(shí)間

1.3目標(biāo)函數(shù)及約束條件

本文的調(diào)度目標(biāo)是最小化加權(quán)延遲總和.目標(biāo)函數(shù)的數(shù)學(xué)表達(dá)式如式（1）所示.

根據(jù)實(shí)際生產(chǎn)中的問(wèn)題特性和約束，本文的約束條件描述如下.

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

2　DABH算法

在運(yùn)輸能力受限的跨單元調(diào)度問(wèn)題中，需要考慮多個(gè)子問(wèn)題以及它們之間的協(xié)同.在解決這一類(lèi)大規(guī)模復(fù)雜調(diào)度問(wèn)題時(shí)，需要兼顧算法的優(yōu)化性能和計(jì)算效率.DABH在超啟發(fā)式的框架上加入動(dòng)態(tài)決策塊策略，通過(guò)合理的縮小搜索空間，從而達(dá)到提高算法計(jì)算效率的目的.同時(shí)，DABH采用ACO作為超啟發(fā)式算法的高層優(yōu)化方法，通過(guò)信息素的引導(dǎo)動(dòng)態(tài)尋找合理的決策塊劃分方案，并為不同的決策塊選擇合適的啟發(fā)式規(guī)則，通過(guò)得到的啟發(fā)式規(guī)則進(jìn)行調(diào)度產(chǎn)生完整解.

2.1基于動(dòng)態(tài)決策塊的算法框架

本文問(wèn)題模型包含三個(gè)子問(wèn)題，其中工序分派為每道工序選擇一臺(tái)加工機(jī)器；工序排序確定機(jī)器緩沖隊(duì)列中待加工工件的加工次序；小車(chē)運(yùn)輸包含對(duì)工件的組批和路徑?jīng)Q策，組批確定小車(chē)每個(gè)批次運(yùn)送哪些工件，路徑?jīng)Q策確定工件的運(yùn)輸次序. DABH算法解決以上三個(gè)問(wèn)題的流程描述如圖1.

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

在圖1中，所有決策塊大小在初始階段隨機(jī)生成，在迭代過(guò)程中根據(jù)解的優(yōu)化性能更新部分最優(yōu)解的信息素，然后根據(jù)信息素逐步優(yōu)化決策塊的大小，使決策塊趨向于更加合理的劃分.同時(shí)，根據(jù)候選規(guī)則的信息素濃度為每個(gè)決策塊選擇規(guī)則.在調(diào)度過(guò)程中，每個(gè)決策塊內(nèi)的實(shí)體采用相同的規(guī)則，生成最終調(diào)度解.

2.2基于動(dòng)態(tài)決策塊的編碼

在DABH算法中，每個(gè)決策塊的大小代表所包含實(shí)體的數(shù)量，這里實(shí)體指工件、機(jī)器和小車(chē)，決策塊的大小決定一個(gè)啟發(fā)式規(guī)則所作用的范圍，本節(jié)對(duì)決策塊以及基于決策塊的編碼進(jìn)行形式化的描述.

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

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

在定義1中，條件1）表示所有實(shí)體都被劃分到各個(gè)決策塊中，條件2）表示一個(gè)實(shí)體不能重復(fù)出現(xiàn)在多個(gè)決策塊中.

例1.假設(shè)在工件分派子問(wèn)題中有4個(gè)工件，這些工件被劃分成兩個(gè)決策塊.那么兩個(gè)決策塊的大小之和為4，并且決策塊之間沒(méi)有重復(fù)的工件出現(xiàn).

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

例2.假設(shè)測(cè)試問(wèn)題有8個(gè)實(shí)體，包括2個(gè)工件，4臺(tái)機(jī)器和2個(gè)單元，即E=｛e1，···，e8｝，啟發(fā)式規(guī)則集合

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

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

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

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

由此可見(jiàn)，當(dāng)決策塊大小不全為1時(shí)，決策塊策略能夠有效縮小搜索空間，在計(jì)算效率方面會(huì)有所提高.但是當(dāng)決策塊大小過(guò)大時(shí)，問(wèn)題求解空間將過(guò)于單一，有可能遺漏掉優(yōu)質(zhì)解，導(dǎo)致算法的優(yōu)化性能受到限制.因此確定合理的決策塊大小，將有利于在提高計(jì)算效率的同時(shí)保證算法的優(yōu)化性能.

2.3基于動(dòng)態(tài)決策塊的規(guī)則選取

在DABH算法中，通過(guò)信息素引導(dǎo)動(dòng)態(tài)生成決策塊，以決策塊為單位選擇啟發(fā)式規(guī)則，對(duì)決策塊內(nèi)的所有實(shí)體應(yīng)用規(guī)則得到調(diào)度解.算法根據(jù)生成的調(diào)度解的優(yōu)劣更新信息素，從而達(dá)到尋優(yōu)的目標(biāo).

2.3.1信息素結(jié)構(gòu)

在構(gòu)造信息素結(jié)構(gòu)時(shí)，DABH包含兩類(lèi)信息素矩陣，即決策塊劃分矩陣和啟發(fā)式規(guī)則選擇矩陣.

針對(duì)分派、排序、運(yùn)輸三個(gè)子問(wèn)題，決策塊劃分矩陣分別為工件、機(jī)器和小車(chē)三個(gè)決策塊劃分矩陣.三個(gè)矩陣的大小分別為N×D'、M×D''和C×D'''，其中N、M 和C分別表示工件、機(jī)器和小車(chē)的數(shù)量，D'、D''和D'''分別表示工件、機(jī)器和小車(chē)決策塊大小的上限，上限取值通過(guò)參數(shù)實(shí)驗(yàn)獲得，在第3.2節(jié)中有詳細(xì)描述.矩陣中元素τi，p表示第i個(gè)決策塊的大小為p的信息素濃度.

同上分析，啟發(fā)式規(guī)則矩陣分別為工件、機(jī)器和小車(chē)三個(gè)分派規(guī)則矩陣.矩陣大小為分別為N×R'、M×R''和C×R'''，其中R'、R''和R'''分別表示分派規(guī)則、排序規(guī)則和運(yùn)輸規(guī)則的數(shù)量.矩陣中元素τi，q表示第i個(gè)決策塊選取第q個(gè)啟發(fā)式規(guī)則的信息素濃度.

2.3.2候選規(guī)則集

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

1）候選分派規(guī)則

First available（FA）：選擇最先可用機(jī)器.

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

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

Most available（MA）：選擇當(dāng)前緩沖區(qū)內(nèi)待加工工件最少的機(jī)器.

Shortest processing time（SPT）：選擇加工時(shí)間最短的機(jī)器.

2）候選排序規(guī)則

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

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

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

Weighted shortest processing time（WSPT）：選擇具有最小加權(quán)加工時(shí)間的工件.

Time in shop（TIS）：選擇在當(dāng)前機(jī)器緩沖隊(duì)列中等待時(shí)間最長(zhǎng)的工件.

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

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

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

Apparent tardiness cost（ATC）：選擇ATC值最大的工件，具體計(jì)算見(jiàn)式（19）.

Cost over time（COVERT）：選擇COVERT值最大的工件，具體計(jì)算見(jiàn)式（20）.

Slackperremainingprocessingtime（S/RPT）：選擇S/RPT值最小的工件，具體計(jì)算見(jiàn)式（21）.

3）候選運(yùn)輸規(guī)則

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

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

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

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

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

Weighted shortest processing time（WSPT）：選擇具有最小加權(quán)加工時(shí)間的工件.

Time in shop（TIS）：選擇當(dāng)前機(jī)器緩沖隊(duì)列中等待時(shí)間最長(zhǎng)的工件.

2.3.3確定決策塊大小和規(guī)則

在DABH算法中，采用ACO算法來(lái)確定決策塊的大小，并為每個(gè)決策塊選取規(guī)則.每只螞蟻通過(guò)信息素濃度計(jì)算選擇決策塊大小和啟發(fā)式規(guī)則的概率.

1）當(dāng)螞蟻選擇決策塊大小時(shí)，第i個(gè)決策塊的大小為p的概率由式（22）計(jì)算可得.

其中，τip表示第i個(gè)決策塊的大小為i的信息素濃度.D表示決策塊大小的上限，當(dāng)選擇工件決策塊大小時(shí)，D為D'；當(dāng)選擇機(jī)器決策塊大小時(shí)，D為D''；當(dāng)選擇小車(chē)決策塊大小時(shí)，D為D'''.

2）當(dāng)螞蟻選擇啟發(fā)式規(guī)則時(shí)，第i個(gè)決策塊選取第q個(gè)啟發(fā)式規(guī)則的概率由式（23）計(jì)算可得.

其中，τiq表示第i個(gè)決策塊的選取第q個(gè)啟發(fā)式規(guī)則的信息素濃度.R表示啟發(fā)式規(guī)則的數(shù)量，為工件決策塊選擇規(guī)則時(shí)，R為R'；為機(jī)器決策塊選擇規(guī)則時(shí)，R為R''；為小車(chē)決策塊選擇規(guī)則時(shí)，R為

R'''.

2.3.4信息素更新

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

信息素更新規(guī)則如下：

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

2）啟發(fā)式規(guī)則的信息素更新規(guī)則.若第i'個(gè)決策塊選擇第l個(gè)分派規(guī)則，則啟發(fā)式規(guī)則選擇矩陣中的元素τi'l根據(jù)式（25）進(jìn)行更新.

在式（24）和（25）中，?τ=Q/Score，Q為信息素更新量影響因子，Score為更新信息素的調(diào)度解對(duì)應(yīng)的目標(biāo)函數(shù)值.

2.4基于動(dòng)態(tài)決策塊的解碼

DABH算法通過(guò)ACO算法為決策塊選擇啟發(fā)式規(guī)則，得到一組規(guī)則編碼序列，系統(tǒng)將其轉(zhuǎn)換成具體的調(diào)度解，即解碼過(guò)程.解碼算法描述如下：

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

步驟2.分別把排序規(guī)則分配至各機(jī)器，分派規(guī)則分配至各工件，運(yùn)輸規(guī)則分配至各單元小車(chē).

步驟3.如果所有工件都已完工，轉(zhuǎn)步驟11.

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

步驟5.如果單元c的小車(chē)是空閑可用的且有要運(yùn)輸?shù)墓ぜ?，則轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟7.

步驟6.根據(jù)運(yùn)輸規(guī)則計(jì)算單元c中待運(yùn)輸工件的優(yōu)先級(jí)，在不超過(guò)小車(chē)容量的情況下根據(jù)優(yōu)先級(jí)進(jìn)行組批并確定小車(chē)的運(yùn)輸路徑.

步驟7.如果機(jī)器m變空閑，則轉(zhuǎn)步驟8；否則，轉(zhuǎn)步驟10.

步驟8.根據(jù)排序規(guī)則調(diào)度一個(gè)工件.

步驟9.記錄該工件調(diào)度工序的開(kāi)工時(shí)間，完工時(shí)間和對(duì)應(yīng)的加工機(jī)器.

步驟10.t=t+1，轉(zhuǎn)到步驟3.

步驟11.利用步驟9的記錄信息，根據(jù)式（1）計(jì)算相應(yīng)的目標(biāo)函數(shù)值TWT.算法結(jié)束.

3　實(shí)驗(yàn)與分析

為了驗(yàn)證DABH算法的優(yōu)化性能和計(jì)算效率，本文進(jìn)行了多組對(duì)比實(shí)驗(yàn)，仿真實(shí)驗(yàn)采用JAVA語(yǔ)言實(shí)現(xiàn)，運(yùn)行在3.10GHz Core i5-2400 CPU，4GB RAM的PC機(jī)上.

3.1實(shí)驗(yàn)設(shè)計(jì)

在運(yùn)輸能力受限的跨單元調(diào)度問(wèn)題研究中，目前尚沒(méi)有相關(guān)的Benchmark，因此設(shè)計(jì)了不同規(guī)模下的多組測(cè)試用例.測(cè)試用例的性能評(píng)價(jià)指標(biāo)為目標(biāo)函數(shù)值TWT，按照式（1）計(jì)算可得，與TWT相關(guān)的工件交貨期di按式（26）進(jìn)行計(jì)算.

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

實(shí)驗(yàn)包括20個(gè)不同大小的規(guī)模，機(jī)器和工件相關(guān)屬性的取值如表1所示.每個(gè)規(guī)模下根據(jù)表1的參數(shù)隨機(jī)產(chǎn)生10個(gè)不同測(cè)試用例，對(duì)每個(gè)不同的測(cè)試用例進(jìn)行5次獨(dú)立的仿真實(shí)驗(yàn).每個(gè)測(cè)試問(wèn)題采用pn1mn2cn3的記法，表示該測(cè)試問(wèn)題中包含n1個(gè)工件、n2臺(tái)機(jī)器和n3個(gè)單元.

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

為了驗(yàn)證算法的有效性，實(shí)驗(yàn)分別在不同問(wèn)題規(guī)模下獲取多個(gè)測(cè)試用例的目標(biāo)函數(shù)TWT的平均值，通過(guò)DABH方法與其他方法之間的Gap值進(jìn)行對(duì)比分析.

3.2參數(shù)分析

本文參數(shù)設(shè)計(jì)采用全因子設(shè)計(jì)方法［22］，使用ANOVA（Analysis of variance）方法從單因子效應(yīng)和雙因子交互作用兩個(gè)方面進(jìn)行分析，觀測(cè)多個(gè)因素對(duì)算法優(yōu)化目標(biāo)TWT的影響，從而確定算法最優(yōu)參數(shù)的設(shè)置.

由于DABH采用ACO算法搜索規(guī)則，因此信息素?fù)]發(fā)因子ρ、信息素更新量影響因子Q和信息素濃度最大值τmax等參數(shù)會(huì)對(duì)算法的優(yōu)化性能有所影響.由于信息素更新量與Q直接相關(guān)，在若干次迭代更新后優(yōu)質(zhì)解路徑上的信息素濃度將達(dá)到τmax，因此將Q/τmax作為實(shí)驗(yàn)參數(shù)，其中τmax取值為5，ρ和Q/τmax的參數(shù)取值分4個(gè)級(jí)別，如表2所示.

表2　DABH參數(shù)Table 2　Parameters in DABH

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

圖4　最小化TWT目標(biāo)下的單因子主效應(yīng)圖Fig.4　Influence of each factor with respect to minimizing TWT

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

在決策塊大小上限的參數(shù)實(shí)驗(yàn)中，工件、機(jī)器和小車(chē)決策塊數(shù)量的上限D(zhuǎn)'、D''、D'''分別根據(jù)三種實(shí)體數(shù)量的百分比｛10%，20%，···，100%｝進(jìn)行取值，測(cè)試10種不同規(guī)格的參數(shù)設(shè)置，最終效果最好的上限參數(shù)為100%，因此D'、D''、D'''分別被設(shè)為三種實(shí)體的數(shù)量.

3.3與基于靜態(tài)決策塊的方法比較

為了檢驗(yàn)DABH算法中動(dòng)態(tài)決策塊劃分策略的有效性，本節(jié)對(duì)比實(shí)驗(yàn)基于采用DABH的算法框架，將動(dòng)態(tài)決策塊劃分策略與三種不同的靜態(tài)決策塊劃分策略進(jìn)行比較.為了保證實(shí)驗(yàn)的公平性，三組對(duì)比實(shí)驗(yàn)采取相同的運(yùn)行時(shí)間作為終止條件.

1）每個(gè)決策塊的范圍是調(diào)度中的一個(gè)實(shí)體

在調(diào)度中每個(gè)決策塊包含一個(gè)實(shí)體，將這種方法記為DABH-ONE.

實(shí)驗(yàn)按照式（27）計(jì)算DABH與DABH-ONE之間的Gap值，記為GapONE.由于計(jì)算方法類(lèi)似，在后續(xù)的對(duì)比實(shí)驗(yàn)中，DABH與其它算法之間的Gap值計(jì)算方法均參考式（27）.

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

實(shí)驗(yàn)結(jié)果如表3所示，在不同規(guī)模的測(cè)試問(wèn)題下，DABH均優(yōu)于DABH-ONE的優(yōu)化性能，Gap平均值為11.5%.這組實(shí)驗(yàn)表明，隨著問(wèn)題規(guī)模增大，實(shí)體的數(shù)量增多，DABH-ONE的解編碼長(zhǎng)度也增大，因此搜索空間變大.而DABH根據(jù)問(wèn)題規(guī)模將所有實(shí)體劃分為若干個(gè)決策塊，每個(gè)決策塊最少包含一個(gè)實(shí)體，決策塊的數(shù)量小于或等于實(shí)體的數(shù)量，相應(yīng)的解編碼長(zhǎng)度減少，從而適當(dāng)?shù)乜s小了搜索空間.由此可見(jiàn)，DABH-ONE雖然能關(guān)注每個(gè)實(shí)體的狀態(tài)，但由于搜索空間過(guò)大，使得在相同條件下前者的計(jì)算能力下降，所以綜合求解能力與DABH相比較差.

2）每個(gè)決策塊的范圍是調(diào)度中的一類(lèi)實(shí)體

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

3）每個(gè)決策塊的范圍是調(diào)度中的多個(gè)實(shí)體

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

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

結(jié)合表3與圖6分析發(fā)現(xiàn)，從平均性能來(lái)看，DABH-AVG處于中間的位置，這主要與DABHAVG的決策塊大小適中有關(guān).從圖6可以看出，當(dāng)問(wèn)題規(guī)模較小時(shí)，DABH-ALL的相對(duì)性能最差，當(dāng)問(wèn)題規(guī)模較大時(shí)，DABH-ONE的性能最差，而DABH-AVG的表現(xiàn)相對(duì)平穩(wěn).

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

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

3.4與基于動(dòng)態(tài)決策塊的方法比較

在現(xiàn)有的研究中，V′azquez-Rodr′?guez等［16］采用基于動(dòng)態(tài)決策塊和GA的超啟發(fā)式方法（Dynamic decision block GA-based hyper-heuristic），以解決作業(yè)車(chē)間調(diào)度問(wèn)題，本文將其稱(chēng)作DGBH. DGBH針對(duì)調(diào)度中的決策，將所有決策劃分為若干個(gè)大小不等的決策塊.而DABH是將所有實(shí)體劃分為多個(gè)決策塊.本節(jié)將進(jìn)行DABH與DGBH的對(duì)比實(shí)驗(yàn).

為了保證實(shí)驗(yàn)的公平性，對(duì)比實(shí)驗(yàn)采用相同的問(wèn)題模型和候選規(guī)則集，種群數(shù)目為100，終止條件為DGBH算法運(yùn)行200代所需要的時(shí)間.

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

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

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

從圖7中可以看出，DABH在第80代之后趨于穩(wěn)定，DGBH在第150代后趨于穩(wěn)定，DABH的收斂速度快于DGBH方法，體現(xiàn)出DABH在尋優(yōu)能力方面上的優(yōu)勢(shì).

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

4　結(jié)論

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

考慮到不同的實(shí)體具有不同的屬性，在今后的工作中可以考慮根據(jù)實(shí)體之間的相關(guān)性劃分決策塊，使決策塊的劃分過(guò)程與問(wèn)題的特性相互適應(yīng)，從而提升算法的性能.

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（賈凌云，李冬妮，田云娜.基于混合蛙跳和遺傳規(guī)劃的跨單元調(diào)度方法.自動(dòng)化學(xué)報(bào)，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（劉兆赫，李冬妮，王樂(lè)衡，田云娜.考慮運(yùn)輸能力限制的跨單元調(diào)度方法.自動(dòng)化學(xué)報(bào)，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.

田云娜北京理工大學(xué)計(jì)算機(jī)學(xué)院智能信息技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室博士研究生，延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院講師.主要研究方向?yàn)檫M(jìn)化計(jì)算與智能優(yōu)化方法.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.）

李冬妮北京理工大學(xué)計(jì)算機(jī)學(xué)院智能信息技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室副教授.主要研究方向?yàn)橹悄軆?yōu)化方法及其在制造業(yè)的應(yīng)用.本文通信作者.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.）

劉兆赫北京理工大學(xué)計(jì)算機(jī)學(xué)院智能信息技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室碩士研究生.主要研究方向?yàn)檫M(jìn)化計(jì)算和生產(chǎn)調(diào)度.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.）

鄭 丹北京理工大學(xué)計(jì)算機(jī)學(xué)院智能信息技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室碩士研究生.主要研究方向?yàn)檫M(jìn)化計(jì)算和生產(chǎn)調(diào)度.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

國(guó)家自然科學(xué)基金（71401014）資助

Supported by National Natural Science Foundation of China（71401014）

本文責(zé)任編委趙千川

Recommended by Associate Editor ZHAO Qian-Chuan

1.北京理工大學(xué)計(jì)算機(jī)學(xué)院智能信息技術(shù)北京市重點(diǎn)實(shí)驗(yàn)室 北京1000812.延安大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院延安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