FMS混合調(diào)度中的兩種啟發(fā)式規(guī)則*

舒海生 趙 剛 趙 丹

（哈爾濱工程大學(xué)，黑龍江哈爾濱 150001）

FMS混合調(diào)度中的兩種啟發(fā)式規(guī)則*

舒海生 趙 剛 趙 丹

（哈爾濱工程大學(xué)，黑龍江哈爾濱 150001）

針對FMS混合調(diào)度系統(tǒng)中的工件選擇和運(yùn)刀小車的啟發(fā)式調(diào)度問題，給出了兩個(gè)新的啟發(fā)式規(guī)則，即在機(jī)床選工件策略中建立了刀具外借量最少規(guī)則，在運(yùn)刀小車任務(wù)調(diào)度策略中提出了目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則，通過仿真實(shí)驗(yàn)驗(yàn)證了兩種啟發(fā)式規(guī)則的有效性。結(jié)果表明所提出的兩種調(diào)度規(guī)則能夠較好地改善FMS的各項(xiàng)性能指標(biāo)。

FMS 刀具流 調(diào)度策略

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

1 FMS混合調(diào)度原理

本文在基于虛擬工序隊(duì)列技術(shù)的工件流調(diào)度方法［2］的基礎(chǔ)上，進(jìn)一步將刀具流考慮進(jìn)來，建立了FMS混合調(diào)度模型（圖1）。

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

由動態(tài)調(diào)度模型可以看出，工件選擇模塊是工件流進(jìn)程和刀具流進(jìn)程的接口，主要用于為機(jī)床選擇合適的下道工序。當(dāng)系統(tǒng)決策點(diǎn)到來時(shí)，可決策機(jī)床在各自的虛擬工序隊(duì)列中決策選取下道工序，根據(jù)所選工序的刀具需求生成相應(yīng)的刀具申請表，然后進(jìn)行死鎖判定，從中選擇不會導(dǎo)致死鎖的下道工序，最后生成相應(yīng)的刀具申請表。

死鎖判定的相關(guān)算法和原理已在另文［11］中詳細(xì)闡述。此處主要針對工件流中的機(jī)床選工件策略和刀具流中的運(yùn)刀小車服務(wù)策略進(jìn)行重點(diǎn)分析。

2 機(jī)床選擇工件策略

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

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

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

于是該規(guī)則即可描述為

由定義不難發(fā)現(xiàn)，該規(guī)則優(yōu)先選擇向其它機(jī)床申請刀具數(shù)量最少的工序作為本機(jī)床的下一道待加工工序，這就使得任意時(shí)刻系統(tǒng)中的刀具申請數(shù)量得到盡可能的控制，從而能夠顯著地減少刀具交換次數(shù)，改善系統(tǒng)性能。

3 運(yùn)刀小車的服務(wù)策略

運(yùn)刀小車的服務(wù)策略問題是指當(dāng)FMS中多臺機(jī)床提出刀具運(yùn)送申請時(shí)，從資源爭用的角度出發(fā)，哪臺機(jī)床應(yīng)該最先得到服務(wù)；從作業(yè)選擇角度出發(fā)，小車應(yīng)首先選擇哪臺機(jī)床為服務(wù)對象，也即小車響應(yīng)策略問題。運(yùn)刀小車的服務(wù)策略一般有先進(jìn)先出策略，按權(quán)優(yōu)先策略，“瓶頸”優(yōu)先策略，時(shí)間最短策略，數(shù)量最少策略，時(shí)間最長策略，數(shù)量最多策略，就近服務(wù)策略等等。

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

從工件流和刀具流相互作用關(guān)系出發(fā)，運(yùn)刀小車應(yīng)該首先滿足最迫切需要相關(guān)刀具的任務(wù)，這樣才能使得機(jī)床盡早進(jìn)入加工狀態(tài)。為此，本文給出一種新的服務(wù)策略——目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則，即運(yùn)刀小車優(yōu)先運(yùn)送任務(wù)隊(duì)列中目的地機(jī)床的t1最小的任務(wù)。

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

Min（t1（i）），（i=0，1，2，…，k）該策略在運(yùn)送機(jī)床加工所需刀具時(shí)考慮了對工件流效率的影響，使得系統(tǒng)中最迫切需要相關(guān)刀具的機(jī)床能迅速得到運(yùn)刀小車的服務(wù)，減少了機(jī)床等待刀具的時(shí)間，提高了系統(tǒng)的生產(chǎn)效率。

4 實(shí)驗(yàn)與分析

