基于遺傳模擬退火算法的自動化制造單元周期調(diào)度

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

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

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

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

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

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

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

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

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

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

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

為便于數(shù)學(xué)模型的表述，定義如表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)

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

2 IGASA算法設(shè)計(jì)

2.1 編碼方式和種群初始化

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

2.2 雙適應(yīng)度

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

第一個(gè)適應(yīng)度參照文獻(xiàn)[9]中的方法計(jì)算。對于任意給定的一個(gè)解，使用式(13)計(jì)算第一個(gè)適應(yīng)度值：

f1=T+ω3

(13)

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

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

(14)

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

(15)

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

2.3 解的更新

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

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

在進(jìn)行選擇操作時(shí)，采用錦標(biāo)賽法從隨機(jī)選擇的兩個(gè)染色體中挑選出較好的進(jìn)入子代種群，步驟如下：

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

步驟2若兩個(gè)染色體適應(yīng)度值f1不相等，選擇f1較小的染色體進(jìn)入子代種群；若兩個(gè)染色體f1值相等，選擇適應(yīng)度值f2較大的染色體進(jìn)入子代種群。

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

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

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

(16)

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

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

2.4 不可行解的修復(fù)

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

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

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

步驟1找出滿足bi

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

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

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

2.5 IGASA算法的步驟

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

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

步驟2隨機(jī)生成初始種群。

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

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

步驟5進(jìn)行選擇操作。

步驟6進(jìn)行交叉操作，應(yīng)用Metropolis準(zhǔn)則判斷是否接受劣解。

步驟7進(jìn)行變異操作，應(yīng)用Metropolis準(zhǔn)則判斷是否接受劣解。

步驟8若n2

步驟9n1←n1+1。若n1

步驟10若t

3 實(shí)驗(yàn)驗(yàn)證

3.1 先后次序約束修復(fù)的效果分析

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

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

3.2 與其他算法的對比分析

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

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

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

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

4 結(jié)語

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