多工序加工單元的移動機(jī)器人調(diào)度優(yōu)化

顧斌斌， 明全華， 張翼飛

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

0 引 言

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

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

1 問題描述

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

圖1 單軌多移動機(jī)器人調(diào)度模型

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

2 數(shù)學(xué)模型

為便于問題描述，現(xiàn)將一些基本符號進(jìn)行說明，如表1所示。

表1 模型相關(guān)符號及其意義

約束模型構(gòu)建如下：

βMi≤A,?Mi

(1)

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

TbaMi≥Tbkas+T(Ikks,Mi)

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

(2)

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

(3)

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

KRk0=M1Rk

(4)

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

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

(5)

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

Tekas-Tbkas=δkasTks,?a,s

(6)

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

TeaMi=TbaMi+Taj,?a,M

(7)

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

(8)

根據(jù)上述約束模型，目標(biāo)函數(shù)為

(9)

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

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

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

(10)

式中：T(Ikks,Baj)為機(jī)器人從開始執(zhí)行搬運任務(wù)s時其所在的設(shè)備Ikks移動到工件a的緩沖區(qū)Bj所用時間；T(Baj,Ma)為機(jī)器人從工件a緩沖區(qū)Bj移動到工件a的目標(biāo)設(shè)備Ma所用時間；βMa為設(shè)備Ma的可加工數(shù)量；

若存在目標(biāo)設(shè)備剩余加工容量等于0，設(shè)備放棄上料任務(wù)，等待完成下一下料任務(wù)后執(zhí)行該上料任務(wù)。

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

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

(11)

式中：Iaks為機(jī)器人開始執(zhí)行任務(wù)s時工件a所在的設(shè)備；T(Ikks,Iaks)為機(jī)器人從開始執(zhí)行任務(wù)s時其所在的設(shè)備Ikks移動到Iaks所用時間；T(Iaks,Ma)為機(jī)器人從Iaks移動到工件a的目標(biāo)設(shè)備Ma所用時間。

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

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

(12)

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

3 算法設(shè)計

3.1 編 碼

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

圖2 機(jī)器人編碼示例

3.2 選擇策略

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

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

(13)

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

(14)

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

3.3 交叉算子

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

圖3 交叉算子修正方法

3.4 變異算子

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

圖4 變異算子

3.5 算法流程

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

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

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

(4) 計算個體目標(biāo)函數(shù)值。

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

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

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

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

(9) 若d

(10) 若d=D且k

(11) 解碼最優(yōu)解，給出最小調(diào)度時間。

4 實例分析

4.1 實例描述

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

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

4.2 容量確定單元服務(wù)范圍分配方案

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

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

表3 各設(shè)備間機(jī)器人行駛時間 s

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

表4 機(jī)器人服務(wù)范圍分配方案

4.3 結(jié)果分析

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

圖5 不同分配方案下目標(biāo)函數(shù)值

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

圖6 最優(yōu)方案目標(biāo)函數(shù)收斂情況

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

5 結(jié) 語

根據(jù)實際生產(chǎn)中移動機(jī)器人的調(diào)度規(guī)則，研究單軌約束多機(jī)器人模式下機(jī)器人服務(wù)范圍分配方案對調(diào)度的影響，建立單軌約束下的多移動機(jī)器人調(diào)度模型，以最小化調(diào)度任務(wù)時間為目標(biāo)，引入遺傳算法，采用MATLAB求解獲得優(yōu)化的調(diào)度方案，驗證了所設(shè)計的調(diào)度方法的有效性。