為檢驗(yàn)這兩種新的調(diào)度規(guī)則對系統(tǒng)性能的影響，下面給出了兩個(gè)仿真對比實(shí)驗(yàn)，比較了傳統(tǒng)的調(diào)度規(guī)則與本文提出的兩種啟發(fā)式規(guī)則的優(yōu)劣。

實(shí)驗(yàn)1：考察了運(yùn)刀小車任務(wù)選擇策略的影響，主要比較了隨機(jī)選擇策略和目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則。

采用隨機(jī)選擇策略，在不配備中央刀庫的情況下對生產(chǎn)計(jì)劃如表1所示的64個(gè)工件進(jìn)行了綜合調(diào)度仿真，結(jié)果如表2所示。

然后采用目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則進(jìn)行仿真，結(jié)果如表3所示。

由表2可計(jì)算出各機(jī)床總等刀時(shí)間值為503 min，平均等刀時(shí)間值為125.75 min，由表3則可計(jì)算出各機(jī)床總等刀時(shí)間值為352 min，平均等刀時(shí)間值為88 min。實(shí)驗(yàn)結(jié)果表明，采用目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則后系統(tǒng)中機(jī)床的平均等刀時(shí)間由125.75 min減少到88 min，減小幅度達(dá)到30.01%。正是因?yàn)榈鹊稌r(shí)間得到大幅降低，所以后者的系統(tǒng)總生產(chǎn)率 有了較大提高，由2 202件/h提高到2 265件/h，增加了2.25%。說明本文提出的新規(guī)則是十分有效的。由仿真結(jié)果還可發(fā)現(xiàn)，運(yùn)刀小車選任務(wù)策略對換刀次數(shù)影響很小。

表1 生產(chǎn)計(jì)劃

表2 隨機(jī)規(guī)則仿真結(jié)果

實(shí)驗(yàn)2：考察了機(jī)床選擇工件策略的影響，主要比較了隨機(jī)選擇策略和刀具外借量最小策略對系統(tǒng)性能的影響。

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

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

表3 目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則仿真結(jié)果

表4 刀具外借量最小規(guī)則仿真結(jié)果

5 結(jié)語

FMS混合調(diào)度中工件流和刀具流是相互聯(lián)系、相互作用的，機(jī)床選擇工件策略的確定必須充分考慮所選工件對刀具流的影響，運(yùn)刀小車選擇任務(wù)策略的確定也必須考慮到要盡可能減少工件流的等刀時(shí)間，只有這樣才能獲得較好的綜合效益。本文提出的兩種啟發(fā)式調(diào)度規(guī)則能夠有效地改善系統(tǒng)運(yùn)行性能，提高系統(tǒng)生產(chǎn)率。仿真結(jié)果表明：

（1）運(yùn)刀小車選擇任務(wù)策略對系統(tǒng)等刀時(shí)間和系統(tǒng)生產(chǎn)率有很大影響，目標(biāo)機(jī)床當(dāng)前工序完成時(shí)間最早規(guī)則可以有效地減少系統(tǒng)等刀時(shí)間，同時(shí)提高了系統(tǒng)生產(chǎn)率；

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

［1］周炳海，蔡建國.基于定向搜索的FMS調(diào)度優(yōu)化算法［J］.組合機(jī)床與自動化加工技術(shù)，2001（10）：1 －4.

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

［3］徐剛，吳智銘.一種運(yùn)用圖論進(jìn)行FMS無死鎖調(diào)度的方法［J］.機(jī)械科學(xué)與技術(shù)，2004（4）：412 －415.

［4］王志亮，汪惠芬，張友良.動態(tài)Job－Shop調(diào)度問題的一種自適應(yīng)遺傳算法［J］.中國機(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中刀具優(yōu)化管理的數(shù)學(xué)建模與分析［J］.昆明理工大學(xué)學(xué)報(bào)，2002（4）：38 －41.

［9］歐陽普仁.FMS刀具管理系統(tǒng)體系結(jié)構(gòu)研究［J］.南京理工大學(xué)學(xué)報(bào)，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］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2006（10）：1681 －1688.

如果您想發(fā)表對本文的看法，請將文章編號填入讀者意見調(diào)查表中的相應(yīng)位置。

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

* 黑龍江省自然科學(xué)基金（E0312）資助項(xiàng)目

舒海生，男，1976年生，副教授，博士，主要從事生產(chǎn)計(jì)劃與調(diào)度和智能制造系統(tǒng)等方面的研究工作，已發(fā)表論文10篇。

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

10713