阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題可行解性質(zhì)研究

趙曉飛， 郭秀萍

(1.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，四川 成都 610031; 2.重慶文理學(xué)院 經(jīng)濟(jì)管理學(xué)院，重慶 永川 402160)

0 引言

機(jī)器人制造單元是一種先進(jìn)生產(chǎn)系統(tǒng)，廣泛應(yīng)用于機(jī)械制造、電路板印刷(Printed Circuit Board, PCB)、半導(dǎo)體制造以及計(jì)算機(jī)集成制造、紡織等行業(yè)[1～4]。隨著技術(shù)進(jìn)步和市場(chǎng)需求改變，機(jī)器人制造單元由生產(chǎn)同類型工件向生產(chǎn)多類型工件[5,6]轉(zhuǎn)變。為了提高機(jī)器人制造單元生產(chǎn)效率和改進(jìn)機(jī)器人制造單元利用率，將待加工多類型工件組成一個(gè)最小工件(Minimum Part Set, MPS)，按照混流生產(chǎn)方式周期生產(chǎn)。

混流生產(chǎn)機(jī)器人制造單元調(diào)度問題是NP難題[7]，為了優(yōu)化該問題，啟發(fā)式算法[8～10]和智能算法被提出[11～13]，但這些方法僅能解決兩工作站或三工作站機(jī)器人制造單元調(diào)度問題，并且這些方法都針對(duì)求解結(jié)果進(jìn)行分析，缺乏對(duì)機(jī)器人制造單元調(diào)度問題可行解性質(zhì)進(jìn)行探討，使得提出算法難以適用于大規(guī)模機(jī)器人制造單元調(diào)度問題；從算法設(shè)計(jì)角度分析，已有算法基本都通過枚舉機(jī)器人運(yùn)行順序?qū)崿F(xiàn)，沒有同時(shí)優(yōu)化機(jī)器人運(yùn)行順序和工件加工順序，易于陷入局部最優(yōu)解。

因此，將機(jī)器人制造單元調(diào)度問題涉及的機(jī)器人運(yùn)行順序和工件加工順序合二為一，變二維調(diào)度問題為一維調(diào)度問題就成為求解大規(guī)模機(jī)器人制造單元調(diào)度問題的關(guān)鍵。另外，由于機(jī)器人制造單元調(diào)度問題的NP難特性，探討機(jī)器人制造單元調(diào)度問題可行解性質(zhì)就成為解決該問題的重點(diǎn)。

本文針對(duì)混流生產(chǎn)機(jī)器人制造單元調(diào)度問題，利用機(jī)器人活動(dòng)調(diào)度表示該問題的解，將二維調(diào)度問題轉(zhuǎn)化為一維調(diào)度問題，探討了可行解性質(zhì)。

1 問題描述與模型建立

典型機(jī)器人制造單元由m個(gè)工作站P1,P2,…,Pm、一個(gè)由計(jì)算機(jī)控制的物料搬運(yùn)機(jī)器人(本文稱為機(jī)器人)、一個(gè)輸入裝置P0和一個(gè)輸出裝置Pm+1組成。總數(shù)為n的多類型工件J1,J2,…,Jn組成MPS同時(shí)在機(jī)器人制造單上被加工。Jj(1≤j≤n)從P0進(jìn)入機(jī)器人制造單元，依次在P1,P2,…,Pm上加工，最后從Pm+1離開機(jī)器人制造單元。不同類型工件在同一工作站上的加工時(shí)間不同，Jj(1≤j≤n)在Pi(1≤i≤m)上的最小加工時(shí)間為ai,j(i≤i≤m,1≤j≤n)。機(jī)器人負(fù)責(zé)工件在工作站之間、輸入裝置和工作站之間以及工作站和輸出裝置之間的移動(dòng)。任何時(shí)刻，機(jī)器人最多搬運(yùn)一個(gè)工件，任意工作站最多加工一個(gè)工件。機(jī)器人將Jj(1≤j≤n)從Pf搬運(yùn)到Pf+1記為rf,j(0≤f≤m)，包含三步操作：(1)從Pf卸下Jj；(2)將Jj移動(dòng)到Pf+1；(3)將Jj裝入Pf+1。

