基于規(guī)則的柔性作業(yè)車間機(jī)床與AGV聯(lián)合調(diào)度優(yōu)化*

郭沛佩 付建林 江海凡 王 坤

(①西南交通大學(xué)先進(jìn)設(shè)計(jì)與制造技術(shù)研究所，四川 成都610031； ②成都運(yùn)達(dá)科技股份有限公司，四川 成都610031))

自動(dòng)導(dǎo)引車系統(tǒng)(automatic guided vehicle system，AGVS)作為一種靈活高效的物流系統(tǒng)在制造、倉儲(chǔ)配送等領(lǐng)域有著廣泛的應(yīng)用，目前柔性作業(yè)車間越來越多地采用AGV進(jìn)行物料輸送，柔性作業(yè)車間集成AGV聯(lián)合調(diào)度問題應(yīng)運(yùn)而生。國內(nèi)外對傳統(tǒng)作業(yè)車間AGV調(diào)度研究已較多，但這些研究都假定每個(gè)工件的工藝路線是確定的[1]，而在柔性作業(yè)車間中，由于每個(gè)工件的每道工序都有不同機(jī)床可供選擇，且在不同機(jī)床上的加工時(shí)間不同，工件的可變工藝路徑又導(dǎo)致AGV路徑選擇不同，這些不同組合會(huì)有不同結(jié)果，也更符合現(xiàn)代多品種小批量的生產(chǎn)方式，因此優(yōu)化柔性作業(yè)車間機(jī)床和多AGV的集成調(diào)度具有重要意義[2]。

集成調(diào)度問題是NP難問題，最先考慮了諸如數(shù)學(xué)建?；蚧趫D形的算法之類的集中方法，盡管這些方法能找到最佳解決方案，但它們只能應(yīng)用于小型場景[3]。國內(nèi)外學(xué)者開展了一系列圍繞柔性作業(yè)車間調(diào)度的研究，元啟發(fā)式智能算法提供了有效的途徑[4]，包括遺傳算法[5]、粒子群優(yōu)化算法[6]和模擬退火[7]等，但隨著求解問題復(fù)雜度上升，這些算法的解空間呈指數(shù)爆炸性增長，計(jì)算時(shí)間長，且容易出現(xiàn)早熟與陷入局部最優(yōu)問題。除此之外，啟發(fā)式規(guī)則調(diào)度方法由于其易于實(shí)現(xiàn)，計(jì)算效率高、有健壯的魯棒性，被廣泛應(yīng)用于車間調(diào)度問題。從實(shí)際生產(chǎn)系統(tǒng)的復(fù)雜性、規(guī)模性和可操作性角度考慮，啟發(fā)式調(diào)度規(guī)則仍然是目前最可行和有效的求解方法[8]。柔性車間中，不同資源有不同調(diào)度規(guī)則，可采用單一規(guī)則或組合規(guī)則方式解決實(shí)際問題，楊小佳[9]等人為比較柔性裝配作業(yè)車間中兩類動(dòng)態(tài)調(diào)度策略，采用了優(yōu)先度規(guī)則方法研究不同擾動(dòng)下的完全反應(yīng)式調(diào)度，得出采用組合規(guī)則性能更優(yōu)結(jié)論。Doh Hyoung Ho[10]等人則比較了不同組合規(guī)則，證明采用恰當(dāng)規(guī)則組合可優(yōu)化車間性能，朱偉[11]采用規(guī)則導(dǎo)向思想選擇更合適的規(guī)則組合解決了柔性作業(yè)車間多目標(biāo)集成優(yōu)化問題，但他們所解決的調(diào)度問題針對的都是車間中機(jī)床與作業(yè)排序聯(lián)合調(diào)度問題，基于規(guī)則的機(jī)床與AGV聯(lián)合調(diào)度研究較少；Jens Heger[12]采用不同規(guī)則組合解決了對作業(yè)排序、機(jī)床和AGV這3類問題的調(diào)度，但并未考慮系統(tǒng)中所需配置AGV數(shù)量對調(diào)度結(jié)果的影響；文獻(xiàn)[13]以最小化平均延遲時(shí)間為目標(biāo)采用神經(jīng)網(wǎng)絡(luò)預(yù)測不同AGV和機(jī)器利用率下車間所適用的3類規(guī)則組合，但并未考慮不同任務(wù)水平對求解模型性能影響。

