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

1、基于零件虛擬工序隊(duì)列的FMS動(dòng)態(tài)調(diào)度研究    摘要提出虛擬工序隊(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ī)則中國圖書資料分類法分類號(hào)TH165TP271 DynamicSchedulingBasedonVirtualOperationQueueofPartforFMSs ZhaoT

2、ianqi(TsinghuaUniversity,Beijing,China)ChenYuliuLiPeigenp1367-1369 對(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ì)列的概念，并

3、在此基礎(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í)間。用以下

4、2個(gè)指標(biāo)來描述：工件平均延誤時(shí)間（meantardiness，MT）和工件平均流通時(shí)間（meanflow-time，MFT）。MT反映零件是否滿足交貨期，MFT則反映工件在系統(tǒng)中的駐留時(shí)間，能較全面地反映系統(tǒng)生產(chǎn)時(shí)間。調(diào)度目標(biāo) f=minW1×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)的

5、調(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è)加工

6、零件是在該機(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)的

7、JobShop生產(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ì)算

8、各機(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作為

9、決策點(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)

10、度規(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.2m/s）、1個(gè)裝

11、卸站、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.29332min的仿真試驗(yàn)得出仿真結(jié)果。系統(tǒng)總加工時(shí)間為23.8222h，總生產(chǎn)率為2.3955件/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ù)A120311A212212A325321A424221A524311表2零件加工工藝及可替代加工工

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