王 娟，唐秋華，毛永年,3

(1.湖南工程學院機械工程學院，湖南 湘潭，411104；2.武漢科技大學冶金裝備及其控制教育部重點實驗室，湖北 武漢，430081；3.遵義師范學院工學院，貴州 遵義，563006)

隨著企業(yè)自動化和智能化程度的提高，物料搬運工作越來越多地由機器人完成。機器人搬運作業(yè)順序不僅影響其自身的工作效率，而且影響整個自動化制造單元的生產(chǎn)效率及生產(chǎn)計劃的執(zhí)行效果。在制定搬運機器人周期作業(yè)順序時，若只有一臺搬運機器人，只有一種工件進入或者離開系統(tǒng)，且工件的加工時間僅能在給定的上、下限范圍內(nèi)變動，則稱之為具有作業(yè)時間窗約束的單機器人單度自動化制造單元調(diào)度問題。

針對這類問題，Phillips等[1]首次建立了混合整數(shù)線性規(guī)劃模型，并構(gòu)建了一個基準案例P&U。此后，研究者逐步提出了各種精確算法、啟發(fā)式算法、元啟發(fā)式算法來求解該問題。隨著制造單元中工作站數(shù)量的增加，分支定界等精確算法[2-4]在求解速度上難以令人滿意；而在使用啟發(fā)式或元啟發(fā)式算法時，首先面臨的難題是所研究問題的可行解空間狹窄，難以找到可行解，更難接近最優(yōu)解。為此，人們采取多種措施，如減小搜索空間、不可行解修復等，以加快求解速度。其中，晏鵬宇等[5-6]計算出最大在制品數(shù)量，據(jù)此將解空間分割成若干子空間，將搜索過程限定在子空間內(nèi)，通過無效空間的剔除提高了算法收斂速度。王躍崗等[7]在混合量子進化算法中加入基于圖論的不可行解修復策略。Lei等[8]在混合量子進化算法中加入啟發(fā)式修復策略。毛永年等[9]在改進遺傳算法中加入不可行解的判斷方法和聯(lián)動修復機制。然而，隨著工作站數(shù)量增多和可行解比例變小，問題的求解難度變得更大，需要采取更加準確而有效的措施去發(fā)掘可行解空間，進一步提升求解速度和質(zhì)量。

為此，本文提出一種具有修復機制的遺傳模擬退火算法(簡稱“IGASA”)。該方法以遺傳算法為基本框架，引入模擬退火機制，通過溫降控制，從算法運行初期到末期遞減較劣解的接受概率，實現(xiàn)全局搜索和集中探測之間的動態(tài)平衡，并對種群中的不可行解進行有限次的修復，從而提升可行解和最優(yōu)解的甄別概率。

1 問題描述和數(shù)學模型

具有作業(yè)時間窗約束的單機器人單度自動化制造單元如圖1所示，有一個裝載站(編號為0)、n個工作站(編號為1～n)、一個卸載站(編號為n+1)和一個物料搬運機器人，加工一類相同的工件。每個工件從裝載站進入制造單元中，順次經(jīng)過工作站1到n后，從卸載站離開制造單元。在裝載站、各工作站和卸載站之間無緩沖區(qū)，工件在任一個工作站完成加工后(加工時間要滿足時間窗約束)，由搬運機器人搬運到下一個工作站。假設裝載站與卸載站的容量無限大，每個工作站上最多只有一個工件在加工，機器人每次最多只能搬運一個工件。

圖1 自動化制造單元示意圖

自動化制造單元的工作效率取決于對搬運機器人作業(yè)的合理規(guī)劃。搬運機器人以一定的周期進行循環(huán)作業(yè)。在它的一個搬運循環(huán)周期內(nèi)，只有一個工件投入生產(chǎn)，且只有一個工件出產(chǎn)。機器人的搬運循環(huán)周期時間即為相鄰兩個工件的出產(chǎn)時間間隔，被稱為生產(chǎn)節(jié)拍或周期長度。對自動化制造單元進行周期調(diào)度，就是要找到最佳的機器人搬運順序，從而使周期長度最短、生產(chǎn)率最高。為了減少周期長度，應盡量使各工作站能夠并行作業(yè)，多個在制品同時進行加工，即在保證可行的前提下，跨周期的工序數(shù)盡量多。