本文采用離散事件建模仿真方法搭建了一個(gè)柔性作業(yè)車間仿真模型研究機(jī)床與AGV聯(lián)合調(diào)度問題，以最小化平均流動(dòng)時(shí)間、完工時(shí)間、合適AGV平均利用率與完工數(shù)量為指標(biāo)比較了3種工件路由規(guī)則與3種AGV調(diào)度規(guī)則的組合影響，確定出最優(yōu)規(guī)則組合與所需配置的AGV數(shù)量，并在確定的最優(yōu)規(guī)則組合下尋找最優(yōu)的任務(wù)到達(dá)模式與AGV數(shù)量，得到柔性生產(chǎn)車間性能最優(yōu)時(shí)的最佳規(guī)則組合、最佳AGV數(shù)量和最佳任務(wù)達(dá)到模式。

1 問題描述

1.1 柔性作業(yè)車間聯(lián)合調(diào)度問題描述

柔性作業(yè)車間機(jī)床與AGV聯(lián)合調(diào)度問題一般可描述為工件集J={J1,J2,…,Jn}在機(jī)床集M={M1,M2,…,Mm}上加工并由AGV集T={T1,T2,…,Tk}實(shí)現(xiàn)其搬運(yùn)的過程。求解該類問題通常需滿足如下假設(shè)條件：

(1)初始時(shí)刻，所有工件均處于待加工狀態(tài)，所有機(jī)器均處于空閑狀態(tài)。

(2)同一時(shí)刻，同一臺(tái)機(jī)器只能加工1個(gè)工件的某道工序。

(3)同一時(shí)刻，同一工件只能被一臺(tái)機(jī)器加工，且不允許中斷正在加工的工序。

(4) 同一工件的工序加工順序固定且不可更改，不同工件的工序間沒有順序約束關(guān)系。

(5)同一AGV1次只能運(yùn)輸一個(gè)工件。

車間中每個(gè)工件包含系列工序Oij(i為工件號(hào)，j為工序號(hào))，每道工序都將在M中的某臺(tái)機(jī)床上加工，每加工完一道工序都需要T中的某臺(tái)AGV搬運(yùn)至下道工序位置，故柔性作業(yè)車間機(jī)床與AGV聯(lián)合調(diào)度問題可看作是每道工序加工與運(yùn)輸問題的組成

1.2 主要的優(yōu)先級(jí)規(guī)則

優(yōu)先級(jí)調(diào)度規(guī)則方法指按一定的準(zhǔn)則對待加工工件、加工設(shè)備、運(yùn)輸設(shè)備進(jìn)行優(yōu)先級(jí)排序，以提供1個(gè)合適的解決方案。本文采用不同工件路由規(guī)則(一道工序有多臺(tái)機(jī)床可供選擇時(shí)，從中選出一臺(tái)機(jī)床的操作稱為工件的路由，即調(diào)度機(jī)床)、AGV調(diào)度規(guī)則組合的方法研究此問題，并找到最合適的規(guī)則組合優(yōu)化調(diào)度。文獻(xiàn)[13]采用了一些常用的工件路由規(guī)則，文獻(xiàn)[14]回顧了多種AGV調(diào)度規(guī)則,這些規(guī)則都能有效解決車間調(diào)度問題，據(jù)此本文所采用的規(guī)則如表1所示：

表1 主要的優(yōu)先級(jí)規(guī)則

評(píng)價(jià)不同規(guī)則組合時(shí)，采用多重性能指標(biāo)如表2所示。

表2 規(guī)則組合及其所需AGV數(shù)量的評(píng)價(jià)指標(biāo)

1.3 規(guī)則組合下的AGV數(shù)量配置、任務(wù)到達(dá)模式問題描述

