FMS混合調度中的兩種啟發式規則*

舒海生 趙 剛 趙 丹

（哈爾濱工程大學，黑龍江哈爾濱 150001）

FMS混合調度中的兩種啟發式規則*

舒海生 趙 剛 趙 丹

（哈爾濱工程大學，黑龍江哈爾濱 150001）

針對FMS混合調度系統中的工件選擇和運刀小車的啟發式調度問題，給出了兩個新的啟發式規則，即在機床選工件策略中建立了刀具外借量最少規則，在運刀小車任務調度策略中提出了目標機床當前工序完成時間最早規則，通過仿真實驗驗證了兩種啟發式規則的有效性。結果表明所提出的兩種調度規則能夠較好地改善FMS的各項性能指標。

FMS 刀具流 調度策略

傳統的FMS動態調度研究［1－7］大多集中于工件流調度，較少考慮刀具流對工件流的影響，少量關于刀具方面的研究［8－10］也大都集中在管理系統的組織架構上以及單一刀具流系統中，現有的一些調度策略和規則在工件流和刀具流的混合調度系統中具有較大的局限性，不利于改善和提高系統綜合性能。本文針對綜合調度系統中的調度策略問題進行了分析，從工件流和刀具流的辯證統一關系出發，提出了兩種新的調度策略：刀具外借量最少規則和目標機床當前工序完成時間最早規則，分別應用于機床選工件和運刀小車選任務的調度過程中。這兩種規則的突出特點在于它們著眼于系統整體性能的提高，充分考慮了工件流和刀具流的相互作用關系，較之傳統的調度規則更為合理，有效地提高了FMS混合調度各項性能指標。

1 FMS混合調度原理

本文在基于虛擬工序隊列技術的工件流調度方法［2］的基礎上，進一步將刀具流考慮進來，建立了FMS混合調度模型（圖1）。

整個調度過程從機床完成當前工序加工時刻1開始，首先判斷機床輸入緩沖區是否存在待加工工件，若存在，則判斷該工件待加工工序所需刀具是否已齊備，若不齊備，則該機床當前為不可決策機床，不能進行下一個待加工工件的選擇，而應等待運刀小車的刀具運送；若刀具已齊備，則工件被搬上機床開始加工。當前時刻即成為系統決策點，可以進行機床選工件決策，利用刀具流死鎖檢測算法選擇確保刀具流不發生死鎖的工件，并根據刀具分派算法計算出當前系統中合理的刀具分配方案，之后發出工件運送命令啟動工件流和刀具申請啟動刀具流，并驅動小車適時運送。

由動態調度模型可以看出，工件選擇模塊是工件流進程和刀具流進程的接口，主要用于為機床選擇合適的下道工序。當系統決策點到來時，可決策機床在各自的虛擬工序隊列中決策選取下道工序，根據所選工序的刀具需求生成相應的刀具申請表，然后進行死鎖判定，從中選擇不會導致死鎖的下道工序，最后生成相應的刀具申請表。

死鎖判定的相關算法和原理已在另文［11］中詳細闡述。此處主要針對工件流中的機床選工件策略和刀具流中的運刀小車服務策略進行重點分析。

2 機床選擇工件策略

機床選擇工件策略有很多，如處理時間最短策略、處理時間最長LPT策略、剩余工序加工時間最短策略、剩余工序加工時間最長策略、隨機選擇策略和松弛量最小策略等等［4］。這些傳統的調度規則雖然各有其適用場合，但是它們大多沒有考慮刀具流的影響。

在混合調度系統中，由于工件流和刀具流是相互影響和相互制約的，為提高系統效率，減小刀具流負荷，從控制刀具交換次數的角度給出了一種新規則，即刀具外借量最少規則：

設機床刀具庫中現有的刀具集為P，P中已被其他機床預定借用的刀具集為Q，又設Wi為該機床可加工工序集W中的一道工序，WTi代表Wi所用的刀具集，Wi所需外借的刀具數量為wi，引入求集合元素個數的運算符“||”，則有下式成立：

于是該規則即可描述為

由定義不難發現，該規則優先選擇向其它機床申請刀具數量最少的工序作為本機床的下一道待加工工序，這就使得任意時刻系統中的刀具申請數量得到盡可能的控制，從而能夠顯著地減少刀具交換次數，改善系統性能。

