李國(guó)民 高 亮 李新宇

華中科技大學(xué)機(jī)械科學(xué)與工程學(xué)院，武漢，430074

0 引言

軌道自動(dòng)導(dǎo)引車（rail guided vehicle，RGV）是一種在智能車間或自動(dòng)化立體倉(cāng)庫(kù)中沿著預(yù)設(shè)軌道運(yùn)行的物料運(yùn)送工具，RGV在物流系統(tǒng)和自動(dòng)存儲(chǔ)與檢索系統(tǒng)中的應(yīng)用較早［1－3］。隨著自動(dòng)化系統(tǒng)在煙草、金融、醫(yī)藥、日化等行業(yè)的廣泛應(yīng)用，對(duì)輸送設(shè)備的需求也日益突顯。

為提高物料運(yùn)輸效率，增加車間產(chǎn)能，企業(yè)逐步引入現(xiàn)代化的RGV物料搬運(yùn)工具。CHEN等［4］模擬柔性制造系統(tǒng)的上料／卸料操作，并闡述了RGV系統(tǒng)的智能生產(chǎn)調(diào)度和控制框架的具體應(yīng)用；JAIGANESH等［5］闡述了自動(dòng)導(dǎo)引車（automated guided vehicle，AGV）的 物 流 系 統(tǒng)；HU等［6］對(duì)線性跟蹤自動(dòng)貨運(yùn)處理系統(tǒng)的多載量RGV進(jìn)行研究，考慮雙邊上料／卸料操作的最優(yōu)路徑，并指出最小化能源消耗目標(biāo)的同時(shí)要考慮避免沖突和時(shí)間窗約束。NEJAD等［7］對(duì)RGV上下料進(jìn)行了研究。

隨著車間作業(yè)規(guī)模的擴(kuò)大，人們結(jié)合不同學(xué)科理論和優(yōu)化算法開(kāi)展了提升RGV綜合調(diào)度性能的研究，如約束理論［8］、粒子群優(yōu)化算法［9-12］、遺 傳 算 法［13－14］、組 合 拍 賣 算 法［15］、模 糊算法［16］、模 擬 退 火 算 法［17］。FAZLOLLAHTABAR等［18］從周期角度進(jìn)行研究以減少延遲造成的損失；YILDIZ等［19］也從周期角度對(duì)加工單元進(jìn)行研究。FOUMANI等［20］對(duì)多功能RGV加工單元進(jìn)行研究，其目標(biāo)為最小化RGV的加工周期或者最大化車間生產(chǎn)效率，同時(shí)，為計(jì)算加工單元產(chǎn)能，考慮上坡和下坡排列目標(biāo)函數(shù)的下界。

完全遍歷路徑規(guī)劃算法（complete coverage path planning，CCPP）的調(diào)度規(guī)則是在滿足某種性能評(píng)價(jià)指標(biāo)最優(yōu)的前提下尋找一條在設(shè)定區(qū)域內(nèi)從始點(diǎn)到終點(diǎn)且經(jīng)過(guò)所有可達(dá)點(diǎn)的連續(xù)路徑。該算法在自動(dòng)化系統(tǒng)中易于實(shí)現(xiàn)且具有實(shí)用性、可重復(fù)性、效率高等特點(diǎn)，在機(jī)器人領(lǐng)域得到廣泛應(yīng)用，主要涉及機(jī)器人清洗、采礦、檢查、探測(cè)等［21－24］。

從目前的文獻(xiàn)來(lái)看，RGV動(dòng)態(tài)調(diào)度大多是在理想狀態(tài)下進(jìn)行研究的，沒(méi)有考慮不確定性環(huán)境下由于存在異常斷刀、刀具壽命到期、零件報(bào)廢、機(jī)器故障等一系列不確定性因素導(dǎo)致的CNC設(shè)備（以下簡(jiǎn)稱CNC）停機(jī)問(wèn)題。為此本文基于CCPP調(diào)度規(guī)則對(duì)生產(chǎn)車間不確定性環(huán)境下RGV動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行研究。

1 問(wèn)題描述及數(shù)學(xué)模型

1.1 問(wèn)題描述