作為柔性作業(yè)車間的主流物料搬運(yùn)設(shè)備，AGV數(shù)量將對表2中的評(píng)價(jià)指標(biāo)產(chǎn)生較大影響：數(shù)量過少將導(dǎo)致搬運(yùn)任務(wù)不能得到及時(shí)處理，工件大量堆積在系統(tǒng)中，各指標(biāo)值過大，AGV過忙，可能造成無論采用何種規(guī)則組合同時(shí)調(diào)度機(jī)床與AGV，調(diào)度結(jié)果都十分不理想，所評(píng)價(jià)出的規(guī)則組合是沒有實(shí)際意義的；AGV數(shù)量過多，即便不會(huì)對評(píng)價(jià)指標(biāo)造成過大影響，也將直面資源浪費(fèi)問題。故需要確定出系統(tǒng)所需配置的AGV最佳數(shù)量?？紤]到不同規(guī)則組合可能對最佳AGV數(shù)量造成影響，故其需與規(guī)則組合同時(shí)評(píng)判。

在最優(yōu)規(guī)則組合以及最優(yōu)AGV數(shù)量配置下，系統(tǒng)性能不一定為最優(yōu)，為進(jìn)一步提升系統(tǒng)性能，可考慮前兩種條件最優(yōu)情況下任務(wù)到達(dá)模式影響，主要包括任務(wù)到達(dá)頻率和任務(wù)投產(chǎn)方式兩方面內(nèi)容，研究過程中，各影響因素可能相互制約，最后相互確定出各自的最優(yōu)選擇。

2 驗(yàn)證實(shí)例及建模仿真過程

2.1 實(shí)例描述

本研究所設(shè)計(jì)的柔性作業(yè)車間共包含6臺(tái)機(jī)床M1～M6，每臺(tái)機(jī)床具備1～2種加工技能，以滿足加工柔性。物料搬運(yùn)設(shè)備采用AGV。加工產(chǎn)品有4類分別為：J1、J2、J3和J4，每類產(chǎn)品包含4道工序，其工藝路線及每道工序可供選擇的機(jī)床及其加工時(shí)間如表3所示，如處理J1產(chǎn)品的第一道工序O11時(shí)可選擇M4、M5兩臺(tái)機(jī)床，選擇M4時(shí)，所需加工時(shí)間P11為100 s，選擇M5時(shí)，P11為70 s。

車間實(shí)際生產(chǎn)時(shí)，工件到達(dá)時(shí)間間隔服從泊松分布，泊松參數(shù)λ=140，每類工件待加工數(shù)量為250件，采用J1～J4順序生產(chǎn)投產(chǎn)方式，AGV數(shù)量待定，企圖在此生產(chǎn)條件下，找到車間性能最優(yōu)時(shí)的規(guī)則組合與所需AGV數(shù)量，以解決機(jī)床與AGV聯(lián)合調(diào)度問題。

聯(lián)合調(diào)度問題解決以后，可能存在原本的生產(chǎn)條件不合理的情況，為已找到的最優(yōu)規(guī)則組合匹配一個(gè)更合適的生產(chǎn)條件，將進(jìn)一步提升系統(tǒng)性能。此時(shí)規(guī)則組合為已知條件，待優(yōu)化參數(shù)為泊松參數(shù)λ，AGV數(shù)量，投產(chǎn)方式及批量等。

表3 每道工序可供選擇的機(jī)床集及加工時(shí)間

2.2 離散制造系統(tǒng)建模及仿真

PlantSimulation是一款面向?qū)ο蟮碾x散事件動(dòng)態(tài)系統(tǒng)仿真軟件，為建模、仿真運(yùn)行和顯示提供了一種完全面向?qū)ο蟮摹D形化的和集成的工作環(huán)境[17]。利用Plant Simulation對設(shè)計(jì)的柔性作業(yè)車間建模及控制過程如下：

(1)車間布局及建模

利用PlantSimulation對設(shè)計(jì)的柔性作業(yè)車間建模如圖1所示:建立6臺(tái)柔性機(jī)床，依次命名為M1、M2、M3、M4、M5和M6，每臺(tái)機(jī)床都有一個(gè)入口緩沖BufIn和出口緩沖BufOut,如BufInM1和BufOutM1。生產(chǎn)訂單由jobsource對象產(chǎn)生，產(chǎn)生的四類工件命名為J1、J2、J3和J4。AGV由AGVSource對象產(chǎn)生，其長度為1.5 m，行駛速度為1 m/s，加速度為0.5 m/s2，系統(tǒng)所能容納的AGV最大數(shù)量為6，AGV在沒有運(yùn)輸任務(wù)的情況下，將?？吭赑arking區(qū)域軌道(最左側(cè)軌道)上。所有工序加工完成的工件最終將被代表系統(tǒng)出口的Drain對象回收。

