基于零件虛擬工序隊列的FMS動態(tài)調(diào)度研究

1、基于零件虛擬工序隊列的FMS動態(tài)調(diào)度研究    摘要提出虛擬工序隊列的概念，并在此基礎(chǔ)上提出一種基于靜態(tài)零件分批（靜態(tài)調(diào)度）的FMS動態(tài)生產(chǎn)調(diào)度方法，該算法充分考慮到FMS的系統(tǒng)資源限制及零件運輸?shù)拳h(huán)節(jié)，能較好地解決生產(chǎn)調(diào)度中的設(shè)備負荷平衡、系統(tǒng)緊急事件發(fā)生（如機床故障、新零件加入等）、可替代加工工序等問題，且易于實現(xiàn)，具有較廣泛的適應(yīng)性。關(guān)鍵詞FMS零件虛擬工序隊列動態(tài)調(diào)度調(diào)度規(guī)則中國圖書資料分類法分類號TH165TP271 DynamicSchedulingBasedonVirtualOperationQueueofPartforFMSs ZhaoT

2、ianqi(TsinghuaUniversity,Beijing,China)ChenYuliuLiPeigenp1367-1369 對于有效地利用已有FMS中的各種資源提高生產(chǎn)效率而言，合理完善的調(diào)度控制系統(tǒng)是關(guān)鍵。調(diào)度是指在時間意義上所有系統(tǒng)資源的定位、分配和處理，其系統(tǒng)分為加工子系統(tǒng)和運輸子系統(tǒng)(刀具流系統(tǒng)和物料流系統(tǒng))，其調(diào)度分為靜態(tài)調(diào)度和動態(tài)調(diào)度。FMS的調(diào)度控制比較復(fù)雜，尤其當(dāng)涉及的因素較多時，若要根據(jù)某一調(diào)度目標(biāo)得到最優(yōu)調(diào)度結(jié)果，往往很難滿足實時性的要求。其實，多數(shù)情況下調(diào)度目標(biāo)是人為的，F(xiàn)MS調(diào)度只要得到近優(yōu)解即可1，2。本文在零件靜態(tài)分批的基礎(chǔ)上提出零件虛擬工序隊列的概念，并

3、在此基礎(chǔ)上提出1個解決FMS動態(tài)生產(chǎn)調(diào)度的啟發(fā)式調(diào)度算法。 1FMS調(diào)度問題描述FMS動態(tài)調(diào)度及零件靜態(tài)分批之間的關(guān)系見圖1。這里所研究的動態(tài)調(diào)度是在零件靜態(tài)分批的基礎(chǔ)上以分好的零件子批為加工任務(wù)進行調(diào)度的3，4。因在加工任務(wù)靜態(tài)分批階段已充分考慮了系統(tǒng)的部分資源(如裝卸站、緩沖站、刀具、夾具、托盤等因素)，故在此不需考慮。 圖1動態(tài)調(diào)度與零件靜態(tài)分批之間的關(guān)系 FMS動態(tài)調(diào)度的目標(biāo)是使系統(tǒng)具有較好的加工性能，一方面能使系統(tǒng)具有較高的生產(chǎn)率，即較高的設(shè)備利用率，另一方面能及時完成給定的加工任務(wù)。在本文中，調(diào)度主要考慮2方面的性能，即盡量滿足加工任務(wù)中零件的交貨期和盡可能減少系統(tǒng)生產(chǎn)時間。用以下

4、2個指標(biāo)來描述：工件平均延誤時間（meantardiness，MT）和工件平均流通時間（meanflow-time，MFT）。MT反映零件是否滿足交貨期，MFT則反映工件在系統(tǒng)中的駐留時間，能較全面地反映系統(tǒng)生產(chǎn)時間。調(diào)度目標(biāo) f=minW1×MT+W2×MFT 式中，W1、W2為權(quán)值；×反映調(diào)度目標(biāo)中MT和MFT的側(cè)重程度。 2零件虛擬工序隊列的概念及特點零件在FMS中加工的過程可用排隊理論和方法來描述，由于加工中影響因素較多，如零件的某些工序存在可替代加工工序和零件的加工工序之間的加工先后關(guān)系的柔性等。這些因素給系統(tǒng)性能的提高創(chuàng)造了有利的條件，但無疑也為系統(tǒng)的