圖2為一個含有4個工作站的自動化制造單元的周期調(diào)度甘特圖。若用搬運作業(yè)i表示機器人從工作站i上取下工件、搬運到工作站i+1并把工件裝載到工作站i+1上的全部操作，則在圖2中，機器人按照(0,2,4,1,3)的順序循環(huán)作業(yè)。在一個周期T內(nèi)，有3個在制品同時加工。工序1和3在一個周期內(nèi)完成，而工序2和4則跨越了兩個周期。

圖2 含4個工作站的自動化制造單元周期調(diào)度Fig.2 A cyclic schedule for robotic cell with four workstations

為便于數(shù)學模型的表述，定義如表1所示的參數(shù)和變量。

表1 模型中的參數(shù)與變量

該問題的混合整數(shù)規(guī)劃模型可以表示為：

minT

(1)

s.t.:

Qi+yi-1,i=1, 1≤i≤n

(2)

M(1-Qi)+bi≥ci,0+d0+c1,i, 2≤i≤n

(3)

yi,j+yj,i=1,i≠j,0≤i,j≤n

(4)

si-(sj+dj)+Myi,j≥cj+1,i,i≠j,1≤i,j≤n

(5)

si-(si-1+di-1)+M(1-yi-1,i)≥ai, 1≤i≤n

(6)

si-(si-1+di-1)-M(1-yi-1,i)≤bi, 1≤i≤n

(7)

(si+T)-(si-1+di-1)+Myi-1,i≥ai, 1≤i≤n

(8)

(si+T)-(si-1+di-1)-Myi-1,i≤bi, 1≤i≤n

(9)

T≥si+di+ci+1,0, 1≤i≤n

(10)

s0=0,Q0=1,Q1=0

(11)

si≥0, 1≤i≤n

(12)

模型的目標函數(shù)是最小化周期長度T。式(2)表示：若工序i跨越兩個周期，則在一個周期內(nèi)搬運i先于搬運i-1；若工序i在一個周期內(nèi)完成，則在一個周期內(nèi)搬運i后于搬運i-1。式(3)表示先后次序約束，當工序i滿足bi

2 IGASA算法設計

2.1 編碼方式和種群初始化

求解具有作業(yè)時間窗的單機器人單度自動化制造單元調(diào)度問題，就是要找出最佳的機器人搬運順序，從而使周期長度最短。所以，在用改進遺傳模擬退火算法進行求解時，解空間即為所有的機器人搬運序列組合，每個解(即染色體)用M=(m0,m1,…,ml,…,mn)表示，其中ml為一個周期內(nèi)的第l次搬運作業(yè)的編號。機器人按固定的搬運順序循環(huán)作業(yè)，任意一個非搬運作業(yè)0開始的解都能等價變換為以搬運作業(yè)0開始的解。以含有5項搬運作業(yè)的此類問題為例，解(0, 1, 2, 3, 4)與解(3, 4, 0, 1, 2)等價。為了保證解的多樣性，采用以任意搬運作業(yè)為首的編碼方式，隨機生成Psize個循環(huán)序列，構(gòu)成初始種群。

2.2 雙適應度

根據(jù)該問題的目標函數(shù)和跨周期決策變量Qi的特性，本文采用雙適應度對解的質(zhì)量進行評價。

第一個適應度參照文獻[9]中的方法計算。對于任意給定的一個解，使用式(13)計算第一個適應度值：

f1=T+ω3

(13)

式中：f1為第一個適應度值；T為解的最短周期長度；ω為解中不可行子序列的個數(shù)。

在計算適應度值f1之前，先對解進行可行性判別，同時得到ω值，判別方法參照文獻[9]。若解可行，T可用文獻[10]中的多項式算法求解。若解不可行，T可用式(14)表示：

(14)

由于不可行解很多，且適應度f1相同的不可行解數(shù)量也較多，為了區(qū)分f1相同的不可行解的優(yōu)劣，引入第二個適應度f2。f2表示解中跨周期工序數(shù)，其計算公式為式(15)：