(2)仿真過程控制

仿真過程控制包括生產(chǎn)訂單控制、工藝流轉(zhuǎn)控制、物流運(yùn)輸任務(wù)控制3方面內(nèi)容。生產(chǎn)訂單由source對象控制，有順序生產(chǎn)和順序循環(huán)兩種投產(chǎn)方式，任務(wù)到達(dá)頻率也在此處設(shè)置。工藝流轉(zhuǎn)控制主要保證工件每加工完一道工序便能讀取到下步工序信息，以便后續(xù)加工任務(wù)展開。物流運(yùn)輸任務(wù)控制則實(shí)現(xiàn)工件在機(jī)床與機(jī)床之間流轉(zhuǎn)，流轉(zhuǎn)的搬運(yùn)任務(wù)由AGV完成。工件在進(jìn)入系統(tǒng)或加工完一道工序離開sourcebuf、BufOut等出口緩沖時(shí)將觸發(fā)路由控制程序，按待加工工序讀取該工件的工序表，然后按照給定的路由規(guī)則為該工件調(diào)度下道工序的加工機(jī)床并記錄其加工時(shí)間，同時(shí)工件在出口緩沖離開事件意味著搬運(yùn)任務(wù)的產(chǎn)生，此時(shí)觸發(fā)的路由程序還要將工件從當(dāng)前工序到達(dá)下步工序的搬運(yùn)任務(wù)信息實(shí)時(shí)存儲(chǔ)，這樣上層程序檢測到有待執(zhí)行搬運(yùn)任務(wù)時(shí)，將按照給定的調(diào)度規(guī)則為其調(diào)度空閑AGV，任務(wù)一旦被執(zhí)行，便從任務(wù)表中刪除。

3 仿真試驗(yàn)及結(jié)果分析

3.1 最優(yōu)規(guī)則組合及其所需AGV數(shù)量分析

本研究主要考慮上文提到的3種路由規(guī)則和3種調(diào)度規(guī)則的組合影響，共有9種規(guī)則組合待比較。仿真運(yùn)行時(shí)，利用試驗(yàn)管理器管理試驗(yàn)，在同一種規(guī)則組合下，AGV數(shù)量為1～6，每次試驗(yàn)重復(fù)5次，共進(jìn)行270次試驗(yàn)。

試驗(yàn)結(jié)果分析如下：圖2～4所示為9種規(guī)則組合下的3種性能指標(biāo)變化趨勢圖，在不同規(guī)則組合下，各指標(biāo)走勢相同，但各點(diǎn)數(shù)值有差異，該結(jié)果表明，采用規(guī)則調(diào)度方法能解決柔性作業(yè)車間中機(jī)床與AGV聯(lián)合調(diào)度問題，且針對同一車間存在一個(gè)最優(yōu)規(guī)則組合優(yōu)化調(diào)度結(jié)果。

從圖2～4可看出在所有規(guī)則組合下系統(tǒng)的性能指標(biāo)1工件平均流動(dòng)時(shí)間隨AGV數(shù)量增加呈逐步下降趨勢，在數(shù)量為4時(shí)開始趨于穩(wěn)定。性能指標(biāo)2完工時(shí)間隨AGV數(shù)量增加也呈逐步下降趨勢，且在AGV數(shù)量為3時(shí)穩(wěn)定，但此時(shí)的平均流動(dòng)時(shí)間值遠(yuǎn)大于AGV數(shù)量為4時(shí)的值，故AGV應(yīng)配置4輛，此時(shí)4輛AGV的平均利用率均在81%左右，相比3輛AGV時(shí)的88%左右平均利用率，配置4輛AGV時(shí)繁忙程度也更合適。綜合比較，該模型在所有規(guī)則組合下的小車數(shù)量最優(yōu)值為4。結(jié)果表明，在同一任務(wù)水平下，采用不同的規(guī)則組合不會(huì)對所需AGV最佳數(shù)量造成太大影響，但會(huì)在不同程度上改善系統(tǒng)性能。