5、調(diào)度控制系統(tǒng)的實現(xiàn)增加了難度。這也是目前大多數(shù)調(diào)度控制系統(tǒng)采用固定加工工藝的主要原因之一。利用本文提出的零件虛擬工序隊列方法可大幅度降低調(diào)度問題的復(fù)雜性。零件虛擬工序隊列方法的基本原理見圖2。假設(shè)系統(tǒng)內(nèi)的每一臺機床前都存在一隊列(集合)，該集合中存放的是當(dāng)前該設(shè)備能夠加工的工序(機床的可加工工序集合)。在調(diào)度開始時各設(shè)備前可加工工序集合為空(也可按給定系統(tǒng)狀態(tài)設(shè)定)，當(dāng)有新零件進入系統(tǒng)或設(shè)備加工完一零件時，首先判明該零件當(dāng)前能加工的工序及其對應(yīng)的機床，然后使這些工序進入對應(yīng)機床的可加工工序集合中。若當(dāng)前可調(diào)度工序存在可替代加工工序，則該工序同時加入到對應(yīng)設(shè)備的可加工工序集合中。設(shè)備的下一個加工

6、零件是在該機床的可加工工序集合中按一定的規(guī)則進行選擇的。當(dāng)機床選擇好1個工序后，從所有設(shè)備的可加工工序集合中刪去該工序?qū)?yīng)的零件的所有工序，從而避免不同設(shè)備同時選擇同一零件的情況。 圖2零件虛擬工序隊列概念圖 采用零件虛擬工序隊列方法有如下特點：(1)有廣泛的適應(yīng)性。對機床故障、緊急零件進入、可替代加工工序以及改變調(diào)度目標(biāo)等通常意義上的重調(diào)度情況都很容易處理。(2)避免了算法中零件在不同的機床隊列之間不必要的相互傳送及調(diào)整。(3)在零件優(yōu)化分批的基礎(chǔ)上，可實現(xiàn)批內(nèi)各機床加工負荷的近似自動平衡。機床最大負荷不均衡量為零件的最后一道加工工序的加工時間。(4)適用于多種零件的混流生產(chǎn)，也適用于傳統(tǒng)的

7、JobShop生產(chǎn)。(5)簡化了FMS動態(tài)調(diào)度控制中的規(guī)則系統(tǒng)，使得調(diào)度控制更易于實現(xiàn)。用零件虛擬工序隊列方法保證了各加工設(shè)備加工負荷的近似均衡，若結(jié)合合適的調(diào)度規(guī)則在機床的可調(diào)度零件集合中選擇合適的加工零件，所得到的結(jié)果必為系統(tǒng)的近優(yōu)解甚至最優(yōu)解。 3基于零件虛擬工序隊列的FMS啟發(fā)式動態(tài)調(diào)度算法該算法是在加工任務(wù)分批的基礎(chǔ)上，同時考慮了工件運輸系統(tǒng)的影響而提出的。機床前輸入/輸出緩沖站配置不同，其調(diào)度算法略有不同。本文針對機床前具有1個輸入和1個輸出緩沖器的典型FMS情況進行研究，提出動態(tài)調(diào)度算法，其流程圖見圖3。 圖3FMS動態(tài)調(diào)度原理圖 在調(diào)度算法中提出了系統(tǒng)決策點的確定方法。通過計算

8、各機床上所有工件的加工完成時刻，確定具有最小加工完成時間的機床，把該機床當(dāng)前加工工件的加工完成時刻作為決策點。該方法一方面全面考慮了各機床的加工負荷情況，另一方面也找出了系統(tǒng)中最迫切需要調(diào)度決策的機床進行決策和運輸，從而提高整個加工和運輸系統(tǒng)的利用率，使總加工時間最短。設(shè)備在加工過程中情況主要有6種（見圖4）。圖4a和圖4b中，系統(tǒng)中各機床均有工件加工，且輸入存儲器中皆有待加工工件，選擇t2時刻最小的機床（機床2）的t1時刻作為決策點tD。 圖4機床工件選擇的決策點分析示意圖 圖4c和圖4d中，此時系統(tǒng)中有機床（機床1）輸入存儲器中無待加工工件（t2=），找出t2最小的機床（機床3）的t1作為