(15)

對于可行解來說，周期長度越小，則跨周期工序數(shù)越多；反之則跨周期工序數(shù)越少。對于適應度f1相同的不可行解，跨周期工序數(shù)越多，可認為解更優(yōu)，經(jīng)過交叉、變異、修復之后更有可能變?yōu)榭缰芷诠ば驍?shù)較多、周期長度較小的可行解。

2.3 解的更新

在進化過程中，采用遺傳算法中的選擇、交叉、變異生成新解，同時分別在交叉和變異之后采用模擬退火算法中的Metropolis準則來判斷是否接受新解，從而在保留優(yōu)良的基因片段的同時，還能保持解的多樣性。

(1)基于雙適應度的選擇操作

在進行選擇操作時，采用錦標賽法從隨機選擇的兩個染色體中挑選出較好的進入子代種群，步驟如下：

步驟1從種群中隨機選擇兩個染色體(每個染色體入選概率相同) 。

步驟2若兩個染色體適應度值f1不相等，選擇f1較小的染色體進入子代種群；若兩個染色體f1值相等，選擇適應度值f2較大的染色體進入子代種群。

步驟3重復執(zhí)行Psize次步驟1和步驟2，得到新一代種群。

(2)基于雙適應度的交叉操作

在進行交叉操作時，順次將子代種群中的染色體兩兩進行兩點交叉。然后，對于種群中的每個染色體，使用Metropolis準則來判斷是否接受新解，接受概率如式(16)所示。

(16)

(3)基于雙適應度的變異操作

在進行變異操作時，對于每個染色體，隨機選擇兩個基因交換其位置。然后，對于種群中的每個染色體，使用Metropolis準則來判斷是否接受新解，接受概率如式(16)所示。

2.4 不可行解的修復

具有作業(yè)時間窗的單機器人單度自動化制造單元調(diào)度問題的可行解非常少，對不可行解進行修復是提高搜索到可行解概率的非常有力的操作。種群初始化和更新之后，都需要對種群中的不可行解進行修復。在修復之前，先將其等價轉(zhuǎn)換為以搬運作業(yè)0為首的序列，用M′表示，對M′進行兩次修復。

(1)基于跨周期決策的先后次序約束修復

如果M′不能滿足先后次序約束(見式(3))，則解不可行，采用下面的步驟進行修復：

步驟1找出滿足bi

步驟2分析R中的任意一個搬運Rj在M′中的位置是否位于搬運Rj-1之后，若不滿足，則將搬運Rj在M′中的位置調(diào)至搬運Rj-1之后。修復后的解用M″表示。

(2)聯(lián)動修復

經(jīng)過上述修復后得到的解M″不一定是可行解，對其進行可行性判斷，若解M″可行，則可不進行聯(lián)動修復，若解M″不可行，則需要進行聯(lián)動修復，聯(lián)動修復采用文獻[9]中相應的方法。

2.5 IGASA算法的步驟

根據(jù)經(jīng)典的模擬退火算法和遺傳算法的流程以及上述修復機制，給出IGASA算法的具體步驟：

步驟1設置初始溫度T0(充分大)、終止溫度Te、溫度衰減率Pt、最大內(nèi)循環(huán)次數(shù)Iloop、種群規(guī)模Psize、交叉概率Pc、變異概率Pm、最大迭代次數(shù)g、最大修復循環(huán)次數(shù)h；初始化模擬退火當前溫度t←T0、內(nèi)循環(huán)迭代計數(shù)器n1←0、迭代計數(shù)器n2←0。

步驟2隨機生成初始種群。

步驟3判斷種群中解的可行性，對可行解進行局部鄰域搜索，對不可行解進行先后次序約束修復和聯(lián)動修復。

步驟4對當前種群中的解進行評價，如果有比全局最優(yōu)解更好的解，則保存該解為全局最優(yōu)解，n2←0；否則，運用精英保留策略，將當前種群中最差的解用當前全局最優(yōu)解替換，n2←n2+1。

步驟5進行選擇操作。

步驟6進行交叉操作，應用Metropolis準則判斷是否接受劣解。

