多工序加工單元的移動機器人調度優化

顧斌斌， 明全華， 張翼飛

(1.滬東中華造船(集團)有限公司， 上海200129；2.中國船級社質量認證公司 上海分公司， 上海200135)

0 引 言

在多工序加工單元中，實現物流搬運的方式多種多樣，其中移動機器人以其高自動化、高柔性等優點得到廣泛應用。目前，國內外學者對機器人調度問題做了許多研究。沈博聞等[1]研究基于機器人的自動化倉儲模式，建立一個靈活可重構的倉儲空間模型，制訂適用于倉儲物流的機器人運行規則，分解物流任務，給出機器人調度方法，修正其算法實現在特殊道路約束下的路徑規劃，進而加入時序建立時間空間地圖進行三維路徑規劃。雷衛東等[2]研究一類帶時間窗口的自動化混流生產線的工件排序和機器人作業排序問題；基于對研究問題的分析，考慮處理時間窗口約束、機器人搬運能力約束和工作站能力約束，使用混合整數規劃方法建立此類問題的通用數學模型，并通過自動化印刷電路板生產線實例和大量隨機生成算例驗證所建模型。DANG等[3]研究單機器人的上料順序問題，提出一種基于遺傳算法的啟發式算法，并應用葉輪生產線驗證方法的有效性。

由上述文獻可以看出：先進的調度算法是解決機器人調度問題的關鍵。對于采用單軌多機器人調度的多工序加工單元，不同工序的加工時間、設備數量及上下料點與不同設備間物理位置的差異，使得各設備間加工任務的合理配置存在較大意義。以某企業動力電池生產線容量確定單元為例，以最小化調度時間為目標，建立多移動機器人調度優化模型，并設計遺傳算法求解得出合理的分配方案，提高調度效率。

1 問題描述

在一個多移動機器人多工序動力電池生產單元內，共有同類型的i個產品需依次經過j道工序完成加工。各工序加工時間不一、設備數量不一，并按工序順序沿機器人軌道依次排開。單元由1個上料口、1個下料口、2個機器人及設備和緩沖區構成。工件由上料口Din進入，由機器人Rk負責在各工序間流轉，最終由下料口Dout移除單元。單軌多移動機器人調度模型如圖1所示，其中Baj表示工件a的緩沖區編號Bj,Mai表示工件a的目標設備Mi。

圖1 單軌多移動機器人調度模型

從實際生產情況出發，對研究問題做如下假設：(1)機器人行駛速度一定，且各臺移動機器人速度一致；(2)機器人單次只能響應1個任務，1次只能抓取1個產品；(3)機器人服務設備時停靠點確定，即各設備、上下料點、緩沖區間的運輸距離已定；(4)機器人抓取料件后若下一工序存在空閑設備且在服務范圍內，則移動機器人直接放料至該設備，否則放料至相應緩沖區；(5)機器人在完成任務后可直接響應下一任務并前往相應位置；(6)每道工序有且僅有一個緩沖區；(7)緩沖區由傳送帶構成，且緩沖區容量不影響移動機器人調度；(8)移動機器人在取料后直接響應緩沖區上料任務。

2 數學模型

為便于問題描述，現將一些基本符號進行說明，如表1所示。

表1 模型相關符號及其意義

約束模型構建如下：

βMi≤A,?Mi

(1)

式(1)表示單元內設備可并行處理多個工件，式中：βMi為設備Mi的可加工數量；A為設備最多能夠并行處理的工件數量。

TbaMi≥Tbkas+T(Ikks,Mi)

+T(Mi,Ma),?M,a,s

(2)

式(2)表示設備需在機器人完成上料任務后開始充放電，式中：TbaMi為工件a在設備Mi上加工開始的時間節點；Tbkas為機器人開始執行工件a搬運任務s的時間節點；T(Ikks,Mi)為機器人從開始執行搬運任務s時其所在的設備Ikks移動到Mi所用時間；T(Mi,Ma)為機器人從設備Mi移動到Ma所用時間。

(3)

式(3)表示機器人單次只能抓取1個工件，式中：δkas為機器人Rk執行工件a搬運任務s的過程。

KRk0=M1Rk

(4)

式(4)表示機器人起始位置在其服務范圍的首個設備位置，式中：KRk0為機器人Rk的起始位置；M1Rk為機器人Rk服務范圍內的首個設備位置。

Tbkas+Tkas≥TeaMi,?M,a,s

(5)