某手機(jī)后殼加工車間有10條產(chǎn)線，每條產(chǎn)線包含10個(gè)加工單元，每個(gè)加工單元配備若干臺(tái)CNC（編號(hào) Mi，i＝1，2，…，N）和1臺(tái) RGV（圖1）。CNC發(fā)出物料需求信號(hào)并通過(guò)中央控制系統(tǒng)將信號(hào)傳送給RGV，RGV檢測(cè)物料需求信號(hào)并依據(jù)一定規(guī)則為CNC上下料。RGV沿直線型軌道運(yùn)行，安裝在RGV上的機(jī)械手執(zhí)行上下料作業(yè)。由于不同加工單元的RGV調(diào)度可以獨(dú)立進(jìn)行，為了簡(jiǎn)化問(wèn)題，本文僅以車間中的1個(gè)加工單元為研究對(duì)象。定義RGV依次為加工單元N臺(tái)CNC全部上下料完畢為1個(gè)作業(yè)周期，RGV完成1個(gè)作業(yè)周期包含以下5個(gè)操作過(guò)程。

圖1 加工單元布局圖Fig.1 The layout of manufacturing cell

（1）RGV用機(jī)械手的一個(gè)手爪從來(lái)料頂升Tray盤內(nèi)抓取未加工的物料移至Mi，用另一個(gè)手爪在Mi內(nèi)抓取已加工物料A，然后將未加工物料放置于加工位置。

（2）上料完畢后，機(jī)械手將抓取的物料A移至RGV自帶的清洗槽，取出已清洗完畢的上一片物料B，并把物料A放入清洗槽，然后把物料B放置于對(duì)面出料頂升的Tray盤內(nèi)。判斷Tray盤是否裝滿，若裝滿則出料頂升Tray盤下降并將Tray盤放置于傳送帶上；若未裝滿，則不作處理。

（3）RGV判斷來(lái)料頂升Tray盤內(nèi)物料是否取完，若取完，則吹氣清理空的Tray盤，并將其轉(zhuǎn)移到出料頂升臺(tái)，來(lái)料頂升從傳送帶頂起Tray盤；若未取完，則不作處理。

（4）RGV檢測(cè)物料需求信號(hào)，依據(jù)調(diào)度規(guī)則移動(dòng)至下一臺(tái)需要上下料的CNC設(shè)備Mi＋1。

（5）移動(dòng)至Mi＋1時(shí)，若Mi＋1加工完畢，則RGV直接進(jìn)行上下料作業(yè)；否則，RGV等待Mi＋1加工完畢后進(jìn)行上下料作業(yè)。

在加工生產(chǎn)過(guò)程中，可能會(huì)因CNC故障、異常斷刀、刀具壽命到期、切削液異常等因素導(dǎo)致CNC報(bào)警甚至停機(jī)，待CNC維修完畢或者更換刀具確保能夠正常加工生產(chǎn)后再次進(jìn)行加工作業(yè)。加工過(guò)程中刀具會(huì)有不同程度的磨損，導(dǎo)致加工產(chǎn)品尺寸不合格，這時(shí)就必須對(duì)CNC的刀具進(jìn)行調(diào)整和補(bǔ)償，從而致使CNC停機(jī)。在正常加工情況下，RGV會(huì)按照原有順序依次為CNC進(jìn)行上下料作業(yè)，但當(dāng)某臺(tái)因異常情況而停機(jī)的CNC維修好可重新加工時(shí)，由于RGV的排他性，CNC之間存在叫料競(jìng)爭(zhēng)，即RGV同一時(shí)間只能為1臺(tái)CNC上下料。目前車間采用的是就近調(diào)度規(guī)則，即RGV作業(yè)完成后檢測(cè)所有發(fā)出物料需求信號(hào)的CNC，選擇離其最近的CNC進(jìn)行上下料作業(yè)，但是采用這種調(diào)度規(guī)則時(shí)存在CNC等待的現(xiàn)象。如何確定RGV調(diào)度規(guī)則、確定調(diào)度期內(nèi)CNC上下料順序、提高CNC產(chǎn)能是值得研究的問(wèn)題。

1.2 基本假設(shè)

