孟現(xiàn)鋒，羅 勇

(鄭州大學(xué) 電氣工程學(xué)院，鄭州 450001)

含并行機(jī)器的自動(dòng)化制造單元機(jī)械手調(diào)度策略*

孟現(xiàn)鋒，羅 勇

(鄭州大學(xué) 電氣工程學(xué)院，鄭州 450001)

文章研究了風(fēng)電葉片預(yù)埋螺套智能鉆孔系統(tǒng)(簡(jiǎn)稱(chēng)智能鉆孔系統(tǒng))的機(jī)械手調(diào)度最優(yōu)策略。針對(duì)智能鉆孔系統(tǒng)中多個(gè)并行加工機(jī)器和一個(gè)機(jī)械手難以合理調(diào)配的優(yōu)化問(wèn)題，提出一種將最小公倍數(shù)周期序列和遺傳算法相結(jié)合的混合調(diào)度策略。論文首先分析了工件加工過(guò)程中機(jī)械手的動(dòng)作特點(diǎn)，建立機(jī)械手搬運(yùn)工件的最小公倍數(shù)周期序列模型。然后，設(shè)計(jì)遺傳算法求解最優(yōu)或者近似最優(yōu)的最小公倍數(shù)周期序列。最后，將優(yōu)化后的機(jī)械手調(diào)度策略用于實(shí)際智能鉆孔生產(chǎn)線，并和傳統(tǒng)的啟發(fā)式算法做了對(duì)比分析，證明了該混合調(diào)度策略的有效性。

機(jī)械手；并行機(jī)器；周期序列；遺傳算法

0 引言

自動(dòng)化制造單元已經(jīng)廣泛應(yīng)用于半導(dǎo)體制造、機(jī)械工件加工、電鍍生產(chǎn)線等生產(chǎn)加工領(lǐng)域。這類(lèi)系統(tǒng)通常由物料搬運(yùn)機(jī)械手、輸入臺(tái)、輸出臺(tái)、機(jī)器和控制臺(tái)等組成[1-3]。為了減小工件的平均加工時(shí)間，調(diào)高生產(chǎn)效率，越來(lái)越多的企業(yè)在加工時(shí)間較長(zhǎng)的瓶頸工序上增加了并行機(jī)器，在同一時(shí)間同一工序上可以加工多個(gè)工件，此類(lèi)系統(tǒng)稱(chēng)為含有并行機(jī)器的自動(dòng)化制造單元[4]。此類(lèi)制造單元的調(diào)度問(wèn)題不僅要合理規(guī)劃?rùn)C(jī)械手的物料搬運(yùn)作業(yè)，還要考慮各個(gè)并行機(jī)器的作業(yè)安排，以保證加工時(shí)間最優(yōu)。

針對(duì)此類(lèi)問(wèn)題的優(yōu)化和調(diào)度受到越來(lái)越多的學(xué)者關(guān)注。Li[5]等人提出一種混合整數(shù)規(guī)劃模型求解含有并行機(jī)器的自動(dòng)化制造單元調(diào)度問(wèn)題。Zhang[6]等人基于最小公倍數(shù)(Least Common Multiple，LCM)周期序列算法研究了實(shí)際生產(chǎn)車(chē)間中機(jī)械手調(diào)度問(wèn)題，并提出了優(yōu)化LCM策略的算法。以上調(diào)度策略不適用于求解大規(guī)模自動(dòng)化制造單元作業(yè)問(wèn)題。隨著自動(dòng)化制造單元日趨復(fù)雜，傳統(tǒng)的調(diào)度策略難以得到令人滿意的效果，車(chē)阿大[7-9]等人設(shè)計(jì)了多種元智能算法求解自動(dòng)化制造單元調(diào)度問(wèn)題，取得了較為令人滿意的效果，但是，對(duì)于某些工序上存在并行機(jī)器的自動(dòng)化制造單元的調(diào)度問(wèn)題討論較少。

本文將LCM調(diào)度策略和遺傳算法相結(jié)合，求解含有并行機(jī)器的自動(dòng)化制造單元的調(diào)度問(wèn)題。采用LCM策略可以避免機(jī)械手搬運(yùn)作業(yè)不可行解的產(chǎn)生[10]。然后，設(shè)計(jì)遺傳算法求解最優(yōu)或者近似最優(yōu)的LCM周期序列。最后，將機(jī)械手調(diào)度策略用于實(shí)際生產(chǎn)車(chē)間，通過(guò)真實(shí)生產(chǎn)數(shù)據(jù)驗(yàn)證調(diào)度策略的有效性。

