- 相關(guān)推薦
基于零件虛擬工序隊(duì)列的FMS動(dòng)態(tài)調(diào)度研究
基于零件虛擬工序隊(duì)列的FMS動(dòng)態(tài)調(diào)度研究
使用者請(qǐng)注明文章內(nèi)容出處
趙天奇陳禹六李培根 摘要提出虛擬工序隊(duì)列的概念，并在此基礎(chǔ)上提出一種基于靜態(tài)零件分批（靜態(tài)調(diào)度）的FMS動(dòng)態(tài)生產(chǎn)調(diào)度方法，該算法充分考慮到FMS的系統(tǒng)資源限制及零件運(yùn)輸?shù)拳h(huán)節(jié)，能較好地解決生產(chǎn)調(diào)度中的設(shè)備負(fù)荷平衡、系統(tǒng)緊急事件發(fā)生（如機(jī)床故障、新零件加入等）、可替代加工工序等問題，且易于實(shí)現(xiàn)，具有較廣泛的適應(yīng)性。
關(guān)鍵詞FMS零件虛擬工序隊(duì)列動(dòng)態(tài)調(diào)度調(diào)度規(guī)則
中國(guó)圖書資料分類法分類號(hào)TH165TP271 Dynamic Scheduling Based on Virtual Operation Queue of Part for FMSs Zhao Tianqi(Tsinghua University,Beijing,China)ChenYuliuLi Peigenp 1367-1369 Abstract: In this paper a concept of Virtual Operation Queue of part is proposed, a dynamic production scheduling algorithm is presented based on static batching of FMSs. The restricts of manufacturing resources, influence of part handling system and some emergency events (e.g. machine breakdown, rush order joining etc.), alternative operations, etc. are considered in the algorithm. The algorithm is easy to be realized, and can be applied to dynamic scheduling for most types of FMSs, which have one or more AGVs and have linear or loop layout.
Key words:FMSVirtual Operation Queue of PartDynamic schedulingDispatching Rule 對(duì)于有效地利用已有FMS中的各種資源提高生產(chǎn)效率而言，合理完善的調(diào)度控制系統(tǒng)是關(guān)鍵。調(diào)度是指在時(shí)間意義上所有系統(tǒng)資源的定位、分配和處理，其系統(tǒng)分為加工子系統(tǒng)和運(yùn)輸子系統(tǒng)(刀具流系統(tǒng)和物料流系統(tǒng))，其調(diào)度分為靜態(tài)調(diào)度和動(dòng)態(tài)調(diào)度。FMS的調(diào)度控制比較復(fù)雜，尤其當(dāng)涉及的因素較多時(shí)，若要根據(jù)某一調(diào)度目標(biāo)得到最優(yōu)調(diào)度結(jié)果，往往很難滿足實(shí)時(shí)性的要求。其實(shí)，多數(shù)情況下調(diào)度目標(biāo)是人為的，F(xiàn)MS調(diào)度只要得到近優(yōu)解即可［1，2］。
本文在零件靜態(tài)分批的基礎(chǔ)上提出零件虛擬工序隊(duì)列的概念，并在此基礎(chǔ)上提出1個(gè)解決FMS動(dòng)態(tài)生產(chǎn)調(diào)度的啟發(fā)式調(diào)度算法。 1FMS調(diào)度問題描述
FMS動(dòng)態(tài)調(diào)度及零件靜態(tài)分批之間的關(guān)系見圖1。這里所研究的動(dòng)態(tài)調(diào)度是在零件靜態(tài)分
批的基礎(chǔ)上以分好的零件子批為加工任務(wù)進(jìn)行調(diào)度的［3，4］。因在加工任務(wù)靜態(tài)分批階段已充分考慮了系統(tǒng)的部分資源(如裝卸站、緩沖站、刀具、夾具、托盤等因素)，故在此不需考慮。
圖1動(dòng)態(tài)調(diào)度與零件靜態(tài)分批之間的關(guān)系 FMS動(dòng)態(tài)調(diào)度的目標(biāo)是使系統(tǒng)具有較好的加工性能，一方面能使系統(tǒng)具有較高的生產(chǎn)率，即較高的設(shè)備利用率，另一方面能及時(shí)完成給定的加工任務(wù)。在本文中，調(diào)度主要考慮2方面的性能，即盡量滿足加工任務(wù)中零件的交貨期和盡可能減少系統(tǒng)生產(chǎn)時(shí)間。用以下2個(gè)指標(biāo)來描述：工件平均延誤時(shí)間（mean tardiness，MT）和工件平均流通時(shí)間（mean flow-time，MFT）。
MT反映零件是否滿足交貨期，MFT則反映工件在系統(tǒng)中的駐留時(shí)間，能較全面地反映系統(tǒng)生產(chǎn)時(shí)間。調(diào)度目標(biāo) f=min{W1×MT+W2×MFT} 式中，W1、W2為權(quán)值；×反映調(diào)度目標(biāo)中MT和MFT的側(cè)重程度。 2零件虛擬工序隊(duì)列的概念及特點(diǎn)
零件在FMS中加工的過程可用排隊(duì)理論和方法來描述，由于加工中影響因素較多，如零件的某些工序存在可替代加工工序和零件的加工工序之間的加工先后關(guān)系的柔性等。這些因素給系統(tǒng)性能的提高創(chuàng)造了有利的條件，但無疑也為系統(tǒng)的調(diào)度控制系統(tǒng)的實(shí)現(xiàn)增加了難度。這也是目前大多數(shù)調(diào)度控制系統(tǒng)采用固定加工工藝的主要原因之一。利用本文提出的零件虛擬工序隊(duì)列方法可大幅度降低調(diào)度問題的復(fù)雜性。
零件虛擬工序隊(duì)列方法的基本原理見圖2。假設(shè)系統(tǒng)內(nèi)的每一臺(tái)機(jī)床前都存在一隊(duì)列(集合)，該集合中存放的是當(dāng)前該設(shè)備能夠加工的工序(機(jī)床的可加工工序集合)。在調(diào)度開始時(shí)各設(shè)備前可加工工序集合為空(也可按給定系統(tǒng)狀態(tài)設(shè)定)，當(dāng)有新零件進(jìn)入系統(tǒng)或設(shè)備加工完一零件時(shí)，首先判明該零件當(dāng)前能加工的工序及其對(duì)應(yīng)的機(jī)床，然后使這些工序進(jìn)入對(duì)應(yīng)機(jī)床的可加工工序集合中。若當(dāng)前可調(diào)度工序存在可替代加工工序，則該工序同時(shí)加入到對(duì)應(yīng)設(shè)備的可加工工序集合中。設(shè)備的下一個(gè)加工零件是在該機(jī)床的可加工工序集合中按一定的規(guī)則進(jìn)行選擇的。當(dāng)機(jī)床選擇好1個(gè)工序后，從所有設(shè)備的可加工工序集合中刪去該工序?qū)?yīng)的零件的所有工序，從而避免不同設(shè)備同時(shí)選擇同一零件的情況。
圖2零件虛擬工序隊(duì)列概念圖 采用零件虛擬工序隊(duì)列方法有如下特點(diǎn)：
(1)有廣泛的適應(yīng)性。對(duì)機(jī)床故障、緊急零件進(jìn)入、可替代加工工序以及改變調(diào)度目標(biāo)等通常意義上的重調(diào)度情況都很容易處理。
(2)避免了算法中零件在不同的機(jī)床隊(duì)列之間不必要的相互傳送及調(diào)整。
(3)在零件優(yōu)化分批的基礎(chǔ)上，可實(shí)現(xiàn)批內(nèi)各機(jī)床加工負(fù)荷的近似自動(dòng)平衡。機(jī)床最大負(fù)荷不均衡量為零件的最后一道加工工序的加工時(shí)間。
(4)適用于多種零件的混流生產(chǎn)，也適用于傳統(tǒng)的Job－Shop生產(chǎn)。
(5)簡(jiǎn)化了FMS動(dòng)態(tài)調(diào)度控制中的規(guī)則系統(tǒng)，使得調(diào)度控制更易于實(shí)現(xiàn)。
用零件虛擬工序隊(duì)列方法保證了各加工設(shè)備加工負(fù)荷的近似均衡，若結(jié)合合適的調(diào)度規(guī)則在機(jī)床的可調(diào)度零件集合中選擇合適的加工零件，所得到的結(jié)果必為系統(tǒng)的近優(yōu)解甚至最優(yōu)解。 3基于零件虛擬工序隊(duì)列的FMS啟發(fā)式動(dòng)態(tài)調(diào)度算法
該算法是在加工任務(wù)分批的基礎(chǔ)上，同時(shí)考慮了工件運(yùn)輸系統(tǒng)的影響而提出的。機(jī)床前輸入/輸出緩沖站配置不同，其調(diào)度算法略有不同。本文針對(duì)機(jī)床前具有1個(gè)輸入和1個(gè)輸出緩沖器的典型FMS情況進(jìn)行研究，提出動(dòng)態(tài)調(diào)度算法，其流程圖見圖3。
>圖3FMS動(dòng)態(tài)調(diào)度原理圖 在調(diào)度算法中提出了系統(tǒng)決策點(diǎn)的確定方法。通過計(jì)算各機(jī)床上所有工件的加工完成時(shí)刻，確定具有最小加工完成時(shí)間的機(jī)床，把該機(jī)床當(dāng)前加工工件的加工完成時(shí)刻作為決策點(diǎn)。該方法一方面全面考慮了各機(jī)床的加工負(fù)荷情況，另一方面也找出了系統(tǒng)中最迫切需要調(diào)度決策的機(jī)床進(jìn)行決策和運(yùn)輸，從而提高整個(gè)加工和運(yùn)輸系統(tǒng)的利用率，使總加工時(shí)間最短。
設(shè)備在加工過程中情況主要有6種（見圖4）。圖4a和圖4b中，系統(tǒng)中各機(jī)床均有工件加工，且輸入存儲(chǔ)器中皆有待加工工件，選擇t2時(shí)刻最小的機(jī)床（機(jī)床2）的t1時(shí)刻作為決策點(diǎn)tD。
圖4機(jī)床工件選擇的決策點(diǎn)分析示意圖 圖4c和圖4d中，此時(shí)系統(tǒng)中有機(jī)床（機(jī)床1）輸入存儲(chǔ)器中無待加工工件（t2=∞），找出t2最小的機(jī)床（機(jī)床3）的t1作為決策點(diǎn)tD。
圖4e和圖4f中，此時(shí)系統(tǒng)中有機(jī)床（機(jī)床1）當(dāng)前為空閑狀態(tài)，同樣找出t2最小的機(jī)床（機(jī)床2）的t1作為決策點(diǎn)tD。
除上面幾種情況外，還有1種特殊情況，即各機(jī)床輸入存儲(chǔ)器中都為空、各機(jī)床或空閑、或只有1個(gè)工件。此時(shí)把新工件進(jìn)入系統(tǒng)時(shí)刻或系統(tǒng)中工件的工序加工完成時(shí)刻作為系統(tǒng)的決策點(diǎn)。
在算法中提出的動(dòng)態(tài)預(yù)調(diào)度方法，能在系統(tǒng)決策點(diǎn)處預(yù)先決策好機(jī)床待加工的零件，并通知零件運(yùn)輸系統(tǒng)送入機(jī)床的輸入緩沖站中，這樣當(dāng)機(jī)床加工好零件后可直接通過托盤交換裝置把機(jī)床上的零件送入輸出緩沖站，并把輸入緩沖站中的零件送入機(jī)床。零件的動(dòng)態(tài)預(yù)調(diào)度能顯著地減少機(jī)床的等待時(shí)間，提高機(jī)床的生產(chǎn)率。
為了實(shí)現(xiàn)調(diào)度目標(biāo)，提出調(diào)度規(guī)則的動(dòng)態(tài)選擇方法，即根據(jù)系統(tǒng)的主調(diào)度目標(biāo)，確定系統(tǒng)的主調(diào)度規(guī)則。在系統(tǒng)中未出現(xiàn)特殊情況時(shí)，用主調(diào)度規(guī)則實(shí)現(xiàn)對(duì)系統(tǒng)的調(diào)度；若出現(xiàn)特殊情況，則根據(jù)系統(tǒng)的輔助調(diào)度目標(biāo)和特殊狀況的類型確定輔助調(diào)度規(guī)則。主調(diào)度規(guī)則和輔助調(diào)度規(guī)則在系統(tǒng)中的動(dòng)態(tài)選擇，使系統(tǒng)可達(dá)到較好的主調(diào)度目標(biāo)和輔助調(diào)度目標(biāo)。本文通過采用最小松弛時(shí)間和零件優(yōu)先級(jí)規(guī)則可使MT最小，從而保證零件的交貨期。 4實(shí)例仿真
根據(jù)上面提出的零件虛擬工序隊(duì)列的概念及動(dòng)態(tài)調(diào)度算法，以直線型雙排布局的FMS為例，在我們所研制的FMS動(dòng)態(tài)調(diào)度仿真系統(tǒng)上對(duì)1個(gè)典型的加工任務(wù)進(jìn)行仿真試驗(yàn)。該FMS由5臺(tái)加工中心、1臺(tái)AGV（正常運(yùn)行速度為0.2 m/s）、1個(gè)裝卸站、8個(gè)緩沖站和8個(gè)可用托盤組成。零件的某一子批加工計(jì)劃（指經(jīng)靜態(tài)分批后生成的子加工計(jì)劃）見表1，零件的加工工藝見表2，在沒有對(duì)動(dòng)態(tài)調(diào)度仿真系統(tǒng)進(jìn)行人工干預(yù)的情況下經(jīng)過14.293 32 min的仿真試驗(yàn)得出仿真結(jié)果。系統(tǒng)總加工時(shí)間為23.822 2 h，總生產(chǎn)率為2.395 5件/h,所用托盤數(shù)為6個(gè)。表3給出了機(jī)床和運(yùn)輸小車的仿真性能結(jié)果。因考慮了零件的可替代加工工序，且是在零件靜態(tài)分批的基礎(chǔ)上進(jìn)行的，所以無法提供可供比較的例子。 表1零件的子批加工計(jì)劃 零件編號(hào)批量交貨期（天）零件優(yōu)先級(jí)對(duì)應(yīng)托盤數(shù) A1 20 3 1 1 A2 12 2 1 2 A3 25 3 2 1 A4 24 2 2 1 A5 24 3 1 1 表2零件加工工藝及可替代加工工序 零件
編號(hào)工序加工時(shí)間(min) 機(jī)床1 機(jī)床2 機(jī)床3 機(jī)床4 機(jī)床5 A1 1 20 — 25 — — 2 — 25 — 25 23 3 10 12 — — — A2
1 60 — 65 70 — 2 — 25 20 — 20 A3 1 — — 40 — 50 2 40 40 — 35 — 3 — 35 40 — 40 A4
1 — 20 20 — — 2 — 30 — 25 25 A5 1 30 — 20 — — 2 — 25 — 25 25 3 15 12 15 — — 4 — 45 — — 25 表3對(duì)該子批零件的調(diào)度結(jié)果 機(jī)床
編號(hào)利用率
(%) 通過工
件數(shù)加工時(shí)間
（h）生產(chǎn)率
（件/h） MC1 78.777 38 17.5002 1.5951 MC2 89.13 26 20.3661 1.0914 MC3 86.262 24 19.7496 1.0075 MC4 52.333 24 11.6668 1.0075 MC5 78.987 25 17.9834 1.0494 AGV1 40.392 - - -
通過對(duì)調(diào)度結(jié)果的分析可知，本文提出的基于零件虛擬工序隊(duì)列的動(dòng)態(tài)調(diào)度算法是切實(shí)可行的。
*國(guó)家科學(xué)技術(shù)部重大攻關(guān)計(jì)劃資助項(xiàng)目和國(guó)家863高技術(shù)發(fā)展計(jì)劃資助項(xiàng)目(863—511—9608—004)
作者簡(jiǎn)介：趙天奇男，1965年生。清華大學(xué)（北京市100084）自動(dòng)化系博士后研究人員、工學(xué)博士。研究方向?yàn)槊艚葜圃臁⒉⑿泄こ�、ERP、企業(yè)過程管理與優(yōu)化。發(fā)表論文20余篇。
作者單位：陳禹六北京市100084清華大學(xué)
李培根武漢市430074華中理工大學(xué)
1.鄧子瓊.FMS建模及仿真.北京:國(guó)防工業(yè)出版社,1993:58～96
2.趙天奇,李培根，段正澄.華中理工大學(xué)學(xué)報(bào)，1998,26(2):12～14
3.Andrew Kusiak. Intelligent Manufacturing Systems.New York:Prentice Hall, Inc., 1990:125～143
4.Chung Dae Young, Chank Wan Park.Computers Ind. Engin.，1996,31(3):557～568
【基于零件虛擬工序隊(duì)列的FMS動(dòng)態(tài)調(diào)度研究】相關(guān)文章：
面向FMS生產(chǎn)調(diào)度和控制的零件動(dòng)態(tài)工藝模型研究08-06
基于虛擬儀器的圓盤式電流變傳動(dòng)機(jī)構(gòu)的動(dòng)態(tài)分析08-06
基于虛擬現(xiàn)實(shí)技術(shù)的自行車漫游系統(tǒng)的研究與實(shí)現(xiàn)08-06
云環(huán)境下基于蟻群算法的動(dòng)態(tài)容錯(cuò)技術(shù)研究08-19
基于MapX的GIS動(dòng)態(tài)操作與實(shí)現(xiàn)08-06
基于虛擬扇區(qū)的Flash存儲(chǔ)管理技術(shù)08-06
基于先驗(yàn)預(yù)知的動(dòng)態(tài)電源管理技術(shù)08-06