步驟7進行變異操作，應用Metropolis準則判斷是否接受劣解。

步驟8若n2

步驟9n1←n1+1。若n1

步驟10若t

3 實驗驗證

3.1 先后次序約束修復的效果分析

表2 隨機案例的測試結(jié)果

從表2中可以看出，隨著不能跨周期工序數(shù)的增多，IGASAFR算法求解的精度總體上越來越高，單純使用先后次序約束修復就可以得到最優(yōu)解，而且，IGASAFR算法的速度比IGASASR算法快很多，即先后次序約束修復的速度遠快于聯(lián)動修復的速度。同時，隨著不能跨周期工序數(shù)的增多，IGASA算法速度與IGASASR算法相比由略慢變化到略快，具體原因是：如果解中沒有不可行子序列，則無需進行聯(lián)動修復；在IGASA算法中，當不能跨周期工序數(shù)較多時，先后次序約束修復的作用比較大，經(jīng)過此修復后，解中沒有不可行子序列而能跳過聯(lián)動修復的概率顯著增加，從而使IGASA算法的求解速度比單純使用聯(lián)動修復的IGASASR算法要快。

3.2 與其他算法的對比分析

為驗證IGASA算法的性能，用該算法求解8個基準案例各10次，得到每個基準案例周期長度的最小值和平均值與最優(yōu)解的百分率偏差，并與傳統(tǒng)的遺傳算法(GA)和模擬退火算法(SA)、HIGA算法[9]進行對比，所得實驗結(jié)果如表3所示。單純使用GA或SA時，8個基準案例中只有3～4個案例可以找到最優(yōu)解。從表3可以看出，IGASA算法與HIGA算法有幾乎相同的求解精度，但是前者的速度比后者快很多，基本上可以節(jié)約2/3的CPU運行時間。

表3 基準案例的測試結(jié)果

圖3為用IGASA和HIGA求解基準案例Zinc的收斂曲線。從圖3也可以看出，IGASA算法能以更快的速度搜索并收斂到最優(yōu)解。IGASA算法能在更短的時間內(nèi)求得基準案例的最優(yōu)解或近優(yōu)解，其原因在于：①遺傳算法采用種群進行進化，可在整個解空間同時搜索，但具有較差的局部搜索能力；模擬退火算法的局部搜索能力雖然較強，但是采用單個個體進行進化，收斂速度慢；將兩者結(jié)合，使全局和局部搜索能力都得到強化，可避免過早收斂。②采用雙適應度對解進行評價，對于周期時間相同的不可行解，選擇跨周期工序數(shù)大的解作為較好解，使其逐漸逼近最優(yōu)解。③對不可行解進行兩步修復，第一步保證不能跨周期的工序?qū)膬蓚€搬運滿足先后次序約束，第二步使用聯(lián)動修復機制盡量使機器人移動能力滿足工件的加工時間窗約束，使解以最大可能性朝著目標函數(shù)優(yōu)化的方向進行調(diào)整。因此IGASA算法在搜索時既能保證解的多樣性，又能使解朝著有用的、可行的方向進化，最終找到最優(yōu)解。

圖3 IGASA和HIGA求解案例Zinc的收斂曲線Fig.3 Convergence curves of benchmark problem Zinc by IGASA and HIGA

4 結(jié)語

本文針對具有作業(yè)時間窗的單機器人單度自動化制造單元調(diào)度問題，提出了一種改進遺傳模擬退火算法。在種群的進化過程中，利用選擇、交叉、變異操作對解進行更新，并利用Metropolis準則判斷是否接受交叉和變異后產(chǎn)生的劣解，使解保持多樣性且避免局部最優(yōu)。在選擇操作和Metropolis準則中使用周期時間和跨周期工序數(shù)雙適應度評價解的優(yōu)劣，加大逼近最優(yōu)解的概率。然后運用先后次序約束修復和聯(lián)動修復機制對不可行解進行修復，避免算法的盲目搜索，提高搜索效率。通過對現(xiàn)有文獻中基準案例的測試以及隨機案例的測試，驗證了該算法求解此類自動化制造單元調(diào)度問題的有效性和優(yōu)越性。