郭沛佩 付建林 江海凡 王 坤

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

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

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

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

1 問題描述

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

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

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

(2)同一時刻，同一臺機器只能加工1個工件的某道工序。

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

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

(5)同一AGV1次只能運輸一個工件。

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

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

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

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

評價不同規(guī)則組合時，采用多重性能指標如表2所示。

表2 規(guī)則組合及其所需AGV數(shù)量的評價指標

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

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

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

2 驗證實例及建模仿真過程

2.1 實例描述

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

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

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

表3 每道工序可供選擇的機床集及加工時間

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

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

(1)車間布局及建模

利用PlantSimulation對設(shè)計的柔性作業(yè)車間建模如圖1所示:建立6臺柔性機床，依次命名為M1、M2、M3、M4、M5和M6，每臺機床都有一個入口緩沖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在沒有運輸任務的情況下，將?？吭赑arking區(qū)域軌道(最左側(cè)軌道)上。所有工序加工完成的工件最終將被代表系統(tǒng)出口的Drain對象回收。

(2)仿真過程控制

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

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

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

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

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

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

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

(1)

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

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

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

(1)任務到達頻率分析

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

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

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

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

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

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

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

(2)

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

(2)任務到達方式分析

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

表5 任務到達方式試驗內(nèi)容

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

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

4 結(jié)語

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