3 運刀小車的服務策略

運刀小車的服務策略問題是指當FMS中多臺機床提出刀具運送申請時，從資源爭用的角度出發，哪臺機床應該最先得到服務；從作業選擇角度出發，小車應首先選擇哪臺機床為服務對象，也即小車響應策略問題。運刀小車的服務策略一般有先進先出策略，按權優先策略，“瓶頸”優先策略，時間最短策略，數量最少策略，時間最長策略，數量最多策略，就近服務策略等等。

事實上，決定運刀小車的服務順序是一個很復雜的問題，以上策略均是針對某一方面的問題而設置的，因而在實際應用中有其局限性。應同時考慮幾種情況，并采用仿真的方法進行模擬，才能取得較佳的服務策略。

從工件流和刀具流相互作用關系出發，運刀小車應該首先滿足最迫切需要相關刀具的任務，這樣才能使得機床盡早進入加工狀態。為此，本文給出一種新的服務策略——目標機床當前工序完成時間最早規則，即運刀小車優先運送任務隊列中目的地機床的t1最小的任務。

設運刀小車的任務隊列為Taskqueue［］，其中的任務對象為Taskqueue［i］，（i=0，1，2，…，k）包含了三個屬性，即：起始運送地i－Start，目的運送地i－Destination，刀具編號 i－ToolNo，并設 i－Destination 表示機床編號，t1（i）表示i－Destination機床的當前工序完成加工時刻t1，那么這種服務策略事實上就是選擇任務Taskqueue［i］作為當前任務，使之滿足下式：

Min（t1（i）），（i=0，1，2，…，k）該策略在運送機床加工所需刀具時考慮了對工件流效率的影響，使得系統中最迫切需要相關刀具的機床能迅速得到運刀小車的服務，減少了機床等待刀具的時間，提高了系統的生產效率。

4 實驗與分析

為檢驗這兩種新的調度規則對系統性能的影響，下面給出了兩個仿真對比實驗，比較了傳統的調度規則與本文提出的兩種啟發式規則的優劣。

實驗1：考察了運刀小車任務選擇策略的影響，主要比較了隨機選擇策略和目標機床當前工序完成時間最早規則。

采用隨機選擇策略，在不配備中央刀庫的情況下對生產計劃如表1所示的64個工件進行了綜合調度仿真，結果如表2所示。

然后采用目標機床當前工序完成時間最早規則進行仿真，結果如表3所示。

由表2可計算出各機床總等刀時間值為503 min，平均等刀時間值為125.75 min，由表3則可計算出各機床總等刀時間值為352 min，平均等刀時間值為88 min。實驗結果表明，采用目標機床當前工序完成時間最早規則后系統中機床的平均等刀時間由125.75 min減少到88 min，減小幅度達到30.01%。正是因為等刀時間得到大幅降低，所以后者的系統總生產率 有了較大提高，由2 202件/h提高到2 265件/h，增加了2.25%。說明本文提出的新規則是十分有效的。由仿真結果還可發現，運刀小車選任務策略對換刀次數影響很小。

表1 生產計劃

表2 隨機規則仿真結果

實驗2：考察了機床選擇工件策略的影響，主要比較了隨機選擇策略和刀具外借量最小策略對系統性能的影響。

首先采用隨機選擇策略，在不含中央刀庫的情況下進行仿真，結果與表2相同。其次采用刀具外借量最小規則進行仿真，結果如表4所示。

由表2可計算出各機床總等刀時間值為503 min，平均等刀時間值為125.75 min，由表4可計算出各機床總等刀時間值為484 min，平均等刀時間值為121 min。實驗結果表明，采用刀具外借量最小規則后系統中機床的平均等刀時間有小幅減少，系統生產率也有少量提高。由此可見，機床選工件規則對于等刀時間和系統生產率的影響是較小的。但是通過表2和表4的比較可以發現，采用刀具外借量最小規則后系統總換刀次數有了大幅度的減少，由隨機規則下的225次下降到現在的84次，降幅達66.7%，這說明機床選工件規則對于換刀次數有著重要影響，本文給出的刀具外借量最小規則可以有效地減少換刀次數，從而能在實際生產中降低刀具交換頻率、縮短輔助時間，并能減少因刀具交換頻繁導致設備故障發生的概率。