為了便于描述問題和避免混淆，定義以下符號(hào)。

決策變量：

ti,j：ri,j的開始時(shí)間(0≤i≤m,1≤j≤n)。

參數(shù)：

T：周期時(shí)間，即兩個(gè)相鄰MPS中第一個(gè)工件進(jìn)入機(jī)器人制造單元所經(jīng)過的時(shí)間。

di,j：常數(shù)，有載移動(dòng)時(shí)間，即執(zhí)行ri,j所耗費(fèi)的時(shí)間(0≤i≤m;1≤j≤n)。

cq,k：空載移動(dòng)時(shí)間，機(jī)器人在Pq與Pk之間不搬運(yùn)工件移動(dòng)耗費(fèi)的時(shí)間(0≤q,k≤m+1)。

M：足夠大的正實(shí)數(shù)。

τi：第i個(gè)機(jī)器人活動(dòng)(0≤i≤n(m+1))。

job(i)：機(jī)器人活動(dòng)τi搬運(yùn)的工件(0≤i≤n(m+1))。

Q(i)：機(jī)器人活動(dòng)τi起始工作站對(duì)應(yīng)下標(biāo)(0≤i≤n(m+1))。

σ：{1,2,…,n(m+1)-1}→{1,2,…,n(m+1)-1}的置換。

另外，本文假設(shè)以下兩式成立。

df,j≥cf,f+1,1≤j≤n,0≤f≤m

(1)

cq,k≤cq,l+cl,k,0≤1,q,k≤m+1

(2)

式(1)表示相鄰工作站之間，有載移動(dòng)時(shí)間不小于空載移動(dòng)時(shí)間；式(2)是三角不等式。為此本文研究問題的數(shù)學(xué)模型如下：

目標(biāo)函數(shù):MinimizeT

1≤i≤m,1≤j≤n

(3)

j≠h,1≤i≤m,1≤j,h≤n

(4)

1≤i≤m

(5)

0≤i,l≤m,1≤j,h≤n

(6)

0≤i,l≤m,1≤j,h≤n

(7)

ti,j≥d1,0+c1,i′,

i≠0或j≠1且0≤i≤m,1≤j≤n

(8)

T≥ti,j+di,j+c(i+1),0,

0≤i≤m,1≤j≤n

(9)

t0,1=0

(10)

(11)

ti,j≥0,0≤i≤m,1≤j≤n

(12)

T≥0

(13)

(14)

約束(3)保證了工件加工時(shí)間約束；約束(4)和約束(5)確保工作站容量約束不被違反；約束(6)和約束(7)避免機(jī)器人沖突；約束(8)給出了ri,j的開始時(shí)間不小于r0,1的開始時(shí)間；約束(9)給出了目標(biāo)函數(shù)值下界；約束(10)和(11)界定了每個(gè)周期總是從r0,1開始；約束(12)和(13)是非負(fù)約束；約束(14)是0-1變量約束。

2 可行解性質(zhì)

優(yōu)化阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題，實(shí)質(zhì)是找到機(jī)器人運(yùn)行順序和工件加工順序這兩個(gè)相互關(guān)聯(lián)的順序。已有研究中，要么固定工件加工順序，優(yōu)化機(jī)器人運(yùn)行順序；要么固定機(jī)器人運(yùn)行順序，優(yōu)化工件加工順序，導(dǎo)致可行解性質(zhì)討論不多。因此，要討論可行解性質(zhì)，首先將機(jī)器人運(yùn)行順序和工件加工順序合二為一，變二維調(diào)度問題為一維調(diào)度問題。為此，給出定義1。

定義1τi+(m+1)(j-1)稱為機(jī)器人活動(dòng)，定義如下：

