求解阻塞混流生產(chǎn)機器人制造單元調(diào)度問題的分支定界算法

趙曉飛，郭秀萍

(1.西南交通大學 經(jīng)濟管理學院，成都 610031； 2.重慶文理學院 經(jīng)濟管理學院，重慶402160)(*通信作者電子郵箱guoxiuping0029@sina.com)

0 引言

機器人制造單元是一種先進生產(chǎn)系統(tǒng)，廣泛應用于機械制造、電路板印刷(Printed Circuit Board, PCB)以及半導體制造等行業(yè)[1-4]。典型機器人制造單元由一個輸入裝置、一個輸出裝置、多個工作站以及一個由計算機控制的機器人組成。

由于市場需求由大批量、少品種向小批量、多品種轉(zhuǎn)變，且機器人制造單元技術改進，使得機器人制造單元由生產(chǎn)同類型工件向生產(chǎn)多類型工件轉(zhuǎn)換[5-6]。為了合理生產(chǎn)多類型工件，提高系統(tǒng)效率，將待加工的多類型工件組成一個最小工件集(Minimum Part Set, MPS)，按照混流方式周期生產(chǎn)。

由于文獻[7]證明了工作站數(shù)大于2的混流生產(chǎn)機器人制造單元調(diào)度問題是非確定性多項式(Non-Deterministic Polynomial， NP)難的，因此以工作站個數(shù)為分類標準，將該問題分為兩大類：一類是工作站數(shù)等于2；一類是工作站數(shù)大于2。工作站數(shù)等于2時，該問題可以轉(zhuǎn)化為推銷員旅行問題(Travel Saleman Problem, TSP)[8-10]，易于求解，但僅限于1-度生產(chǎn)策略情形。工作站數(shù)等于3時，研究者通過枚舉機器人運行順序[7,9,11-12]，設計了多種啟發(fā)式方法，但這些方法沒能同時優(yōu)化工件加工順序和機器人運行順序。文獻[13]首次同時優(yōu)化了工件加工順序和機器人運行順序，并證實了同時優(yōu)化工件加工順序和機器人運行順序優(yōu)于固定一個順序優(yōu)化另一個順序，但該研究前提是工作站數(shù)等于3。文獻[14-15]在文獻[13]研究基礎上，首次設計化學反應優(yōu)化求解該問題，得到了更好解。

以上優(yōu)化方法僅適用于工作站數(shù)為2或3時的阻塞混流生產(chǎn)機器人制造單元調(diào)度問題，很難推廣到更多工作站情形；因此，設計新的優(yōu)化方法，同時優(yōu)化機器人運行順序和工件加工順序，求解阻塞混流生產(chǎn)機器人制造單元調(diào)度問題就顯得尤為重要。文獻[16]研究了阻塞單件車間(Job-shop)機器人制造單元調(diào)度問題，給出了可行解構建條件，同時優(yōu)化了工件加工順序和機器人活動順序。由于混流生產(chǎn)和單件車間的不同，以文獻[16]研究為基礎，本文首先構建了工作站編號與工件編號與機器人活動之間的數(shù)量關系；其次，提出了順序插入規(guī)則修正文獻[16]給出的可行解構建條件；第三，文獻[16]限定了跨周期加工工件數(shù)，本文放松了該假設，認為跨周期加工工件理論上來說可以有無限多個，增加了順序插入規(guī)則適用性。

本文針對阻塞混流生產(chǎn)機器人制造單元調(diào)度問題，構建了順序插入規(guī)則，生成可行解。以順序插入規(guī)則為基礎，構建了分支定界算法求解該問題。

1 問題描述與模型構建