1 問(wèn)題描述及符號(hào)定義

1.1 問(wèn)題描述

本文的智能鉆孔生產(chǎn)線包括上料、臥式鉆孔、立式鉆孔、下料等四個(gè)環(huán)節(jié)。其中臥式加工采用2臺(tái)臥式鉆床(臥鉆)，立式加工采用3臺(tái)立式鉆床(立鉆)并行加工。系統(tǒng)模型如圖1所示：機(jī)械手在中心，負(fù)責(zé)加工過(guò)程中工件的轉(zhuǎn)移和上下料作業(yè)。機(jī)械手的四周，分別布置2臺(tái)臥鉆，3臺(tái)立鉆，以及碼垛機(jī)。碼垛機(jī)包括了毛坯料架和成品架。由于機(jī)械手可以360°旋轉(zhuǎn)，并且其手臂可伸展和彎曲，具有空間的6自由度，因此可以抓取智能鉆孔生產(chǎn)空間的任意工件，從而實(shí)現(xiàn)無(wú)人自動(dòng)抓取作業(yè)，保證了整個(gè)生產(chǎn)線的全自動(dòng)進(jìn)行。

圖1 智能鉆孔生產(chǎn)布局圖

智能鉆孔系統(tǒng)具有以下特點(diǎn)：

(1)系統(tǒng)加工的是同一種工件，每個(gè)工件要經(jīng)過(guò)兩道工序，即先經(jīng)過(guò)臥式機(jī)床加工，后經(jīng)過(guò)立式機(jī)床加工。

(2)每個(gè)機(jī)器在同一時(shí)刻只加工一個(gè)工件，加工過(guò)程不會(huì)中斷。

(3)同一工序內(nèi)的并行機(jī)器具有相同的優(yōu)先級(jí)。

(4)機(jī)械手同一時(shí)間一次最多搬運(yùn)一個(gè)工件。

(5)各個(gè)機(jī)器之間沒(méi)有工件緩存區(qū)。

Crama[11]證明該加工過(guò)程是一個(gè)周期性循環(huán)過(guò)程，即每個(gè)循環(huán)周期內(nèi)加工相同數(shù)量的工件，機(jī)械手和機(jī)器恢復(fù)初始狀態(tài)，與之對(duì)應(yīng)會(huì)有周期性的機(jī)械手動(dòng)作序列。本文的研究目標(biāo)就是求解智能鉆孔系統(tǒng)中機(jī)械手的調(diào)度問(wèn)題，得到最優(yōu)或者近似最優(yōu)的機(jī)械手動(dòng)作序列。

1.2 符號(hào)定義

M1a，M1b：臥鉆工序的兩臺(tái)機(jī)器定義；M2a，M2b，M2c：立鉆工序的3臺(tái)機(jī)器定義；I：毛坯料架(輸入臺(tái))定義；O：成品架(輸出臺(tái))定義。

機(jī)械手的搬運(yùn)作業(yè)A1γη：表示機(jī)械手將工件從第一道工序的機(jī)器M1γ下料后，移動(dòng)到第二道工序，給機(jī)器M2η上料；A0*γ：表示機(jī)械手從毛坯料架取料后，給第一道工序內(nèi)的機(jī)器M1γ上料；A2η*：表示機(jī)械手從第二道工序下料后，將加工完成的工件放到成品架上。其中，γ={a,b} ，η={a,b,c} ，分別對(duì)應(yīng)第一道工序的兩臺(tái)臥鉆和第二道工序的三臺(tái)立鉆。

舉例來(lái)說(shuō)，A1ba表示機(jī)械手從機(jī)器M1b下料，隨后搬運(yùn)工件到機(jī)器M2a并給M2a上料；A0*a表示機(jī)械手從毛坯料架上I取下工件后，給機(jī)器M1a上料。

2 建立LCM模型

本文研究的智能鉆孔系統(tǒng)是典型的含有并行機(jī)器的自動(dòng)化生產(chǎn)單元，LCM策略被證明是求解此類(lèi)問(wèn)題的有效方法[12]，LCM策略有如下特點(diǎn)：

(1)一個(gè)周期內(nèi)，完成加工的工件數(shù)量為λ，λ=LCM(k1,k2,…,km)。

(2)同一工序內(nèi)，機(jī)器上料和下料遵守同一順序。

(3)同一個(gè)機(jī)器上料次數(shù)和下料次數(shù)相同。

(4)同一工序內(nèi)，并行機(jī)器使用的次數(shù)相同。

