零件虛擬工序隊列動態論文

導語：零件虛擬工序隊列動態論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

關鍵詞FMS零件虛擬工序隊列動態調度調度規則

中國圖書資料分類法分類號TH165TP271

DynamicSchedulingBasedonVirtualOperationQueueofPartforFMSs

ZhaoTianqi(TsinghuaUniversity,Beijing,China)ChenYuliuLiPeigenp1367-1369

Abstract:InthispaperaconceptofVirtualOperationQueueofpartisproposed,adynamicproductionschedulingalgorithmispresentedbasedonstaticbatchingofFMSs.Therestrictsofmanufacturingresources,influenceofparthandlingsystemandsomeemergencyevents(e.g.machinebreakdown,rushorderjoiningetc.),alternativeoperations,etc.areconsideredinthealgorithm.Thealgorithmiseasytoberealized,andcanbeappliedtodynamicschedulingformosttypesofFMSs,whichhaveoneormoreAGVsandhavelinearorlooplayout.

Keywords:FMSVirtualOperationQueueofPartDynamicschedulingDispatchingRule

對于有效地利用已有FMS中的各種資源提高生產效率而言，合理完善的調度控制系統是關鍵。調度是指在時間意義上所有系統資源的定位、分配和處理，其系統分為加工子系統和運輸子系統(刀具流系統和物料流系統)，其調度分為靜態調度和動態調度。FMS的調度控制比較復雜，尤其當涉及的因素較多時，若要根據某一調度目標得到最優調度結果，往往很難滿足實時性的要求。其實，多數情況下調度目標是人為的，FMS調度只要得到近優解即可［1，2］。

本文在零件靜態分批的基礎上提出零件虛擬工序隊列的概念，并在此基礎上提出1個解決FMS動態生產調度的啟發式調度算法。

1FMS調度問題描述

FMS動態調度及零件靜態分批之間的關系見圖1。這里所研究的動態調度是在零件靜態分

批的基礎上以分好的零件子批為加工任務進行調度的［3，4］。因在加工任務靜態分批階段已充分考慮了系統的部分資源(如裝卸站、緩沖站、刀具、夾具、托盤等因素)，故在此不需考慮。

圖1動態調度與零件靜態分批之間的關系

FMS動態調度的目標是使系統具有較好的加工性能，一方面能使系統具有較高的生產率，即較高的設備利用率，另一方面能及時完成給定的加工任務。在本文中，調度主要考慮2方面的性能，即盡量滿足加工任務中零件的交貨期和盡可能減少系統生產時間。用以下2個指標來描述：工件平均延誤時間（meantardiness，MT）和工件平均流通時間（meanflow-time，MFT）。

MT反映零件是否滿足交貨期，MFT則反映工件在系統中的駐留時間，能較全面地反映系統生產時間。調度目標

f=min{W1×MT+W2×MFT}

式中，W1、W2為權值；×反映調度目標中MT和MFT的側重程度。

2零件虛擬工序隊列的概念及特點

零件在FMS中加工的過程可用排隊理論和方法來描述，由于加工中影響因素較多，如零件的某些工序存在可替代加工工序和零件的加工工序之間的加工先后關系的柔性等。這些因素給系統性能的提高創造了有利的條件，但無疑也為系統的調度控制系統的實現增加了難度。這也是目前大多數調度控制系統采用固定加工工藝的主要原因之一。利用本文提出的零件虛擬工序隊列方法可大幅度降低調度問題的復雜性。

零件虛擬工序隊列方法的基本原理見圖2。假設系統內的每一臺機床前都存在一隊列(集合)，該集合中存放的是當前該設備能夠加工的工序(機床的可加工工序集合)。在調度開始時各設備前可加工工序集合為空(也可按給定系統狀態設定)，當有新零件進入系統或設備加工完一零件時，首先判明該零件當前能加工的工序及其對應的機床，然后使這些工序進入對應機床的可加工工序集合中。若當前可調度工序存在可替代加工工序，則該工序同時加入到對應設備的可加工工序集合中。設備的下一個加工零件是在該機床的可加工工序集合中按一定的規則進行選擇的。當機床選擇好1個工序后，從所有設備的可加工工序集合中刪去該工序對應的零件的所有工序，從而避免不同設備同時選擇同一零件的情況。

圖2零件虛擬工序隊列概念圖

采用零件虛擬工序隊列方法有如下特點：

(1)有廣泛的適應性。對機床故障、緊急零件進入、可替代加工工序以及改變調度目標等通常意義上的重調度情況都很容易處理。

(2)避免了算法中零件在不同的機床隊列之間不必要的相互傳送及調整。

(3)在零件優化分批的基礎上，可實現批內各機床加工負荷的近似自動平衡。機床最大負荷不均衡量為零件的最后一道加工工序的加工時間。

(4)適用于多種零件的混流生產，也適用于傳統的Job－Shop生產。

(5)簡化了FMS動態調度控制中的規則系統，使得調度控制更易于實現。

用零件虛擬工序隊列方法保證了各加工設備加工負荷的近似均衡，若結合合適的調度規則在機床的可調度零件集合中選擇合適的加工零件，所得到的結果必為系統的近優解甚至最優解。