本文研究的機器人制造單元由m個工作站P1,P2,…,Pm；一個由計算機控制的物料搬運機器人；一個輸入裝置P0和一個輸出裝置Pm+1組成。由n個多類型工件J1,J2,…,Jn組成的MPS同時在機器人制造單元上被加工。Jj(1≤j≤n)從P0進入機器人制造單元，依次在m個工作站P1,P2,…,Pm上加工，最后從Pm+1離開機器人制造單元，不考慮重入和平行工作站情形，不考慮加工中斷情形，且同一時間，每個工作站最多加工一個工件。Jj在Pi上的加工時間ai, j(1≤i≤m，1≤j≤n)為常數(shù)，工件類型不同，加工時間ai, j一般不同。機器人負責工件在工作站之間、輸入裝置和工作站以及工作站和輸出裝置之間的移動。同一時刻，機器人最多能搬運一個工件。機器人移動ri, j包含3步操作：1)機器人從Pi卸下Jj；2)機器人搬運Jj從Pi到Pi+1；3)機器人將Jj裝入Pi+1(0≤i≤m，1≤j≤n)，其開始時間為ti, j。執(zhí)行ri, j耗時di, j，也稱為有載移動時間，為常數(shù)。cq,k是機器人在Pq與Pk之間不搬運工件移動耗費的時間(0≤q,k≤m+1)，即空載移動時間。目標是最小化兩個相鄰MPS中第一個工件進入機器人制造單元所經(jīng)過的時間，即加工周期T。另外本文假設以下兩式成立：

dh, j≥ch,h+1； 1≤j≤n,0≤h≤m

(1)

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

(2)

式(1)表示相鄰工作站之間，有載移動時間不小于空載移動時間；式(2)是三角不等式。

為了便于數(shù)學模型構建，給出以下符號定義。

M表示足夠大的正實數(shù)。

數(shù)學模型如下。

目標函數(shù):

MinimizeT

約束：

1≤i≤m,1≤j≤n

(3)

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

(4)

(5)

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

(6)

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

(7)

ti, j≥d0,1+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)保證了工件加工時間約束；約束(4)和約束(5)確保工作站容量約束不被違反；約束(6)和約束(7)避免機器人沖突；約束(8)給出了ri, j的開始時間不小于r0,1的開始時間；約束(9)給出了加工周期的下界；約束(10)和(11)界定了每個周期總是從r0,1開始；約束(12)和(13)是非負約束；約束(14)是0- 1變量約束。

2 基礎理論

針對混流生產(chǎn)機器人制造單元調(diào)度問題，文獻[8]證明了1-度機器人運行順序共有m!個，因此，隨著工作站個數(shù)增多，通過枚舉機器人運行順序優(yōu)化工件加工順序的求解策略基本不可行；當然，如果枚舉工件加工順序，優(yōu)化機器人運行順序也僅在理論上有可能。為此，構建混流生產(chǎn)機器人制造單元調(diào)度問題的可行解就成為求解該問題的關鍵。為了構建可行解，先給出機器人活動定義。

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

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

(15)

依據(jù)定義1，τi+(m+1)(j-1)與ri, j一一對應，因此，每個ri, j的開始時間也是執(zhí)行機器人活動τi+(m+1)(j-1)的開始時間。應用機器人活動，將工件加工排序和機器人運行排序轉(zhuǎn)化為機器人活動排序。例如，由4個工作站P1、P2、P3、P4、一個機器人、一個輸入裝置P0和一個輸出裝置P5組成機器人制造單元。MPS由工件J1、J2、J3組成。ri, j與τi+(m+1)(j-1)的關系如表1所示。

表1 ri, j與τi+(m+1)(j-1)的關系

優(yōu)化阻塞混流生產(chǎn)機器人制造單元調(diào)度問題，實質(zhì)是對ri, j的開始時間排序。依據(jù)定義1，對ri, j的開始時間排序，可以轉(zhuǎn)化為對機器人活動τi+(m+1)(j-1)調(diào)度。因為本文考慮周期調(diào)度，總認為每個機器人活動調(diào)度中，τ0排第一個，因此，S=(τ0,τσ(1),τσ(2),…,τσ(n(m+1)-1))為問題的解，其中σ是{1,2,…,n(m+1)-1} → {1,2,…,n(m+1)-1}的置換。為了便于表述，假設job(h)為機器人活動τh搬運的工件；Q(h)為機器人活動τh起始工作站對應下標(0≤h≤n(m+1))。為了判斷解S是否可行，給出定義2。