定義Li為第i個(gè)LCM序列，Li中的第j個(gè)子序列表示為L(zhǎng)i,j，每個(gè)子序列完成一個(gè)工件的全部加工工序，所以LCM序列可以看作λ個(gè)單工件序列的串聯(lián)。一個(gè)自動(dòng)化制造單元LCM序列可以表示為：

L1=[L1,1,L1,2,…,L1,λ]
L2=[L2,1,L2,2,…,L2,λ]
…
Lξ=[Lξ,1,Lξ,2,…,Lξ,λ]

其中，i=1,2,…,ξ;j=1,2,…,λ。

本文研究的系統(tǒng)含有2道加工工序，k1=2,k2=3，λ=LCM(k1,k2)=6。其中一個(gè)LCM序列可以表示為：

L1=A0*aA1bcA2a*A0*bA1abA2c*A0*aA1bcA2b*
A0*bA1aaA2c*A0*aA1bbA2a*A0*bA1aaA2b*=
[A0*aA1bcA2a*,A0*bA1abA2c*,A0*aA1bcA2b*,
A0*bA1aaA2c*,A0*aA1bbA2a*,A0*bA1aaA2b*]=
[L1,1,L1,2,L1,3,L1,4,L1,5,L1,6]

該LCM序列解釋如下：在循環(huán)周期開(kāi)始的時(shí)候，在機(jī)器M1b和機(jī)器M2a上有工件在處理。在第一個(gè)子序列L1,1，機(jī)械手從毛坯料架拿起一個(gè)工件上料到機(jī)器M1a上，然后機(jī)械手移動(dòng)到M1b，將M1b上的工件搬運(yùn)到機(jī)器M2c上；隨后，移動(dòng)到機(jī)器M2a，把加工好的工件下料后放到成品架上，第一個(gè)子序列完成。

機(jī)械手返回到毛坯料架后，開(kāi)始第二個(gè)子序列L1,2。從毛坯料架拿起工件上料到機(jī)器M1b上；機(jī)械手移動(dòng)到機(jī)器M1a，從機(jī)器M1a上搬運(yùn)工件上料到M2b上；然后機(jī)械手移動(dòng)到機(jī)器M2c，從機(jī)器M2c上下料一個(gè)加工完成的工件放到成品架上，第二個(gè)子序列結(jié)束。其余的4個(gè)子序列的執(zhí)行過(guò)程類(lèi)似。

在整個(gè)LCM序列執(zhí)行完成后，臥站工序內(nèi)的兩臺(tái)機(jī)器均使用3次，立鉆工序內(nèi)的3臺(tái)機(jī)器均被使用2次，系統(tǒng)的加工過(guò)程如圖3所示。

圖2 加工過(guò)程示意圖

3 遺傳算法求解LCM序列

通過(guò)以上轉(zhuǎn)化，對(duì)智能鉆孔系統(tǒng)采用類(lèi)似于單工件循環(huán)的編碼方式。適應(yīng)度函數(shù)是LCM序列循環(huán)時(shí)間；控制策略的目標(biāo)是最小化循環(huán)時(shí)間，在算法執(zhí)行的過(guò)程中不斷替換保存種群中適應(yīng)度高的染色體，并且剔除適應(yīng)度弱的染色體。實(shí)驗(yàn)參數(shù)選擇為:種群規(guī)模為100，交叉概率為0.95，突變概率為0.1，精英概率為0.25。算法流程圖如圖3所示。

圖3 遺傳算法流程圖

算法求解的機(jī)械手動(dòng)作序列為：

L2=A0*aA2a*A1baA0*bA2b*A1abA0*aA2c*
A1bcA0*bA2a*A1aaA0*aA2b*A1bbA0*bA2c*A1ac

該LCM序列解釋如下：在LCM序列循環(huán)開(kāi)始的時(shí)候，在機(jī)器M1b,M2a,M2b,M2c上有工件正在處理，在第一個(gè)子序列內(nèi)，機(jī)械手從毛坯料架上取出一個(gè)工件，上料到機(jī)器M1a；然后機(jī)械手移動(dòng)到M2a，從M2a上卸下一個(gè)加工完成的工件，搬運(yùn)到成品架；隨后，機(jī)械手移動(dòng)到M1b，將機(jī)器M1b上的工件下料后，帶著工件移動(dòng)到M2a，給機(jī)器M2a上料；第一個(gè)子序列執(zhí)行完成。