τi+(m+1)(j-1)=i+(m+1)(j-1),1≤j≤n,0≤i≤m

(15)

依據(jù)定義1，每個(gè)ri,j唯一對(duì)應(yīng)一個(gè)τi+(m+1)(j-1)。例如，由4個(gè)工作站P1,P2,P3,P4、一個(gè)機(jī)器人、一個(gè)輸入裝置P0和一個(gè)輸出裝置P5組成的機(jī)器人制造單元。MPS由J1,J2,J3組成。ri,j與τi+(m+1)(j-1)對(duì)應(yīng)情形見表1。

表1 ri,j與τi+(m+1)(j-1)對(duì)應(yīng)情形

求解阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的實(shí)質(zhì)是對(duì)ri,j的開始時(shí)間ti,j(0≤i≤m;1≤j≤n)排序。依據(jù)定義1，決策變量ti,j也是機(jī)器人活動(dòng)τi+(m+1)(j-1)的開始時(shí)間，又因?yàn)楸疚难芯孔枞{(diào)度，因此ti,j排序可轉(zhuǎn)化為機(jī)器人活動(dòng)排序，將二維排序轉(zhuǎn)化為一維排序。故，問題的解可表示為：S=(τ0,τσ(1),τσ(2),…,τσ(n(m+1)-1))。

為了判斷解S是否可行，給出定義2。

定義2滿足以下條件機(jī)器人活動(dòng)排序，稱為可行機(jī)器人活動(dòng)調(diào)度。

(1)執(zhí)行τi(0≤i≤n(m+1)-1)前，job(i)必須被裝載在PQ(i)上，且完成加工；

(2)禁止機(jī)器人向非空工作站裝載工件；

(3)禁止機(jī)器人向空工作站卸載工件。

依據(jù)定義1和定義2，如果確定了可行機(jī)器人活動(dòng)調(diào)度，那么ti,j排序可以唯一確定。依據(jù)定義1，確定了可行機(jī)器人活動(dòng)調(diào)度，機(jī)器人運(yùn)行順序和工件加工順序被唯一確定。

機(jī)器人活動(dòng)調(diào)度雖然是單排序，但是隱含了機(jī)器人運(yùn)行順序和工件加工順序；本文研究周期調(diào)度，允許工件跨周期加工，因此，可行機(jī)器人活動(dòng)調(diào)度涉及一些特殊性質(zhì)。為了便于詳細(xì)闡述這些性質(zhì)，先給出加工同類型工件機(jī)器人制造單元調(diào)度問題可行解的性質(zhì)。

針對(duì)時(shí)間窗約束加工兩類型工件機(jī)器人制造單元調(diào)度問題，Lei和Liu[14]給出了如下結(jié)論：若S是可行機(jī)器人活動(dòng)調(diào)度，那么兩個(gè)連續(xù)Pi之間有且僅有一個(gè)Pi-1。本文將該結(jié)論拓展到加工同類型工件機(jī)器人制造單元調(diào)度問題和阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題。

性質(zhì)1若機(jī)器人活動(dòng)調(diào)度S是加工同類型工件機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度當(dāng)且僅當(dāng)每對(duì)連續(xù)Pi之間有且僅有一個(gè)Pi-1。

證明充分性證明。因?yàn)镾是加工同類型工件機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度，所以，S中，Pi的個(gè)數(shù)與Pi-1的個(gè)數(shù)一樣多。依據(jù)引理1[15]，每對(duì)連續(xù)Pi-1之間有且僅有一個(gè)Pi，意思是Pi與Pi-1交叉出現(xiàn)。那么每對(duì)連續(xù)Pi之間有且僅有一個(gè)Pi-1。性質(zhì)1的充分性成立。