定義2 滿足以下條件的機器人活動調(diào)度稱為可行機器人活動調(diào)度：

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

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

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

依據(jù)表1，解S1=(τ0,τ12,τ13,τ1,τ2,τ5,τ14,τ6,τ3,τ4,τ7,τ10,τ8,τ9,τ11)是可行機器人活動調(diào)度。

3 順序插入規(guī)則

定義2可以判斷給定解是否可行，但不能構建可行解，因此，本章給出構建可行解的規(guī)則：順序插入規(guī)則。

文獻[16]給出了阻塞作業(yè)車間機器人制造單元調(diào)度問題可行解構建規(guī)則，但是由于作業(yè)車間和混流生產(chǎn)的區(qū)別，僅利用文獻[16]給出的規(guī)則會產(chǎn)生不可行解。令Rdone為部分可行機器人活動集合，Rtodo為未排序機器人活動集合。例如：利用文獻[16]提出規(guī)則，Rdone={τ0,τ9,τ14}滿足可行性要求；但是，Rdone={τ0,τ9,τ14}不滿足定義2中條件3)，故Rdone={τ0,τ9,τ14}不是部分可行機器人活動調(diào)度。

阻塞混流生產(chǎn)機器人制造單元調(diào)度問題是阻塞作業(yè)車間機器人制造單元調(diào)度問題的特殊情形，故本文以文獻[16]提出規(guī)則為基礎，提出了順序插入規(guī)則構建阻塞混流生產(chǎn)機器人制造單元調(diào)度問題可行解。順序插入規(guī)則的條件1、條件2由文獻[16]提出，余下條件下文給出，滿足這6個條件之一的Rdone是不可行的。

條件1 在Rtodo中任意選擇機器人活動τf、τf-1存在，且job(f)=job(f-1)，將τf插入Rdone末端，若對任意τh、τh+1存在，有job(h)=job(h+1)和Q(f-1)=Q(h)成立，但τh∈Rdone而τh+1∈Rtodo或τh+1∈Rdone而τf-1∈Rtodo。

條件2 在Rtodo中任意選擇機器人活動τf，且τf+1存在，job(f)=job(f+1)，將τf插入Rdone末端，若對任意τh，τh+1存在，有job(h)=job(h+1)和Q(f)=Q(h)≠m成立，但τh∈Rdone而τh+1∈Rtodo或τf+1∈Rdone而τh∈Rtodo。

條件3 在Rtodo中任意選擇機器人活動τf，將τf插入Rdone末端，對任意τh∈Rdone，若Q(f)=Q(h)=m，但τf-1∈Rtodo。

條件4 在Rtodo中任意選擇機器人活動τf，將τf插入Rdone末端，對任意τh∈Rdone，若Q(f)≠Q(mào)(h)，且Q(f)=m，job(f)=job(h)，但τf-1∈Rtodo。

條件5 在Rtodo中任意選擇機器人活動τf，將τf插入Rdone末端，對任意τh∈Rdone，若Q(f)≠Q(mào)(h)，且Q(h)=m，job(f)=job(h)，但τh-τf