機(jī)器人返回毛坯料架后，開(kāi)始執(zhí)行第二個(gè)子序列，機(jī)械手從毛坯料架把一個(gè)新的工件上料給機(jī)器M1b；然后轉(zhuǎn)移到M2b，從M2b上卸載一個(gè)加工好的工件放到成品架上；隨后機(jī)械手移動(dòng)到M1a，給機(jī)器M1a下料，并將工件搬運(yùn)到機(jī)器M2b，給機(jī)器M2b上料；第二個(gè)子序列執(zhí)行完成。其余的4個(gè)子序列的執(zhí)行過(guò)程類(lèi)似。機(jī)械手搬運(yùn)作業(yè)甘特圖如圖4所示。

圖4 機(jī)械手搬運(yùn)作業(yè)甘特圖

4 實(shí)驗(yàn)驗(yàn)證

本文研究的風(fēng)電葉片預(yù)埋螺套鉆孔系統(tǒng)，以往機(jī)械手調(diào)度采用的是先請(qǐng)求先服務(wù)(FirstInFirstServed，F(xiàn)IFS)的啟發(fā)式規(guī)則策略，F(xiàn)IFS策略可以表述為：機(jī)械手等待當(dāng)前的任務(wù)完成后，按照各個(gè)機(jī)器請(qǐng)求時(shí)間的先后順序執(zhí)行下一步的搬運(yùn)作業(yè)。在FIFS策略控制下，機(jī)械手優(yōu)先響應(yīng)發(fā)出請(qǐng)求最早的機(jī)器，不能對(duì)意外情況做出及時(shí)的響應(yīng)，并且要求搬運(yùn)機(jī)械手實(shí)時(shí)等待正在加工處理的工件，容易引起整個(gè)加工生產(chǎn)線的阻塞，影響機(jī)器的生產(chǎn)效率和整個(gè)生產(chǎn)線的加工能力。

為了改善這些不足，本文提出了LCM策略調(diào)度機(jī)械手的搬運(yùn)作業(yè)，并基于遺傳算法求解近似最優(yōu)的LCM序列，將求解的近似最優(yōu)解作為搬運(yùn)機(jī)械手的控制方案。在實(shí)際加工車(chē)間中，兩種控制策略實(shí)際應(yīng)用的對(duì)比結(jié)果如表1所示；生產(chǎn)現(xiàn)場(chǎng)如圖5所示。從表1看到，在實(shí)際生產(chǎn)線上，使用本文提出的機(jī)械手調(diào)度策略后，人力資源成本降低83.3%；產(chǎn)量提高50%；產(chǎn)品合格率提高11.2%；維護(hù)成本下降30%，很好的提高了生產(chǎn)企業(yè)的市場(chǎng)競(jìng)爭(zhēng)力。

表1 實(shí)際加工車(chē)間生產(chǎn)數(shù)據(jù)

5 結(jié)論

針對(duì)智能鉆孔系統(tǒng)加工過(guò)程中并行機(jī)器的上下料順序和機(jī)械手調(diào)度雙資源優(yōu)化問(wèn)題，在建立LCM周期序列模型的基礎(chǔ)上，利用遺傳算法全局尋優(yōu)能力較強(qiáng)的特點(diǎn)，求解得到了最優(yōu)或者近似最優(yōu)的LCM周期序列，該混合算法在智能鉆孔系統(tǒng)生產(chǎn)現(xiàn)場(chǎng)的實(shí)際應(yīng)用表明：機(jī)械手調(diào)度采用LCM策略后，克服了傳統(tǒng)啟發(fā)式調(diào)度策略等待時(shí)間長(zhǎng)，容易導(dǎo)致生產(chǎn)線阻塞的缺點(diǎn)，降低了人力資源成本和機(jī)器的維護(hù)成本，并且較大程度提高了產(chǎn)品產(chǎn)量和合格率。為含有并行機(jī)器的自動(dòng)化制造單元機(jī)械手的調(diào)度提供了參考，下一步工作將研究不同工件類(lèi)型以及遺傳算法中變異、交叉算子等方面的機(jī)械手調(diào)度問(wèn)題。