式(5)表示機器人需在設備加工完成后開始執行取料任務，式中：Tkas為機器人執行搬運任務s時，裝載工件a前設備所用時間；TeaMi為工件a在設備Mi上加工完成的時間節點。

Tekas-Tbkas=δkasTks,?a,s

(6)

式(6)表示搬運任務結束時間是開始搬運工件i的時間加上搬運時間，式中：Tekas為機器人完成工件a搬運任務s的時間節點；Tks為機器人執行搬運任務s所用時間。

TeaMi=TbaMi+Taj,?a,M

(7)

式(7)表示工件完工時間等于開始時間加上加工時間，式中：Taj為工件a在工序j上的加工時間。

(8)

根據上述約束模型，目標函數為

(9)

當機器人有上料任務時，若存在目標設備剩余加工容量不為0，則完成一次搬運任務所需時間是機器人從當前位置移至上料緩沖區取料的時間加上從上料區移至目標設備的時間，如式(10)所示：

δkasTks=T(Ikks,Baj)+T(Baj,Ma),

?a,s,?as=1,βMa>0

(10)

式中：T(Ikks,Baj)為機器人從開始執行搬運任務s時其所在的設備Ikks移動到工件a的緩沖區Bj所用時間；T(Baj,Ma)為機器人從工件a緩沖區Bj移動到工件a的目標設備Ma所用時間；βMa為設備Ma的可加工數量；

若存在目標設備剩余加工容量等于0，設備放棄上料任務，等待完成下一下料任務后執行該上料任務。

當機器人有下料任務時，若存在目標設備剩余加工容量不為0，則完成一次搬運任務所需時間是從當前位置移至目標設備的時間加上從目標設備移至下料設備的時間，如式(11)所示：

δkasTks=T(Ikks,Iaks)+T(Iaks,Ma),?a,k,s且?as=0

(11)

式中：Iaks為機器人開始執行任務s時工件a所在的設備；T(Ikks,Iaks)為機器人從開始執行任務s時其所在的設備Ikks移動到Iaks所用時間；T(Iaks,Ma)為機器人從Iaks移動到工件a的目標設備Ma所用時間。

若不存在目標設備剩余加工容量不為0，或下工序設備不在該機器人服務范圍內，則機器人完成一次搬運任務所需時間是從當前位置移至目標設備的時間加上從目標設備移至緩沖區位置的時間，如式(12)所示：

δkasTks=T(Ikks,Iaks)+T(Iaks,Baj),?a,k,s且?as=0

(12)

式中：T(Iaks,Baj)為機器人從開始執行搬運任務s時工件a所在的設備Iaks移動到工件a的緩沖區Bj所用時間。

3 算法設計

3.1 編 碼

分別對2臺機器人編碼，并將工件編號出現的次數作為機器人將該工件運至某工序對應設備的判斷依據，即若在該機器人服務范圍存在2道工序，每個工件編號需在個體中重復出現3次。當工件編號第1次出現時表示工件從上料區運至工序1設備，第2次出現時為從工序1設備運至工序2設備，第 3次出現時為從工序2設備運至緩沖區。同理，在機器人Ⅱ的編碼中，工件編號第1次出現時表示工件從緩沖區運至工序3設備，直到下料完成加工，具體表示如圖2所示。最終，通過記錄機器人依次在染色體中出現時所對應的設備，解碼得出機器人運輸路徑。

圖2 機器人編碼示例

3.2 選擇策略

考慮到所設計的算法在初代種群生成過程中存在一定隨機性，若采用傳統的輪盤賭方法進行算子選擇，則：在進化前期，目標函數值高的個體被選中概率過高，導致子代繼承過多，子代個體單一，從而使搜索陷入局部搜索；在進化后期，個體目標函數值差距較小，無法做到有效選擇[4-6]。因此，在進行輪盤賭之前，將個體的目標函數值由小到大排序，獲得個體排序序號l，按式(13)計算個體的適應度值f(i)：

f(i)=a(1-a)l-1，a∈(0,1)

(13)

按式(14)計算個體的c(i)，作為其進行輪盤賭時被選中的概率上限：

(14)

采取此方法，個體被選中的概率只取決于其在種群中的排序l與參數值a的大小，該個體與其他個體目標函數值的絕對差值大小并不會影響其遺傳到子代的數量，從而在一定程度上避免了上述問題。

3.3 交叉算子

任意選取同一機器人個體a1、a2對應位置上的工件編號i1、i2：若i1=i2，不做交叉運算；若i1≠i2，將i1與i2相互交換，從a1中隨機選出一個工件編號i2改為i1，并對a2展開與a1相同的修正。具體修正過程如圖3所示。