9、決策點tD。圖4e和圖4f中，此時系統(tǒng)中有機床（機床1）當(dāng)前為空閑狀態(tài)，同樣找出t2最小的機床（機床2）的t1作為決策點tD。除上面幾種情況外，還有1種特殊情況，即各機床輸入存儲器中都為空、各機床或空閑、或只有1個工件。此時把新工件進入系統(tǒng)時刻或系統(tǒng)中工件的工序加工完成時刻作為系統(tǒng)的決策點。在算法中提出的動態(tài)預(yù)調(diào)度方法，能在系統(tǒng)決策點處預(yù)先決策好機床待加工的零件，并通知零件運輸系統(tǒng)送入機床的輸入緩沖站中，這樣當(dāng)機床加工好零件后可直接通過托盤交換裝置把機床上的零件送入輸出緩沖站，并把輸入緩沖站中的零件送入機床。零件的動態(tài)預(yù)調(diào)度能顯著地減少機床的等待時間，提高機床的生產(chǎn)率。為了實現(xiàn)調(diào)度目標(biāo)，提出調(diào)

10、度規(guī)則的動態(tài)選擇方法，即根據(jù)系統(tǒng)的主調(diào)度目標(biāo)，確定系統(tǒng)的主調(diào)度規(guī)則。在系統(tǒng)中未出現(xiàn)特殊情況時，用主調(diào)度規(guī)則實現(xiàn)對系統(tǒng)的調(diào)度；若出現(xiàn)特殊情況，則根據(jù)系統(tǒng)的輔助調(diào)度目標(biāo)和特殊狀況的類型確定輔助調(diào)度規(guī)則。主調(diào)度規(guī)則和輔助調(diào)度規(guī)則在系統(tǒng)中的動態(tài)選擇，使系統(tǒng)可達到較好的主調(diào)度目標(biāo)和輔助調(diào)度目標(biāo)。本文通過采用最小松弛時間和零件優(yōu)先級規(guī)則可使MT最小，從而保證零件的交貨期。 4實例仿真根據(jù)上面提出的零件虛擬工序隊列的概念及動態(tài)調(diào)度算法，以直線型雙排布局的FMS為例，在我們所研制的FMS動態(tài)調(diào)度仿真系統(tǒng)上對1個典型的加工任務(wù)進行仿真試驗。該FMS由5臺加工中心、1臺AGV（正常運行速度為0.2m/s）、1個裝

11、卸站、8個緩沖站和8個可用托盤組成。零件的某一子批加工計劃（指經(jīng)靜態(tài)分批后生成的子加工計劃）見表1，零件的加工工藝見表2，在沒有對動態(tài)調(diào)度仿真系統(tǒng)進行人工干預(yù)的情況下經(jīng)過14.29332min的仿真試驗得出仿真結(jié)果。系統(tǒng)總加工時間為23.8222h，總生產(chǎn)率為2.3955件/h,所用托盤數(shù)為6個。表3給出了機床和運輸小車的仿真性能結(jié)果。因考慮了零件的可替代加工工序，且是在零件靜態(tài)分批的基礎(chǔ)上進行的，所以無法提供可供比較的例子。 表1零件的子批加工計劃 零件編號批量交貨期（天）零件優(yōu)先級對應(yīng)托盤數(shù)A120311A212212A325321A424221A524311表2零件加工工藝及可替代加工工

12、序 零件編號工序加工時間(min)機床1機床2機床3機床4機床5A1 12025225252331012A216065702252020A3 1405024040353354040A4120202302525A5 130202252525315121544525表3對該子批零件的調(diào)度結(jié)果 通過對調(diào)度結(jié)果的分析可知，本文提出的基于零件虛擬工序隊列的動態(tài)調(diào)度算法是切實可行的。*國家科學(xué)技術(shù)部重大攻關(guān)計劃資助項目和國家863高技術(shù)發(fā)展計劃資助項目(8635119608004)作者簡介：趙天奇男，1965年生。清華大學(xué)（北京市100084）自動化系博士后研究人員、工學(xué)博士。研究方向為敏捷制造、并行工程、ERP、企業(yè)過程管理與優(yōu)化。發(fā)表論