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

孟現(xiàn)鋒，羅 勇

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

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

孟現(xiàn)鋒，羅 勇

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

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

機械手；并行機器；周期序列；遺傳算法

0 引言

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

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

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

1 問題描述及符號定義

1.1 問題描述

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

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

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

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

(2)每個機器在同一時刻只加工一個工件，加工過程不會中斷。

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

(4)機械手同一時間一次最多搬運一個工件。

(5)各個機器之間沒有工件緩存區(qū)。

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

1.2 符號定義

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

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

舉例來說，A1ba表示機械手從機器M1b下料，隨后搬運工件到機器M2a并給M2a上料；A0*a表示機械手從毛坯料架上I取下工件后，給機器M1a上料。

2 建立LCM模型

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

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

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

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

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

定義Li為第i個LCM序列，Li中的第j個子序列表示為Li,j，每個子序列完成一個工件的全部加工工序，所以LCM序列可以看作λ個單工件序列的串聯(lián)。一個自動化制造單元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。其中一個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)周期開始的時候，在機器M1b和機器M2a上有工件在處理。在第一個子序列L1,1，機械手從毛坯料架拿起一個工件上料到機器M1a上，然后機械手移動到M1b，將M1b上的工件搬運到機器M2c上；隨后，移動到機器M2a，把加工好的工件下料后放到成品架上，第一個子序列完成。

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

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

圖2 加工過程示意圖

3 遺傳算法求解LCM序列

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

圖3 遺傳算法流程圖

算法求解的機械手動作序列為：

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

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

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

圖4 機械手搬運作業(yè)甘特圖

4 實驗驗證

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

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

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

5 結(jié)論

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

[1] 龍傳澤, 楊煜俊. 基于遺傳算法的柔性機器人制造單元調(diào)度問題研究[J]. 組合機床與自動化加工技術(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] 王躍崗, 車阿大. 基于混合量子進化算法的自動化制造單元調(diào)度[J]. 計算機集成制造系統(tǒng), 2013, 19(9):2193-2201.[8] 李鵬, 車阿大. 基于混沌遺傳算法的自動化生產(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] 柳青紅, 袁逸萍, 李曉娟,等. 基于改進遺傳算法交叉算子的作業(yè)車間調(diào)度[J]. 組合機床與自動化加工技術(shù), 2014(12):150-153.

[14] 李運霞, 杜娟, 孫王路. 基于多種群遺傳算法的路徑柔性車間調(diào)度問題[J]. 組合機床與自動化加工技術(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

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

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

TH166;TG659

A