求解阻塞混流生產機器人制造單元調度問題的分支定界算法

趙曉飛，郭秀萍

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

0 引言

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

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

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

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

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

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)為常數，工件類型不同，加工時間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。執行ri, j耗時di, j，也稱為有載移動時間，為常數。cq,k是機器人在Pq與Pk之間不搬運工件移動耗費的時間(0≤q,k≤m+1)，即空載移動時間。目標是最小化兩個相鄰MPS中第一個工件進入機器人制造單元所經過的時間，即加工周期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)是三角不等式。

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

M表示足夠大的正實數。

數學模型如下。

目標函數:

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 基礎理論

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

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

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

(15)

依據定義1，τi+(m+1)(j-1)與ri, j一一對應，因此，每個ri, j的開始時間也是執行機器人活動τi+(m+1)(j-1)的開始時間。應用機器人活動，將工件加工排序和機器人運行排序轉化為機器人活動排序。例如，由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)的關系

優化阻塞混流生產機器人制造單元調度問題，實質是對ri, j的開始時間排序。依據定義1，對ri, j的開始時間排序，可以轉化為對機器人活動τi+(m+1)(j-1)調度。因為本文考慮周期調度，總認為每個機器人活動調度中，τ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 滿足以下條件的機器人活動調度稱為可行機器人活動調度：

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

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

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

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

3 順序插入規則

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

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

阻塞混流生產機器人制造單元調度問題是阻塞作業車間機器人制造單元調度問題的特殊情形，故本文以文獻[16]提出規則為基礎，提出了順序插入規則構建阻塞混流生產機器人制造單元調度問題可行解。順序插入規則的條件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(h)，且Q(f)=m，job(f)=job(h)，但τf-1∈Rtodo。

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

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

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

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

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

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

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

例如，考慮表1給出的機器人活動。初始狀態：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未排，違反流水線性質；如果排τ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未排，違反流水線性質；如果排τ5或τ10，違反文獻[16]給出的條件2；如果排τ6或τ11，機器人從P0搬運J2或J3，但是P1被J1占用，違反文獻[16]給出的條件1；如果插入τ7或τ8，雖然滿足文獻[16]給出的條件1和條件2，但是不滿足條件5；如果插入τ14，雖然滿足文獻[16]給出的條件1和條件2，但是不滿足條件3。依據順序插入規則，得可行機器人活動調度為：S2=(τ0,τ9,τ1,τ2,τ10,τ11,τ3,τ4,τ12,τ5,τ13,τ14,τ6,τ7,τ8)。以上可行機器人活動調度構建過程如圖1。

圖1 可行機器人活動調度構建過程示意圖

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

表2 理論解個數與可行解個數比較

4 分支定界算法

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

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

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

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

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

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

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

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

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

5 結果比較

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

本文借鑒文獻[17]中算例生成方式。ai, j為整數，且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表示給定時間內未求得可行解；CT表示計算時間，單位為s。

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

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

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

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

6 結語

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

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