調(diào)度問(wèn)題必須滿足以下假設(shè)：①起始時(shí)刻RGV在M1與M2之間的軌道位置，所有CNC處于空閑狀態(tài)；②1臺(tái)CNC同一時(shí)間只能加工1片物料，每片物料只能被1臺(tái)CNC加工；③RGV同一時(shí)間只能為1臺(tái)CNC進(jìn)行上下料操作，不考慮RGV故障的情況；④物料使用傳送帶傳送，生產(chǎn)過(guò)程中不存在缺料現(xiàn)象；⑤每個(gè)Tray盤只能放置2片物料；⑥RGV軌道是雙向的，CNC之間的間距固定。

1.3 參數(shù)和變量

所涉及的集合、變量和參數(shù)見(jiàn)表1。

表1 相關(guān)參數(shù)Tab.1 Related parameters

1.4 數(shù)學(xué)函數(shù)

隨著生產(chǎn)的進(jìn)行，CNC會(huì)出現(xiàn)停機(jī)等待的現(xiàn)象，不恰當(dāng)?shù)恼{(diào)度規(guī)則會(huì)導(dǎo)致RGV路徑迂回，增加RGV行走時(shí)間，進(jìn)而增加RGV的上下料周期，一旦RGV的上下料周期超過(guò)CNC的加工周期，會(huì)導(dǎo)致CNC停機(jī)等待，影響CNC產(chǎn)能。因此，本研究的目標(biāo)是，在確保穩(wěn)態(tài)期RGV周期小于CNC周期的前提下，最小化RGV的過(guò)渡周期?；谏鲜鰠?shù)設(shè)置，該RGV動(dòng)態(tài)調(diào)度數(shù)學(xué)模型如下：

約束條件：

式（1）表示最小化過(guò)渡期時(shí)RGV周期，保證RGV能夠及時(shí)為CNC進(jìn)行上下料作業(yè)。其中RGV周期包含加工單元內(nèi)所有CNC的上下料時(shí)間和所有RGV洗料時(shí)間、移動(dòng)Tray盤時(shí)間、RGV在CNC間的移動(dòng)時(shí)間及等待時(shí)間；式（2）保證Tray盤只能放置2片物料；式（3）表示通過(guò)調(diào)整CNC上下料順序，在CNC上下料周期穩(wěn)定后，存在部分序列的RGV周期小于CNC加工周期。式（4）、式（5）是為了最大化加工單元CNC數(shù)量，保證RGV與CNC數(shù)量能夠得到有效配置，在此配置機(jī)制下，RGV能夠在CNC加工結(jié)束之前返回，保證CNC不因缺料而停機(jī)。

2 完全遍歷路徑規(guī)劃算法設(shè)計(jì)

完全遍歷路徑規(guī)劃類似于旅行商問(wèn)題（traveling sales-man problem，TSP），要求移動(dòng)機(jī)器人在滿足一定的指標(biāo)下完全覆蓋目標(biāo)環(huán)境中的可達(dá)區(qū)域［25－26］。RGV 動(dòng)態(tài)調(diào)度采用 CCPP算法調(diào)度規(guī)則的思想是：對(duì)維修完成的CNC遍歷后插入到正常工作的CNC序列中，計(jì)算各遍歷序列的穩(wěn)態(tài)期和過(guò)渡期的RGV周期，在滿足TRCi≤TCC的前提下，最小化RGV的過(guò)渡周期。若不存在TRCi≤TCC的情況，則對(duì)正常的加工序列進(jìn)行重排。CCPP算法的流程見(jiàn)圖2，具體描述如下。

圖2 完全遍歷路徑規(guī)劃算法流程圖Fig.2 The flow chart of CCPP

（1）初始化集合，初始化正常工作CNC集合W＝ ｛wiwi∈N，i＝1，2，…，l｝、故障CNC集合F＝ ｛fifi∈N，i＝1，2，…，m｝、維修完成CNC集合R＝ ｛riri∈N，i＝1，2，…，n｝，其中，N ＝l＋m＋n。

（2）判斷維修完成CNC集合R是否為空，若為空則RGV按照原有CNC加工順序進(jìn)行上下料作業(yè)；否則，將集合R中的Mri按照維修完成時(shí)間依次遍歷插入到正常加工的CNC集合W中，得到新的CNC集合：W′＝（W∪R）。

