顧斌斌， 明全華， 張翼飛

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

0 引 言

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

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

1 問題描述

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

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

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

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

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

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

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

βMi≤A,?Mi

(1)

式(1)表示單元內(nèi)設(shè)備可并行處理多個(gè)工件，式中：β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上加工開始的時(shí)間節(jié)點(diǎn)；Tbkas為機(jī)器人開始執(zhí)行工件a搬運(yùn)任務(wù)s的時(shí)間節(jié)點(diǎn)；T(Ikks,Mi)為機(jī)器人從開始執(zhí)行搬運(yùn)任務(wù)s時(shí)其所在的設(shè)備Ikks移動(dòng)到Mi所用時(shí)間；T(Mi,Ma)為機(jī)器人從設(shè)備Mi移動(dòng)到Ma所用時(shí)間。

(3)

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

KRk0=M1Rk

(4)

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

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

(5)

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

Tekas-Tbkas=δkasTks,?a,s

(6)

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

TeaMi=TbaMi+Taj,?a,M

(7)

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

(8)

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

(9)

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

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

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

(10)

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

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

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

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

(11)

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

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

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

(12)

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

3 算法設(shè)計(jì)

3.1 編 碼

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

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

3.2 選擇策略

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

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

(13)

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

(14)

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

3.3 交叉算子

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

圖3 交叉算子修正方法

3.4 變異算子

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

圖4 變異算子

3.5 算法流程

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

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

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

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

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

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

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

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

(9) 若d

(10) 若d=D且k

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

4 實(shí)例分析

4.1 實(shí)例描述

以某企業(yè)動(dòng)力電池生產(chǎn)線容量確定單元為例，對(duì)其進(jìn)行設(shè)備加工任務(wù)分配、機(jī)器人任務(wù)分配和路徑優(yōu)化。容量確定單元由1 V放電、容量確定前充放電、容量確定、靜置、補(bǔ)充電和分揀等6道工序構(gòu)成，該單元因各工序加工時(shí)間較短，設(shè)備數(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臺(tái)，以完工120件電池盒為計(jì)算目標(biāo)。

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

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

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

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

4.3 結(jié)果分析

通過MATLAB軟件進(jìn)行遺傳算法編程和運(yùn)算，對(duì)移動(dòng)機(jī)器人搬運(yùn)過程進(jìn)行運(yùn)算，得出不同機(jī)器人分配方案目標(biāo)函數(shù)值及其收斂情況。6種機(jī)器人服務(wù)范圍分配方案的目標(biāo)函數(shù)值曲線如圖5所示，顯示了6種不同的分配方案對(duì)最終所需調(diào)度時(shí)間的影響。圖中曲線的目標(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è)備位置和加工時(shí)間的不同，對(duì)分段機(jī)器人服務(wù)范圍進(jìn)行規(guī)劃，通過一定算法關(guān)系結(jié)合多因素決策以取得良好的效果。

5 結(jié) 語

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