3基于零件虛擬工序隊列的FMS啟發式動態調度算法

該算法是在加工任務分批的基礎上，同時考慮了工件運輸系統的影響而提出的。機床前輸入/輸出緩沖站配置不同，其調度算法略有不同。本文針對機床前具有1個輸入和1個輸出緩沖器的典型FMS情況進行研究，提出動態調度算法，其流程圖見圖3。

圖3FMS動態調度原理圖

在調度算法中提出了系統決策點的確定方法。通過計算各機床上所有工件的加工完成時刻，確定具有最小加工完成時間的機床，把該機床當前加工工件的加工完成時刻作為決策點。該方法一方面全面考慮了各機床的加工負荷情況，另一方面也找出了系統中最迫切需要調度決策的機床進行決策和運輸，從而提高整個加工和運輸系統的利用率，使總加工時間最短。

設備在加工過程中情況主要有6種（見圖4）。圖4a和圖4b中，系統中各機床均有工件加工，且輸入存儲器中皆有待加工工件，選擇t2時刻最小的機床（機床2）的t1時刻作為決策點tD。

圖4機床工件選擇的決策點分析示意圖

圖4c和圖4d中，此時系統中有機床（機床1）輸入存儲器中無待加工工件（t2=∞），找出t2最小的機床（機床3）的t1作為決策點tD。

圖4e和圖4f中，此時系統中有機床（機床1）當前為空閑狀態，同樣找出t2最小的機床（機床2）的t1作為決策點tD。

除上面幾種情況外，還有1種特殊情況，即各機床輸入存儲器中都為空、各機床或空閑、或只有1個工件。此時把新工件進入系統時刻或系統中工件的工序加工完成時刻作為系統的決策點。

在算法中提出的動態預調度方法，能在系統決策點處預先決策好機床待加工的零件，并通知零件運輸系統送入機床的輸入緩沖站中，這樣當機床加工好零件后可直接通過托盤交換裝置把機床上的零件送入輸出緩沖站，并把輸入緩沖站中的零件送入機床。零件的動態預調度能顯著地減少機床的等待時間，提高機床的生產率。

為了實現調度目標，提出調度規則的動態選擇方法，即根據系統的主調度目標，確定系統的主調度規則。在系統中未出現特殊情況時，用主調度規則實現對系統的調度；若出現特殊情況，則根據系統的輔助調度目標和特殊狀況的類型確定輔助調度規則。主調度規則和輔助調度規則在系統中的動態選擇，使系統可達到較好的主調度目標和輔助調度目標。本文通過采用最小松弛時間和零件優先級規則可使MT最小，從而保證零件的交貨期。

4實例仿真

根據上面提出的零件虛擬工序隊列的概念及動態調度算法，以直線型雙排布局的FMS為例，在我們所研制的FMS動態調度仿真系統上對1個典型的加工任務進行仿真試驗。該FMS由5臺加工中心、1臺AGV（正常運行速度為0.2m/s）、1個裝卸站、8個緩沖站和8個可用托盤組成。零件的某一子批加工計劃（指經靜態分批后生成的子加工計劃）見表1，零件的加工工藝見表2，在沒有對動態調度仿真系統進行人工干預的情況下經過14.29332min的仿真試驗得出仿真結果。系統總加工時間為23.8222h，總生產率為2.3955件/h,所用托盤數為6個。表3給出了機床和運輸小車的仿真性能結果。因考慮了零件的可替代加工工序，且是在零件靜態分批的基礎上進行的，所以無法提供可供比較的例子。

表1零件的子批加工計劃

零件編號批量交貨期（天）零件優先級對應托盤數A120311A212212A325321A424221A524311表2零件加工工藝及可替代加工工序

零件

編號工序加工時間(min)機床1機床2機床3機床4機床5A1

120—25——2—25—252331012———A2

160—6570—2—2520—20A3

1——40—5024040—35—3—3540—40A4

1—2020——2—30—2525A5

130—20——2—25—25253151215——4—45——25表3對該子批零件的調度結果

機床

編號利用率

(%)通過工

件數加工時間

（h）生產率

（件/h）MC178.7773817.50021.5951MC289.132620.36611.0914MC386.2622419.74961.0075MC452.3332411.66681.0075MC578.9872517.98341.0494AGV140.392---

通過對調度結果的分析可知，本文提出的基于零件虛擬工序隊列的動態調度算法是切實可行的。

*國家科學技術部重大攻關計劃資助項目和國家863高技術發展計劃資助項目(863—511—9608—004)

作者簡介：趙天奇男，1965年生。清華大學（北京市100084）自動化系博士后研究人員、工學博士。研究方向為敏捷制造、并行工程、ERP、企業過程管理與優化。20余篇。

作者單位：陳禹六北京市100084清華大學

李培根武漢市430074華中理工大學

參考文獻

1.鄧子瓊.FMS建模及仿真.北京:國防工業出版社,1993:58～96

2.趙天奇,李培根，段正澄.華中理工大學學報，1998,26(2):12～14

3.AndrewKusiak.IntelligentManufacturingSystems.NewYork:PrenticeHall,Inc.,1990:125～143

4.ChungDaeYoung,putersInd.Engin.，1996,31(3):557～568