在所有規(guī)則組合下，AGV數(shù)量為4時(shí)，系統(tǒng)性能達(dá)到穩(wěn)定，可采用此時(shí)的指標(biāo)值評(píng)判規(guī)則組合，由于完工時(shí)間與AGV平均利用率兩項(xiàng)指標(biāo)的穩(wěn)定值在不同規(guī)則組合下變化不大，故選擇平均流動(dòng)時(shí)間評(píng)判，其結(jié)果如圖5所示，可以發(fā)現(xiàn)無論何種調(diào)度規(guī)則下均為路由規(guī)則LWT優(yōu)于LUM，再遠(yuǎn)優(yōu)于SQ。無論何種路由規(guī)則情況下，調(diào)度規(guī)則均為STT最優(yōu)。最終確定該模型最適用的AGV數(shù)量與規(guī)則組合為：小車數(shù)量為4時(shí)的LWT/STT組合。為更直觀體現(xiàn)最優(yōu)規(guī)則組合對平均流動(dòng)時(shí)間影響，定義系統(tǒng)性能提升指數(shù)μ，按式(1)計(jì)算。

(1)

得到最優(yōu)規(guī)則組合較于其他組合系統(tǒng)性能最大提升6%。

3.2 最優(yōu)任務(wù)到達(dá)模式及其所需AGV數(shù)量分析

上文所找到的最優(yōu)規(guī)則組合，是在已知生產(chǎn)條件任務(wù)到達(dá)頻率服從泊松140分布，順序投產(chǎn)下研究的，針對此最優(yōu)規(guī)則組合，可能還將存在更優(yōu)的任務(wù)到達(dá)模式，進(jìn)一步提升系統(tǒng)性能。

(1)任務(wù)到達(dá)頻率分析

固定規(guī)則組合為STT/LWT，變化泊松參數(shù)λ值從40～220，AGV數(shù)量從1～6，研究最優(yōu)規(guī)則組合下最優(yōu)的任務(wù)到達(dá)頻率及所需AGV數(shù)量。仍采用試驗(yàn)管理器管理試驗(yàn)，每次試驗(yàn)重復(fù)5次，共進(jìn)行300次試驗(yàn)，試驗(yàn)結(jié)果分析如下：

如圖6所示，在不同的任務(wù)到達(dá)時(shí)間間隔下，工件的平均流動(dòng)時(shí)間隨AGV數(shù)量增加呈不同變化趨勢，具體趨勢分析及取舍結(jié)果如表4所示。

表4 不同值下平均流動(dòng)時(shí)間隨AGV數(shù)量增加變化趨勢

其中λ<100時(shí)，AGV數(shù)量增至5而平均流動(dòng)時(shí)間突增，這是由于各機(jī)床加工能力不足，任務(wù)投產(chǎn)頻率過快，工件被搬運(yùn)到機(jī)床入口緩沖區(qū)的頻率也過快，工件大量堆積在入口緩沖中，等待加工時(shí)間過長所造成的。

如圖7所示，相反增大任務(wù)到達(dá)時(shí)間間隔會(huì)不斷增大系統(tǒng)的完工時(shí)間。結(jié)合前面分析，完工時(shí)間指標(biāo)下，選擇泊松120、AGV數(shù)量為4的情況為最優(yōu)。從圖8可看出增大任務(wù)到達(dá)時(shí)間間隔也會(huì)不斷降低所需AGV的平均利用率，選擇泊松120、AGV數(shù)量為4的組合時(shí)AGV平均利用率為86.8%，利用率較高，應(yīng)選擇數(shù)量為5時(shí)，利用率為77.2%更合適，此時(shí)指標(biāo)1平均流動(dòng)時(shí)間相比于AGV數(shù)量為4時(shí)的20 min也更穩(wěn)定更低，為17 min，與最終的穩(wěn)定值更接近。

原生產(chǎn)條件泊松140分布時(shí)，在AGV數(shù)量為4時(shí)各指標(biāo)均達(dá)到最優(yōu)，雖然其平均流動(dòng)時(shí)間為16 min，利用率為81%，都比泊松120。5輛車時(shí)更好一些，實(shí)則很接近，但其完工時(shí)間高出6個(gè)多小時(shí)，最終確定最優(yōu)任務(wù)到達(dá)時(shí)間間隔服從泊松120分布，最佳配置AGV數(shù)量為5。

