郭沛佩 付建林 江海凡 王 坤

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

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

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

本文采用離散事件建模仿真方法搭建了一個柔性作業(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)的任務(wù)到達模式與AGV數(shù)量，得到柔性生產(chǎn)車間性能最優(yōu)時的最佳規(guī)則組合、最佳AGV數(shù)量和最佳任務(wù)達到模式。

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ù)量配置、任務(wù)到達模式問題描述

作為柔性作業(yè)車間的主流物料搬運設(shè)備，AGV數(shù)量將對表2中的評價指標產(chǎn)生較大影響：數(shù)量過少將導(dǎo)致搬運任務(wù)不能得到及時處理，工件大量堆積在系統(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)情況下任務(wù)到達模式影響，主要包括任務(wù)到達頻率和任務(wù)投產(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在沒有運輸任務(wù)的情況下，將?？吭赑arking區(qū)域軌道(最左側(cè)軌道)上。所有工序加工完成的工件最終將被代表系統(tǒng)出口的Drain對象回收。

(2)仿真過程控制

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

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

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

本研究主要考慮上文提到的3種路由規(guī)則和3種調(diào)度規(guī)則的組合影響，共有9種規(guī)則組合待比較。仿真運行時，利用試驗管理器管理試驗，在同一種規(guī)則組合下，AGV數(shù)量為1～6，每次試驗重復(fù)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應(yīng)配置4輛，此時4輛AGV的平均利用率均在81%左右，相比3輛AGV時的88%左右平均利用率，配置4輛AGV時繁忙程度也更合適。綜合比較，該模型在所有規(guī)則組合下的小車數(shù)量最優(yōu)值為4。結(jié)果表明，在同一任務(wù)水平下，采用不同的規(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)任務(wù)到達模式及其所需AGV數(shù)量分析

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

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

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

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

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

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

如圖7所示，相反增大任務(wù)到達時間間隔會不斷增大系統(tǒng)的完工時間。結(jié)合前面分析，完工時間指標下，選擇泊松120、AGV數(shù)量為4的情況為最優(yōu)。從圖8可看出增大任務(wù)到達時間間隔也會不斷降低所需AGV的平均利用率，選擇泊松120、AGV數(shù)量為4的組合時AGV平均利用率為86.8%，利用率較高，應(yīng)選擇數(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)任務(wù)到達時間間隔服從泊松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)性能，同時也說明不同的任務(wù)到達頻率將會影響規(guī)則組合對系統(tǒng)性能的提升指數(shù)，也有可能改變最優(yōu)規(guī)則組合：SQ路由規(guī)則由最次變?yōu)榇蝺?yōu)。兩種生產(chǎn)條件下系統(tǒng)性能穩(wěn)定時的平均流動時間值相差不大，為更直觀表達改變?nèi)蝿?wù)到達頻率對系統(tǒng)性能影響，定義完工時間指標下的系統(tǒng)性能提升指數(shù)φ，按式(2) 計算：

(2)

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

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

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

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

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

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

4 結(jié)語

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