圖3 交叉算子修正方法

3.4 變異算子

在算法中對于每個個體，隨機生成2個[1,2Na]之間不等的整數，取這2個數位上的基因片段相互交換，產生鄰域范圍解，如圖4所示。通過多次搜索，計算每次交換前后個體的目標函數值，選出值最小的個體作為局部搜索后的最優個體。

圖4 變異算子

3.5 算法流程

(1) 設置相關參數：種群大小P，最大迭代次數D，交叉概率Pc，變異概率Pm，機器人服務范圍約束矩陣R，工序約束矩陣G，初始工件節拍Rt， 機器人在各節點間行駛時間表H。

(2) 機器人任務分配方案取k=1，迭代次數d=1，令分配方案總數kT=矩陣R的行數。

(3) 令J=R(k,:)，根據J中約束關系，結合工序約束順序生成初始種群。

(4) 計算個體目標函數值。

(5) 計算個體適應度值c(i)，并執行選擇操作。

(6) 交叉操作：以概率Pc對隨機選取的兩個個體進行交叉。

(7) 變異操作：以概率Pm對個體進行變異操作。

(8) 選出父代和子代中適應度值最高的個體作為最優個體。

(9) 若d

(10) 若d=D且k

(11) 解碼最優解，給出最小調度時間。

4 實例分析

4.1 實例描述

以某企業動力電池生產線容量確定單元為例，對其進行設備加工任務分配、機器人任務分配和路徑優化。容量確定單元由1 V放電、容量確定前充放電、容量確定、靜置、補充電和分揀等6道工序構成，該單元因各工序加工時間較短，設備數量較少而形成了多工序加工單元。各工序加工時間與設備數量如表2所示。

表2 容量確定單元工序信息

4.2 容量確定單元服務范圍分配方案

在初始參數設置上，設置交叉概率Pc=0.8，變異概率Pm=0.1。種群規模P=100，最大迭代次數D=400，機器人數量2臺，以完工120件電池盒為計算目標。

工序約束矩陣為：G={G1,G2,G3,G4,G5,G6},其中：G1={1}表示1 V放電工序，其設備為1號；G2={2,3,4,5,6,7,8}表示容量確定前充放電工序，其設備編號為2～8號；G3={9}表示靜置工序，其設備編號為9號；G4={10}表示容量確定設備，其設備編號為10號；G5={11,12,13,14}表示補充電設備，其設備編號為11～14號；G6={15}表示分揀設備，其設備編號為15號。緩沖區設備表示為：B={B1,B2,B3,B4,B5}={20,9,21,22,23}。取機器人平均速度為1 m/s，上下料抓取時間10 s。各設備間機器人行駛時間表H按表3輸入。

表3 各設備間機器人行駛時間 s

考慮到實際中各設備間距離相近，機器人只服務1臺或2臺設備意義不大，因此只考慮中間幾種分配方案，具體分配方案如表4所示，并按該關系輸入分配方案矩陣R如下：

表4 機器人服務范圍分配方案

4.3 結果分析

通過MATLAB軟件進行遺傳算法編程和運算，對移動機器人搬運過程進行運算，得出不同機器人分配方案目標函數值及其收斂情況。6種機器人服務范圍分配方案的目標函數值曲線如圖5所示，顯示了6種不同的分配方案對最終所需調度時間的影響。圖中曲線的目標函數值越小，代表該分配方案越合理，調度效率越高。

圖5 不同分配方案下目標函數值

采用第3種服務范圍分配方案，即機器人Ⅰ服務于設備1～設備8、機器人Ⅱ服務于設備9～設備16，目標函數值最小，機器人調度效率最高。方案3目標函數收斂情況如圖6所示。采用第3種分配方案，目標函數值的收斂曲線最終收斂于37 901 s。

圖6 最優方案目標函數收斂情況

由此說明，在單軌機器人規劃中，根據設備位置和加工時間的不同，對分段機器人服務范圍進行規劃，通過一定算法關系結合多因素決策以取得良好的效果。

5 結 語

根據實際生產中移動機器人的調度規則，研究單軌約束多機器人模式下機器人服務范圍分配方案對調度的影響，建立單軌約束下的多移動機器人調度模型，以最小化調度任務時間為目標，引入遺傳算法，采用MATLAB求解獲得優化的調度方案，驗證了所設計的調度方法的有效性。