新確定的泊松120、AGV數(shù)量為5的生產(chǎn)條件，可能會(huì)對已確定的最優(yōu)規(guī)則造成影響，為驗(yàn)證此影響是否存在及是何影響，在此條件下再次進(jìn)行規(guī)則組合比較，驗(yàn)證結(jié)果如圖9所示，最優(yōu)規(guī)則組合仍為LWT/STT，試驗(yàn)前提條件成立，此時(shí)最優(yōu)規(guī)則組合下的平均流動(dòng)時(shí)間值較之其他組合系統(tǒng)性能提升指數(shù)μ最大達(dá)到26.8%，再次證明采用STT/LWT規(guī)則組合將提升系統(tǒng)性能，同時(shí)也說明不同的任務(wù)到達(dá)頻率將會(huì)影響規(guī)則組合對系統(tǒng)性能的提升指數(shù)，也有可能改變最優(yōu)規(guī)則組合：SQ路由規(guī)則由最次變?yōu)榇蝺?yōu)。兩種生產(chǎn)條件下系統(tǒng)性能穩(wěn)定時(shí)的平均流動(dòng)時(shí)間值相差不大，為更直觀表達(dá)改變?nèi)蝿?wù)到達(dá)頻率對系統(tǒng)性能影響，定義完工時(shí)間指標(biāo)下的系統(tǒng)性能提升指數(shù)φ，按式(2) 計(jì)算：

(2)

得到泊松120、AGV數(shù)量為5情況下系統(tǒng)性能較之泊松140、AGV數(shù)量為4時(shí)提升18%。

(2)任務(wù)到達(dá)方式分析

在最優(yōu)規(guī)則組合、最優(yōu)任務(wù)到達(dá)時(shí)間間隔下，選擇最優(yōu)任務(wù)到達(dá)方式，包含投產(chǎn)方式與批量兩方面內(nèi)容。具體試驗(yàn)內(nèi)容如表5所示。

表5 任務(wù)到達(dá)方式試驗(yàn)內(nèi)容

第1、2種任務(wù)到達(dá)方式下的仿真結(jié)果如圖10～11所示，在小車數(shù)量為5時(shí)，系統(tǒng)的加工能力分別飽和在5 030件與5 027件，相差不大，但后者工件的平均流動(dòng)時(shí)間增加了近兩分鐘。故前一種到達(dá)方式更好。

第3種到達(dá)方式下的仿真結(jié)果如圖12～13所示，結(jié)果表明在泊松120到達(dá)時(shí)間間隔下，一旦任務(wù)一次到達(dá)兩個(gè)及以上，工件在系統(tǒng)中的平均流動(dòng)時(shí)間將大幅增加，而系統(tǒng)加工能力卻得不到大幅提升，這是由于工件一次到達(dá)過多而機(jī)床加工能力不足所造成的。故適應(yīng)該模型最優(yōu)的任務(wù)到達(dá)方式應(yīng)為順序投產(chǎn)、批量為1。

4 結(jié)語

柔性作業(yè)車間機(jī)床與AGV聯(lián)合調(diào)度問題是典型NP難問題，求解過程具有一定復(fù)雜度，為此采用基于優(yōu)先級(jí)規(guī)則組合的方法，本文考慮了工件路由規(guī)則和AGV調(diào)度規(guī)則兩方面的規(guī)則組合，基于離散事件建模與仿真方法對9種規(guī)則組合進(jìn)行對比研究，結(jié)果表明，將LWT作為工件路由規(guī)則、STT作為AGV調(diào)度規(guī)則可提供良好的結(jié)果，在此種規(guī)則組合下，進(jìn)一步可確定最優(yōu)的任務(wù)到達(dá)模式為采用順序投產(chǎn)、批量為1、到達(dá)頻率服從泊松120分布，以及系統(tǒng)應(yīng)配置AGV的最佳數(shù)量為5。在這些最優(yōu)條件下，系統(tǒng)性能平均流動(dòng)時(shí)間將縮短26.8%、完工時(shí)間將縮短18%，證明了采用合適的優(yōu)先級(jí)規(guī)則組合、任務(wù)到達(dá)模式以及AGV數(shù)量可以有效解決機(jī)床與AGV聯(lián)合調(diào)度問題、優(yōu)化系統(tǒng)生產(chǎn)性能。