（3）計(jì)算集合W′各個(gè)序列在穩(wěn)態(tài)期時(shí)RGV周期TRCi和過(guò)渡期時(shí) RGV 周期 TRC′i，若 TRCi≤TCC，則從集合W′中選擇過(guò)渡期RGV周期最小的CNC上下料作業(yè)序列作為CCPP算法的可行解，轉(zhuǎn)步驟（6）；否則，對(duì)正常加工的CNC集合W 進(jìn)行重排，轉(zhuǎn)步驟（4）。

（4）檢測(cè)維修完成的CNC集合R中Mri對(duì)面正常加工Mwi的鄰位是否有單側(cè)上料（相對(duì)的兩臺(tái)CNC上下料順序不相鄰）的Mi，若有，則將最早完工的單側(cè)上料Mi移至其對(duì)位CNC的鄰位，并將Mri放置于Mi的位置，得到新的CNC集合W″，若TRCi≤TCC則將該集合作為CCPP算法的可行解；否則，從正常加工的CNC集合W中尋找最早完工的單側(cè)上料Mi并移至其對(duì)位CNC的鄰位，同時(shí)將Mri放置于其對(duì)位CNC的鄰位得到集合W″，若TRCi≤TCC則轉(zhuǎn)步驟（6），否則轉(zhuǎn)步驟（5）。

（5）將集合W″中最早完工的單側(cè)上料Mj移至其對(duì)位CNC的鄰位，若TRCi≤TCC則轉(zhuǎn)步驟（6），否則執(zhí)行步驟（5）。

（6）從集合R中移除維修完成的Mri。

（7）重復(fù)步驟（1）～步驟（6）。

特別說(shuō)明的是，基于CCPP算法的重排是依據(jù)車間實(shí)際參數(shù)而提出，并依據(jù)式（3）～式（5）計(jì)算RGV服務(wù)CNC的數(shù)量，即RGV為加工單元內(nèi)CNC上下料結(jié)束后返回第一臺(tái)需要上下料的CNC時(shí)，該臺(tái)CNC恰好加工結(jié)束或者即將加工結(jié)束，以保障CNC不出現(xiàn)等待的現(xiàn)象。所以，若CNC上下料順序混亂導(dǎo)致CNC等待，通過(guò)調(diào)整CNC的上下料順序必有TRCi≤TCC存在。

3 算例分析

由于直接計(jì)算目標(biāo)函數(shù)值、更新已有和未來(lái)的上下料任務(wù)等過(guò)程非常復(fù)雜，故對(duì)智能車間加工單元N臺(tái)CNC分別采用就近調(diào)度規(guī)則、CCPP算法并運(yùn)用Java語(yǔ)言進(jìn)行建模仿真。

3.1 參數(shù)設(shè)置

在進(jìn)行模擬仿真之前，首先要確定系統(tǒng)輸入?yún)?shù)，恰當(dāng)?shù)妮斎雲(yún)?shù)對(duì)生產(chǎn)車間的產(chǎn)能具有重要影響，依據(jù)車間生產(chǎn)現(xiàn)狀，對(duì)RGV動(dòng)態(tài)調(diào)度系統(tǒng)參數(shù)進(jìn)行統(tǒng)計(jì)，分別收集各指標(biāo)的20組數(shù)據(jù)并取均值見(jiàn)表2。

表2 RGV動(dòng)態(tài)調(diào)度參數(shù)值Tab.2 The parameters values of RGV

本文對(duì)車間加工單元10H的加工狀況進(jìn)行模擬。在模型中輸入CNC停機(jī)數(shù)據(jù)，包含停機(jī)CNC編號(hào)（e）、停機(jī)開(kāi)始時(shí)間（tF）和停機(jī)結(jié)束時(shí)間（tR），停機(jī)數(shù)據(jù)是從智能車間監(jiān)控系統(tǒng)中實(shí)時(shí)收集的，隨機(jī)選取一組CNC停機(jī)數(shù)據(jù)，見(jiàn)表3。在1 500s時(shí)編號(hào)為5的CNC開(kāi)始停機(jī)，在1 797s時(shí)該CNC維修結(jié)束，該臺(tái)CNC需要按照本文提出的CCPP算法重新加入加工序列。