必要性證明。因?yàn)镾是機(jī)器人活動(dòng)調(diào)度，那么依據(jù)多度調(diào)度定義[16]，機(jī)器人活動(dòng)調(diào)度S中，Pi的個(gè)數(shù)與Pi-1的個(gè)數(shù)一樣多。又因?yàn)槊繉?duì)連續(xù)Pi之間有且僅有一個(gè)Pi-1，意思是Pi與Pi-1交替出現(xiàn)。那么每對(duì)連續(xù)Pi-1之間有且僅有一個(gè)Pi。依據(jù)引理1[15]，機(jī)器人活動(dòng)調(diào)度S是可行的。必要性證得。性質(zhì)1證畢。

文獻(xiàn)[15]中引理2闡述了時(shí)間窗約束加工多類型工件機(jī)器人制造單元調(diào)度問題可行解的性質(zhì)。本文將此結(jié)論拓展到阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題，并且證明了該結(jié)論為充要條件。

性質(zhì)2若機(jī)器人活動(dòng)調(diào)度S是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行解機(jī)器人活動(dòng)調(diào)度當(dāng)且僅當(dāng)每對(duì)連續(xù)Pi之間有且僅有一個(gè)Pi+1，且Pi+1與緊前Pi加工相同工件。

證明充分性證明。由于引理2[15]在時(shí)間窗約束條件下得到，本文為阻塞約束，條件更寬松，因此，性質(zhì)2的充分性證明詳見引理2[15]。

必要性證明。因?yàn)镾是機(jī)器人活動(dòng)調(diào)度，依據(jù)多度調(diào)度定義[16]，機(jī)器人活動(dòng)調(diào)度S中，Pi的個(gè)數(shù)與Pi+1的個(gè)數(shù)一樣多。又因?yàn)槊繉?duì)連續(xù)Pi之間有且僅有一個(gè)Pi+1，意思是Pi與Pi+1交替出現(xiàn)。且Pi+1與緊前Pi加工相同工件。依據(jù)引理1[15]和定義2，機(jī)器人活動(dòng)調(diào)度S是可行的。必要性證得。性質(zhì)2證畢。

依據(jù)性質(zhì)1和性質(zhì)2，可得性質(zhì)3。

性質(zhì)3若機(jī)器人活動(dòng)調(diào)度S是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度當(dāng)且僅當(dāng)每對(duì)連續(xù)Pi之間有且僅有一個(gè)Pi-1，且Pi-1與緊后Pi加工的工件相同。

證明充分性證明。由性質(zhì)2可以得到，可行機(jī)器人活動(dòng)調(diào)度S中，Pi的個(gè)數(shù)與Pi-1的個(gè)數(shù)一樣多，每對(duì)連續(xù)Pi-1之間有且僅有一個(gè)Pi，意思是Pi與Pi-1交替出現(xiàn)，而且Pi與Pi-1緊前加工的工件相同。又因?yàn)檎{(diào)度是周期進(jìn)行的，所以，每對(duì)連續(xù)Pi之間有且僅有一個(gè)Pi-1，且Pi-1與緊后Pi加工相同工件。充分性證得。

必要性證明。因?yàn)镾是機(jī)器人活動(dòng)調(diào)度，那么依據(jù)多度調(diào)度定義[16]，S中，Pi的個(gè)數(shù)與Pi-1的個(gè)數(shù)一樣多。又因?yàn)槊繉?duì)連續(xù)Pi之間有且僅有一個(gè)Pi-1，意思是Pi與Pi-1交替出現(xiàn)。那么每對(duì)連續(xù)Pi-1之間有且僅有一個(gè)Pi。由于是周期調(diào)度，且Pi-1與緊后Pi加工相同工件。保證機(jī)器人運(yùn)行順序和工件加工順序可行。依據(jù)性質(zhì)2，必要性成立。性質(zhì)3證畢。

性質(zhì)2和性質(zhì)3研究了阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度的充要條件。接下來闡述，什么條件下，可行機(jī)器人活動(dòng)調(diào)度，經(jīng)過一定變化后得到的機(jī)器人活動(dòng)調(diào)度仍然是可行的。