條件6 若Jδ(1),Jδ(2),…,Jδ(l)(l

條件3、條件4和條件5關注工作站是否沖突，條件6關注跨周期加工工件的加工順序是否一致。條件3保證兩個連續(xù)的Pm之間，一定存在一個Pm-1；條件4和條件5確保混流生產(chǎn)性質(zhì)不被違反。

利用順序插入規(guī)則構建可行解的步驟如下：

步驟1 令Rdone={τ0}，Rtodo包含余下機器人活動，假設除P1外，所有工作站為空。

步驟2 利用順序插入規(guī)則，選擇插入Rdone末端，并使得Rdone是部分可行的機器人活動，從Rtodo中刪除該機器人活動。

步驟3 重復步驟2，直到Rtodo為空集。

例如，考慮表1給出的機器人活動。初始狀態(tài)：Rtodo={τ1,τ2,τ3,τ4,τ5,τ6,τ7,τ8,τ9,τ10,τ11,τ12,τ13,τ14}，Rdone={τ0}。假設工作站Pi為空(2≤i≤4)。

接下來，選擇Rtodo中所有可能機器人活動插入Rdone中第2個位置，可能的部分可行機器人活動分別為：{τ0,τ1}、{τ0,τ7}、{τ0,τ8}、{τ0,τ9}、{τ0,τ12}、{τ0,τ13}、{τ0,τ14}。余下機器人活動不能排在Rdone中第2個位置。因為，如果排τ2,τ3,τ4中的一個，τ1未排，違反流水線性質(zhì)；如果排τ6或τ11，機器人從P0搬運J2或J3，但是P1被J1占用，違反文獻[16]給出的條件1；如果排τ5或τ10，違反文獻[16]給出的條件2。

然后，令Rtodo={τ1,τ2,τ3,τ4,τ5,τ6,τ7,τ8,τ10,τ11,τ12,τ13,τ14},Rdone={τ0,τ9}。此時P1被占用，其余工作站為空。從Rtodo中選擇所有可能機器人活動插入Rdone中第3個位置，可能的部分可行機器人活動分別為：{τ0,τ9,τ1}、{τ0,τ9,τ12}、{τ0,τ9,τ13}。余下機器人活動不能排在第3個位置。因為，如果排τ2,τ3,τ4中的一個，τ1未排，違反流水線性質(zhì)；如果排τ5或τ10，違反文獻[16]給出的條件2；如果排τ6或τ11，機器人從P0搬運J2或J3，但是P1被J1占用，違反文獻[16]給出的條件1；如果插入τ7或τ8，雖然滿足文獻[16]給出的條件1和條件2，但是不滿足條件5；如果插入τ14，雖然滿足文獻[16]給出的條件1和條件2，但是不滿足條件3。依據(jù)順序插入規(guī)則，得可行機器人活動調(diào)度為：S2=(τ0,τ9,τ1,τ2,τ10,τ11,τ3,τ4,τ12,τ5,τ13,τ14,τ6,τ7,τ8)。以上可行機器人活動調(diào)度構建過程如圖1。

圖1 可行機器人活動調(diào)度構建過程示意圖

理論上，阻塞混流生產(chǎn)機器人制造單元調(diào)度問題解的個數(shù)為(n(m+1)-1)!。表2給出了小規(guī)模時理論解個數(shù)與可行解個數(shù)的比較。從表2可以發(fā)現(xiàn)，利用順序插入規(guī)則生成可行解的個數(shù)遠遠小于解的個數(shù)，可以有效減少搜索空間。

表2 理論解個數(shù)與可行解個數(shù)比較

4 分支定界算法

分支定界算法兩個關鍵點是：剪枝策略與上界的確定。首先，利用文獻[16]給出的下界計算方法，選擇使得部分可行機器人活動調(diào)度下界最小的節(jié)點繼續(xù)分支，即通過深度優(yōu)先搜索找到問題的一個上界；然后，在分支過程中，再次利用文獻[16]給出的下界計算方法，計算部分可行機器人活動的下界；最后，利用上界和下界進行剪枝，繼續(xù)搜索，求得該問題的最好解。具體步驟如下：

步驟1 令Rdone={τ0}，Rtodo包含余下機器人活動，假設除P1外，所有工作站為空。

步驟2 利用順序插入規(guī)則，選擇插入Rdone末端，并使得Rdone是部分可行的所有機器人活動，組成集合Ω。

步驟3 利用文獻[16]給出的下界計算方法，計算集合Ω中每個機器人活動插入Rdone后的下界。

步驟4 選擇最小下界對應的機器人活動插入Rdone末端，從Rtodo中刪除該機器人活動。

步驟5 重復步驟2～4，直到Rtodo為空集。計算獲得可行解的目標函數(shù)值，作為分支定界算法的上界，記為當前最好解。

步驟6 利用回溯算法和文獻[16]給出的下界計算方法，計算其他分支的下界：若下界大于上界，則剪枝；否則，利用順序插入規(guī)則，繼續(xù)分支。

步驟7 若得到的目標函數(shù)值小于當前最好解，更新當前最好解。

步驟8 若搜索完所有分支或滿足算法終止條件，輸出最優(yōu)解或滿意解。

5 結(jié)果比較

以順序插入規(guī)則構建的分支定界(Branch and Bound, BB)算法利用C++語言編程，在CPU為Intel Core i5- 4460 CPU@ 3.20 GHz，內(nèi)存為8 GB的環(huán)境下運行。運行時間為以秒計的CPU時間。終止條件為CPU時間600 s。

本文借鑒文獻[17]中算例生成方式。ai, j為整數(shù)，且ai, j～U[20,99](1≤i≤m,1≤j≤n)；dh, j=6(1≤j≤n,0≤h≤m)；cq,k=4|q-k|(0≤q,k≤m+1)。其中：inf表示給定時間內(nèi)未求得可行解；CT表示計算時間，單位為s。

表3給出了n為4、5、6時，m為3、4時，分支定算法(BB)和CPLEX12.5的計算結(jié)果比較。在表3中，P表示問題，例如J6P1表示6個工件時的第一個問題。給定m值和n隨機生成5個算例，每個算例每種算法運行10次，取平均計算時間和平均目標函數(shù)值進行比較。從表3中可以發(fā)現(xiàn)，兩種方法都能在合理的時間求得最優(yōu)解，且隨著工件數(shù)或工作站數(shù)增多，計算時間變長，證實了算法的有效性。

表3 不同m值時兩種算法的運行時間和目標函數(shù)值對比

表4給出了n∈[7,15]且為整數(shù)；m∈[4,20]且為偶數(shù)時，分支定算法和CPLEX12.5的計算結(jié)果比較。每個算例每種算法運行10次，取平均計算時間和平均目標函數(shù)值進行比較。

在總共81個算例中，CPLEX給出了14個算例的可行解，占比17.28%，隨著算例規(guī)模變大，在給定時間內(nèi)不能求得可行解；而分支定界算法給出了所有算例的可行解。CPLEX給出了兩個算例的最優(yōu)解，分別為n=7，m=4和n=8，m=4；分支定界算法給出了n=7，m=4算例的最優(yōu)解。兩種方法都給出解的算例中，僅有兩個算例，分別為n=7，m=4和n=7，m=8，是分支定界算法的解不劣于CPLEX?？偟膩碚f，小規(guī)模算例時，CPLEX的求解效率和精度高于分支定界算法，當算例規(guī)模變大，分支定界算法的效率高于CPLEX，因此，利用順序插入規(guī)則構建的分支定界算法具有求解大規(guī)模問題的能力。

6 結(jié)語

本文針對阻塞混流生產(chǎn)機器人制造單元調(diào)度問題，利用機器人活動將工件加工順序和機器人運行順序合二為一，將二維調(diào)度問題轉(zhuǎn)化為一維調(diào)度問題。為了同時優(yōu)化該問題的工件加工順序和機器人運行順序，提出了順序插入規(guī)則構建可行解。以順序插入規(guī)則為基礎，構建了分支定界算法。通過計算隨機生成的算例表明，分支定界算法相對于CPLEX在求解大規(guī)模問題時更有優(yōu)勢。后續(xù)研究可以從以下兩方面考慮：一是研究分支定界算法的剪枝策略和下界計算方式，提高算法效率；一是利用順序插入規(guī)則構建可行解，設計啟發(fā)式算法或智能優(yōu)化算法，提高解的質(zhì)量。

表4 不同n值時兩種算法的運行時間和目標函數(shù)值比較