表3 10H內(nèi)停機(jī)數(shù)據(jù)Tab.3 Downtime data in 10H s

3.2 方案分析與評(píng)價(jià)

在表2參數(shù)設(shè)置的情況下，通過(guò)式（3）～式（5）計(jì)算得加工單元CNC臺(tái)數(shù)N 最多為8，即1臺(tái)RGV為8臺(tái)CNC上下料的配置比較合理，模擬CCPP算法下加工單元的加工過(guò)程得到CNC的上下料順序見(jiàn)表4。

由表3CNC停機(jī)數(shù)據(jù)和表4CNC加工序列可以看出，加工單元8臺(tái)CNC均未出現(xiàn)停機(jī)狀況時(shí)，CNC的上下料初始順序?yàn)镸1—M2—M3—M4—M5—M6—M7—M8；第2 400s時(shí)，M7出現(xiàn)停機(jī)狀況，加工單元CNC的上下料順序變?yōu)镸1—M2—M3—M4—M5—M6—M8；第2 588s時(shí)M7處理完畢，需要重新加入正常工作CNC上下料序列中，通過(guò)CCPP算法模擬得到CNC上下料順序?yàn)镸7—M1—M2—M3—M4—M5—M6—M8，該順序表示RGV先給M7上下料再為M1上下料，依此類推。

表4 CNC加工序列Tab.4 CNC machines scheduling sequences

在就近調(diào)度規(guī)則、CCPP算法兩種不同規(guī)則的調(diào)度情況下，對(duì)表3CNC故障數(shù)據(jù)進(jìn)行模擬，兩種方案在加工單元10h內(nèi)8臺(tái)CNC的產(chǎn)能見(jiàn)表5。通過(guò)表中數(shù)據(jù)可以看出，與就近調(diào)度規(guī)則相比，采用CCPP算法時(shí)CNC總產(chǎn)能較高。該數(shù)據(jù)表明在產(chǎn)能方面，CCPP算法優(yōu)勢(shì)明顯，能夠達(dá)到提高車間產(chǎn)能的目的。

表5 CNC產(chǎn)能對(duì)比Tab.5 The comparison of CNC capacity pcs

另外，隨機(jī)選取5組不同時(shí)間段的CNC停機(jī)數(shù)據(jù)，對(duì)加工單元8臺(tái)CNC加工狀況進(jìn)行模擬，兩種調(diào)度規(guī)則時(shí)RGV行駛總路程見(jiàn)表6。

表6 不同停機(jī)情況下RGV行駛總路程對(duì)比Tab.6 Comparison of total distance of RGV under different shutdown conditions m

由表6可以看出，在5種不同時(shí)間段停機(jī)狀況下，采用CCPP算法時(shí)RGV平均總路程明顯少于就近規(guī)則下的RGV平均總路程，該數(shù)據(jù)表明CCPP算法能夠很好地對(duì)RGV進(jìn)行調(diào)度，減少RGV行駛路程，避免RGV因路徑迂回導(dǎo)致的CNC停機(jī)等待現(xiàn)象的發(fā)生。

因此，在車間調(diào)度過(guò)程中，不論是在產(chǎn)能提升方面還是在RGV總路程減少方面，采用CCPP算法的RGV動(dòng)態(tài)調(diào)度效果都優(yōu)于車間現(xiàn)行的就近調(diào)度規(guī)則。

4 結(jié)語(yǔ)

本文針對(duì)智能車間RGV作業(yè)流程進(jìn)行了詳細(xì)分析，建立了在穩(wěn)態(tài)期存在RGV周期小于CNC周期的前提下，最小化RGV過(guò)渡期的數(shù)學(xué)模型；通過(guò)模擬驗(yàn)證了CCPP算法優(yōu)于車間現(xiàn)行的就近調(diào)度規(guī)則，能夠?qū)崿F(xiàn)增加CNC產(chǎn)能、減少RGV行駛路徑的目的，避免RGV因路徑迂回導(dǎo)致CNC停機(jī)等待，為直線型軌道自動(dòng)導(dǎo)引車的實(shí)際規(guī)劃設(shè)計(jì)提供依據(jù)。