性質(zhì)4S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度。如果job(σ(i))≠job(σ(i+1))且|Q(σ(i))-Q(σ(i+1))|>1，那么交換τσ(i)與τσ(i+1)后，機(jī)器人活動(dòng)調(diào)度S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是可行的。

證明由于S是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度，因此，S滿足性質(zhì)2。也就是說，τσ(i)左邊最靠近τσ(i)的機(jī)器人活動(dòng)τσ(s)對(duì)應(yīng)起始工作站為PQ(σ(s))，且Q(σ(s))+1=Q(σ(i))和job(σ(i))=job(σ(s))成立；同理τσ(i)，右邊最靠近τσ(i)的機(jī)器人活動(dòng)τσ(w)對(duì)應(yīng)起始工作站為PQ(σ(w))，且Q(σ(w))+1=Q(σ(i))成立。由于τσ(i)與τσ(i+1)對(duì)應(yīng)工作站不相鄰，即Q(σ(w))≠Q(mào)(σ(i+1))，那么τσ(i+1)同樣位于τσ(s)與τσ(w)之間，當(dāng)τσ(i)與τσ(i+1)交換后，τσ(i)同樣位于τσ(s)與τσ(w)之間，且有job(σ(i))=job(σ(s))。故，依據(jù)性質(zhì)2，性質(zhì)4成立。性質(zhì)4證畢。

依據(jù)性質(zhì)4，可以得到性質(zhì)5。

性質(zhì)5S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度。如果job(σ(i))≠job(σ(i-1))且|Q(σ(i))-Q(σ(i-1))|>1，那么交換τσ(i)與τσ(i-1)后，機(jī)器人活動(dòng)調(diào)度S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是可行的。

性質(zhì)4和性質(zhì)5通過交換相鄰機(jī)器人活動(dòng)，得到可行機(jī)器人活動(dòng)調(diào)度。在這個(gè)過程中，工件加工順序不變，機(jī)器人運(yùn)行順序改變。性質(zhì)6工件加工順序改變，機(jī)器人運(yùn)行順序不變。

性質(zhì)6S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度。如果(τσ(e0),τσ(e1),…,τσ(em))與(τσ(g0),τσ(g1),…,τσ(gm))分別是兩個(gè)不同工件的所有機(jī)器人活動(dòng)，且Q(σ(ef))=Q(σ(gf))(0≤f≤m)，依次交換τσ(ef)與τσ(gf)后，得到的機(jī)器人活動(dòng)調(diào)度仍然可行。

證明S=(τ0,τσ(1),…,τσ(i),τσ(i+1),…,τσ(n(m+1)-1))是阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行機(jī)器人活動(dòng)調(diào)度，因此滿足性質(zhì)2的條件。又因?yàn)镼(σ(ef))=Q(σ(gf))(0≤f≤m)，所以依次交換τσ(ef)與τσ(gf)后，機(jī)器人運(yùn)行順序不變，同樣滿足性質(zhì)2的條件，故，得到的機(jī)器人活動(dòng)調(diào)度是可行的。性質(zhì)6證畢。

3 結(jié)論

實(shí)際生產(chǎn)過程中，機(jī)器人制造單元調(diào)度問題具有阻塞約束和混流生產(chǎn)組織形式是常見情形。本文針對(duì)阻塞混流生產(chǎn)機(jī)器人制造單元調(diào)度問題的可行解基本性質(zhì)進(jìn)行了研究，得到以下結(jié)論：利用機(jī)器人活動(dòng)概念，將二維調(diào)度問題轉(zhuǎn)化為一維調(diào)度問題，降低了問題難度；重點(diǎn)分析了可行機(jī)器人活動(dòng)調(diào)度的性質(zhì)。

通過可行機(jī)器人活動(dòng)調(diào)度性質(zhì)研究，為算法設(shè)計(jì)提供了一條有效途徑。利用可行機(jī)器人活動(dòng)調(diào)度性質(zhì)，可以設(shè)計(jì)有效的進(jìn)化算子，提升進(jìn)化算法求解效率，改善進(jìn)化算法收斂速度。