表3 目標機床當前工序完成時間最早規則仿真結果

表4 刀具外借量最小規則仿真結果

5 結語

FMS混合調度中工件流和刀具流是相互聯系、相互作用的，機床選擇工件策略的確定必須充分考慮所選工件對刀具流的影響，運刀小車選擇任務策略的確定也必須考慮到要盡可能減少工件流的等刀時間，只有這樣才能獲得較好的綜合效益。本文提出的兩種啟發式調度規則能夠有效地改善系統運行性能，提高系統生產率。仿真結果表明：

（1）運刀小車選擇任務策略對系統等刀時間和系統生產率有很大影響，目標機床當前工序完成時間最早規則可以有效地減少系統等刀時間，同時提高了系統生產率；

（2）機床選擇工件策略對于系統等刀時間和系統生產率的影響較小，但是對于系統總換刀次數卻有著重要影響，刀具外借量最小規則可以十分有效地減少總換刀次數。

［1］周炳海，蔡建國.基于定向搜索的FMS調度優化算法［J］.組合機床與自動化加工技術，2001（10）：1 －4.

［2］趙天奇，陳禹六，李培根.基于零件虛擬工序隊列的FMS動態調度研究［J］.中國機械工程，1999，10（12）：1367 －1369.

［3］徐剛，吳智銘.一種運用圖論進行FMS無死鎖調度的方法［J］.機械科學與技術，2004（4）：412 －415.

［4］王志亮，汪惠芬，張友良.動態Job－Shop調度問題的一種自適應遺傳算法［J］.中國機械工程，2004，15（11）：995 －999.

［5］Key K.LEE.Fuzzy rule generation for adaptive scheduling in a dynamic manufacturing environment［J］.Applied Soft Computing，2008（9）：1295－1304.

［6］Ouajdi KORBAA ，Herve CAMUS，and Jean－claude GENTINA .A New Cyclic Scheduling Algorithm for Flexible Manufacturing Systems［J］.International Journal of Flexible Manufacturing Systems，2002（14）：177－191.

［7］Mark A.LAWLEY.Deadlock Avoidance for Production Systems with Flexible Routing［J］.IEEE Transactions on Robotics and Automation，1999，15（3）：497 －508.

［8］蘇加國，鄒福生.FMS中刀具優化管理的數學建模與分析［J］.昆明理工大學學報，2002（4）：38 －41.

［9］歐陽普仁.FMS刀具管理系統體系結構研究［J］.南京理工大學學報，1996，20（3）：273 －276.

［10］Nagi Z.GEBRAEEL，and Mark A.LAWLEY.Deadlock Detection，Prevention，and Avoidance for Automated Tool Sharing Systems［ J］.IEEE Transactions on Robotics and Automation，2001，17（3）：342 －356.

［11］舒海生，李慶芬.FMS中刀具流死鎖檢測新方法的研究［J］.哈爾濱工業大學學報，2006（10）：1681 －1688.

如果您想發表對本文的看法，請將文章編號填入讀者意見調查表中的相應位置。

Two Kinds of Heuristic Rules in Synthesis Scheduling of FMS

SHU Haisheng，ZHAO Gang，ZHAO Dan
（Harbin Engineering University，Harbin 150001，CHN）

Heuristic scheduling is a difficult problem for machine selecting part and tool AGV selecting task in synthesis scheduling system of FMS.Two heuristic scheduling rules named minimal tool borrowing rule and minimal completion time of curent operation of target machines rule are given in this paper.Computer simulation is adopted to testify the validity of these new rules.The output argues that the two rules can enhance the efficiency of FMS.

Flexible Manufacturing System（FMS）；Tool Flow；Scheduling Rule

TP273+.5

A

* 黑龍江省自然科學基金（E0312）資助項目

舒海生，男，1976年生，副教授，博士，主要從事生產計劃與調度和智能制造系統等方面的研究工作，已發表論文10篇。

（編輯 周富榮） （收修改稿日期：2010－02－23）

10713