[1] 龍傳澤, 楊煜俊. 基于遺傳算法的柔性機(jī)器人制造單元調(diào)度問(wèn)題研究[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(11):141-144.

[2] FOUMANI M. Scheduling rotationally arranged robotic cells served by a multi-function robot[J]. International Journal of Production Research, 2014, 52(13):4037-4058.

[3] FOX J. Bi-objective cyclic scheduling in a robotic cell with processing time windows and non-Euclidean travel times[J]. International Journal of Production Research, 2014, 52(52):2505-2518.

[4] NADERI B, KHALILI M, KHAMSEH A A. Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines[J]. International Journal of Production Research, 2014, 52(9):2667-2681.[5] LI Xin, CHAN F T S, CHUNG S H. Optimal multi-degree cyclic scheduling of multiple robots without overlapping in robotic flowshops with parallel machines[J]. Journal of Manufacturing Systems, 2015, 36:62-75.

[6] ZHANG J, FANG X, QI L. LCM cycle based optimal scheduling in robotic cell with parallel workstations[C]// Robotics and Automation (ICRA), 2014 IEEE International Conference on IEEE, 2014:1367-1373.

[7] 王躍崗, 車(chē)阿大. 基于混合量子進(jìn)化算法的自動(dòng)化制造單元調(diào)度[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2013, 19(9):2193-2201.[8] 李鵬, 車(chē)阿大. 基于混沌遺傳算法的自動(dòng)化生產(chǎn)單元調(diào)度方法[J]. 系統(tǒng)工程, 2008，26(11):75-80.

[9] YAN Pengyu, CHE Ada, CAI Xiaoqiang, et al. Two-phase branch and bound algorithm for robotic cells rescheduling considering limited disturbance[J]. Computers & Operations Research, 2014, 50(10):128-140.

[10] GEISMAR H N, DAWANDE M, SRISKANDARAJAH C. Throughput Optimization in Constant Travel-Time Dual Gripper Robotic Cells with Parallel Machines[J]. Production & Operations Management, 2006, 15(2):311-328.

[11] CRAMA Y, KATS V, KLUNDERT J V D, et al. Cyclic scheduling in robotic flowshops[J]. Annals of Operations Research, 2000, 96(14):97-124.

[12] GEISMAR H N, DAWANDE M, SRISKANDARAJAH C. Robotic Cells with Parallel Machines: Throughput Maximization in Constant Travel-Time Cells[J]. Journal of Scheduling, 2004, 7(5):375-395.

[13] 柳青紅, 袁逸萍, 李曉娟,等. 基于改進(jìn)遺傳算法交叉算子的作業(yè)車(chē)間調(diào)度[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2014(12):150-153.

[14] 李運(yùn)霞, 杜娟, 孫王路. 基于多種群遺傳算法的路徑柔性車(chē)間調(diào)度問(wèn)題[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2014(3):152-155.

[15] TA Q C, BILLAUT J C, BOUQUARD J L. Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem[J]. Journal of Intelligent Manufacturing, 2015:1-12.

[16] LI D C, HSU P H, CHANG C C. A Genetic Algorithm-Based Approach for Single-Machine Scheduling with Learning Effect and Release Time[J]. Mathematical Problems in Engineering, 2014(1):1-12.

[17] VERMA R, PHANDEN R K, JAIN A. A Genetic Algorithm-based Approach for Job Shop Scheduling[J]. Journal of Manufacturing Technology Management, 2012, 23(7):937-946.

[18] KUMAR S. Minimizing cycle time in large robotic cells[J]. Iie Transactions, 2005, 37(37):123-136.

(編輯 李秀敏)

Scheduling Strategy for Robot in Robot Cell with Parallel Machines

MENG Xian-feng, LUO Yong

(School of Electrical Engineer, Zhengzhou University, Zhengzhou 450001, China)

The optimal scheduling strategy for robot in the intelligent drill system was studied in this paper. To solve optimization scheduling problem for intelligent drill system including parallel over several machines and a robot, a new scheduling algorithm is proposed, which combines genetic algorithms and least common multiple periodic sequence. Firstly, based on the analysis of the operating characteristics of the robot in the process, this thesis presented the least common multiple periodic sequence model. Secondly, a genetic algorithm was designed for the optimal least common multiple periodic sequence. Finally, the strategy was applied to the practical production line, in addition to comparisons with a early heuristic algorithm, and the results show that the strategy for the robot has feasibility.

robot; parallel machines; periodic sequence; genetic algorithm

1001-2265(2017)01-0042-04

10.13462/j.cnki.mmtamt.2017.01.012

2016-04-05；

2016-04-26

河南省青年骨干教師項(xiàng)目(2015GGJS-148)；河南省產(chǎn)學(xué)研合作項(xiàng)目(152107000058)

孟現(xiàn)鋒(1989—)，男，安徽阜陽(yáng)人，鄭州大學(xué)碩士研究生，研究方向?yàn)樯a(chǎn)計(jì)劃與調(diào)度、計(jì)算機(jī)技術(shù)，(E-mail)971770764@qq.com； 通訊作者：羅勇(1989—)，男，湖南常德人，鄭州大學(xué)教授，博士，研究方向?yàn)橛?jì)算機(jī)控制技術(shù),(E-mail)luoyong@zzu.edu.cn。

TH166;TG659

A