基于刀具壽命約束的FMS刀具流死鎖研究

舒海生 趙 剛 趙 丹

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

基于刀具壽命約束的FMS刀具流死鎖研究

舒海生 趙 剛 趙 丹

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

刀具流死鎖問題是柔性制造系統(tǒng)（FMS）調(diào)度中的重要核心內(nèi)容，為實現(xiàn)合理的死鎖回避，必須深入分析刀具流死鎖的相關(guān)性質(zhì)。在前期研究的基礎(chǔ)上，分析了刀具壽命對刀具申請的影響，進一步建立了基于刀具壽命約束的刀具申請分配圖，分析了死鎖的相關(guān)性質(zhì)，建立了在考慮刀具壽命的情況下的刀具流死鎖判定定理，為下一步的深入分析死鎖檢測算法和死鎖回避準備了基礎(chǔ)。

FMS 刀具流 死鎖 刀具壽命

FMS包括兩個相互依存的工作流：工件流和刀具流。在過去的20年里，在眾多學(xué)者的共同努力下，工件流的研究已經(jīng)取得了長足的發(fā)展［1－5］。近年來，刀具流的研究開始受到學(xué)界的重視，不少學(xué)者針對刀具流中的刀具管理體系以及仿真調(diào)度做了大量的工作［6－9］，提出了很多實用的新技術(shù)和新方法。相對而言，刀具流死鎖問題的研究工作尚處于起步階段，相關(guān)文獻還不多。

刀具流的研究主要是死鎖分析和刀具分派兩個方面，它們一直是刀具流控制中的基本問題和難點問題。參考文獻［10－11］分別采用了Petri網(wǎng)和圖論工具定義了刀具流死鎖的概念，并給出了相應(yīng)的死鎖檢測算法，但他們并沒有給出如何進行死鎖控制以及如何實現(xiàn)刀具的實時分派，同時也沒有考慮刀具壽命對刀具流的影響。文獻［12］中，通過定義一類刀具申請分配圖（TAAG），針對基于工序備刀的生產(chǎn)情況下刀具流死鎖問題做了一些初步研究，取得了一些結(jié)論，但是這些工作仍然沒有考慮刀具壽命的影響，而是規(guī)定每把刀具的壽命都是足夠的。顯然，這與實際情況不相符合。為此，本文對考慮刀具壽命的刀具流死鎖做了進一步的分析。

1 刀具壽命對TAAG的影響

刀具流死鎖表現(xiàn)為系統(tǒng)中的若干臺機床之間互相等待對方釋放相關(guān)刀具。這種循環(huán)等刀現(xiàn)象是在相關(guān)刀具資源不足情況下由不恰當?shù)臋C床選擇工件策略和刀具分派策略所引發(fā)的。

以矩形表示機床刀具庫，以有向線段表示機床之間的刀具申請（稱作刀具申請線），在各矩形之間加入系統(tǒng)中所有刀具申請線，從而形成一個有向圖，該圖稱作刀具申請分配圖［12］。從圖論觀點看，刀具流死鎖與TAAG死鎖圖二者是等價的，因此我們可以把對刀具流死鎖問題的研究轉(zhuǎn)換到圖論域中對TAAG的研究。

在考慮刀具壽命之后，TAAG中原有的刀具申請線（包括單一線，復(fù)選線和爭用線）將受到一定影響，從而表現(xiàn)出一些新的特征。這種特征的出現(xiàn)主要發(fā)生在當某把被申請刀具的剩余壽命不足以提供給申請者，但多把相同刀具的剩余壽命之和卻能夠滿足申請者的需求時。此時申請者可以發(fā)出一類新的申請線，要求多把被申請刀具全都分配給申請者。下面首先給出這類新的申請線的定義。

定義1 對于單起點多終點的刀具申請線，如果只有所有終點處機床刀庫中指定的刀具都被分派給起點機床刀庫，該刀具申請才能得到滿足，則稱此類刀具申請線為全選線。

圖1給出了刀具申請分配圖（TAAG）的示例，圖中L1為單一線，L2為復(fù)選線，L3為爭用線，這些申請線終點所指向的機床刀庫中相關(guān)刀具的壽命都是滿足需要的。而M1機床刀庫向M4和M5發(fā)出的申請線L4則是一條全選線，由于M4和M5中被申請的刀具各自的剩余壽命都不足以滿足M1的需求，所以只有M4和M5中被申請的相關(guān)刀具全都分配給M1時這個刀具申請才徹底滿足（此處已假設(shè)這2把刀的剩余壽命之和能夠滿足需要）。

對于單一線，在被申請刀具壽命足夠滿足申請者時，該單一線仍然保持不變；而若被申請刀具壽命不足時，此單一線將不存在。

對于復(fù)選線，當被申請的多把刀具的剩余壽命均足夠時，該復(fù)選線保持不變；而若其中某些刀具剩余壽命不足時，則可能出現(xiàn)以下4種情況：

（1）原復(fù)選線轉(zhuǎn)化為單一線

原復(fù)選線如圖 2所示，M2向 M1，M4，M5，M6發(fā)出一條復(fù)選線申請某種刀具。當M1，M5，M6中的相關(guān)刀具剩余壽命不足且三者之和都不能滿足所需壽命時，將轉(zhuǎn)化為如圖3所示的單一線（M2指向M4）。

（2）原復(fù)選線轉(zhuǎn)化為新復(fù)選線

若只有M1中的刀具剩余壽命不足，而M4，M5，M6中的刀具壽命都足夠時，原復(fù)選線將轉(zhuǎn)化為如圖4所示的新的復(fù)選線。

（3）原復(fù)選線轉(zhuǎn)化為全選線

若M1，M4，M5，M6中的刀具壽命都不能滿足需求且只有所有這些刀具剩余壽命之和才能滿足需要時，原復(fù)選線將轉(zhuǎn)化為如圖5所示的全選線。

（4）原復(fù)選線轉(zhuǎn)化為“復(fù)選+全選”線

當某些刀具剩余壽命足夠，另一部分刀具不能單獨提供所需壽命，但必須組合起來才能提供足夠壽命時，如圖6所示，M6中的被申請刀具壽命足夠，而M1，M4，M5中的刀具壽命不夠，但是M1與M4或者M4與M5一起卻可以提供足夠的刀具壽命，此時，原復(fù)選線將轉(zhuǎn)化為圖中所示的“復(fù)選+全選”線。

對于爭用線，在考慮刀具壽命時，可以類似地得到轉(zhuǎn)化后的TAAG。限于篇幅，此處僅列出三種主要的情況：

（1）原爭用線轉(zhuǎn)化為新爭用線

圖7表示1條爭用線，當M3中的被申請刀具壽命都不足以提供給M4和M5時，原爭用線將轉(zhuǎn)化為如圖8所示的新爭用線。

（2）原爭用線轉(zhuǎn)化為“爭用+全選”線

當M1，M2，M3中的被申請刀具壽命均不足，但三者剩余壽命之和能夠滿足申請時，原爭用線將轉(zhuǎn)化為如圖9所示的“爭用+全選”線。

（3）原爭用線轉(zhuǎn)化為“爭用+全選+復(fù)選”線

當M1中被申請刀具壽命足夠，而M2和M3中的相關(guān)刀具壽命不足（二者剩余壽命之和能夠滿足需求）時，原爭用線將轉(zhuǎn)化為如圖10所示的“爭用+全選+復(fù)選”線。

綜上所述可以看出，引入全選線之后，刀具申請分配圖（TAAG）仍然可以較好地描述考慮刀具壽命因素的FMS刀具流資源狀況。

2 死鎖塊與死鎖圖的引入

定義 在TAAG中，如果存在一個節(jié)點集A，A中任意元素均有出線申請，且至少有一個出線申請落在A中，則A稱為死鎖塊，該TAAG稱作死鎖圖。其中，出線申請落于A中是指：對于單一線、復(fù)選線和爭用線，要求其所有終點均落于A中；對于全選線，要求其至少有一個分支的終點落于A中。

圖11給出了一個死鎖圖的示例，圖中的｛M1，M2，M3，M5，M6｝構(gòu)成了一個死鎖塊，塊中每一元素都有出線申請，出線申請中的單一線、復(fù)選線和爭用線的所有終點都落于塊中，而全選線L4的一個分支終點也落于該集合中。

由死鎖塊和死鎖圖的定義可以看出，考慮刀具壽命之后，在分析TAAG的死鎖性時，圖中新增的與全選線有關(guān)的申請線也可以采用等效的方法加以處理。對于全選線，可以用多條單一線來等效。圖12a所示為一條全選線，等效后的單一線如圖12b。對圖9所示的“爭用+全選”線，等效后如圖13。

對于“爭用+全選+復(fù)選”線，如圖10所示。這一類較為復(fù)雜，可以對其中的復(fù)選線加以拆分，分解為一條全選線和一條單一線，然后將全選線分解為兩條單一線即可，等效后如圖14所示，圖14a是保留全選線后的等效圖，圖14b為保留單一線后的等效圖。

3 刀具流死鎖判定定理及證明

定理

刀具流發(fā)生死鎖的充分必要條件是對應(yīng)的TAAG是死鎖圖。

證明

充分性：設(shè)刀具流發(fā)生死鎖，則根據(jù)死鎖概念及現(xiàn)象，必定存在一個刀具庫集合B，B中刀具庫形成循環(huán)等刀，也即B中任意一個刀具庫都會發(fā)出刀具申請，而且被申請刀具恰好位于B中其他刀具庫的T域（T域是指機床刀具庫中被下道工序所預(yù)先占有的刀具集合［12］）中，由此反映到對應(yīng)的 TAAG中，B就形成了A，A中元素都有出線申請，并都落在A中其他節(jié)點上，A為死鎖塊，對應(yīng)TAAG為死鎖圖；

必要性：反證法。假定刀具流不死鎖，于是必定存在某種刀具分配方案，使得各機床都能得到所申請的刀具，而不用互相循環(huán)等刀。由于TAAG為死鎖圖，那么其中至少包含一個死鎖塊A，A中任意元素都有出線申請。不妨設(shè)A中各集合元素分別代表刀具庫M1，M2，…，Mi，…，Mn。以 M1 為起點，設(shè)其出線申請中有1條指向M2（對于單一線，要求終點指向M2；對于復(fù)選線，要求所有終點落于A中的同時，有某分支指向M2；對于爭用線，要求所有終點都落于A中，同時有某分支指向M2；對于全選線，要求其至少有一個終點落于A中），M2的落于A中的出線申請分支中可能避免死鎖的顯然不能選擇指向M1，這是因為，對于單一線，如果指向M1，按死鎖概念會產(chǎn)生M1和M2之間循環(huán)等刀而死鎖，與假設(shè)矛盾；而對于復(fù)選項和爭用線，也不能選擇其終點指向M1的分支，否則仍然因循環(huán)等刀而死鎖；而對于全選線，其任何一個分支如果指向M1，M1和M2都將陷入互相等刀而死鎖。因此，M2的出線申請分支中可能避免死鎖的只能指向集合｛M3，…，Mi，…，Mn｝；不妨假設(shè) M2 的出線指向 M3，類似地，M3的出線既不能選擇指向M1，也不能選擇M2。如果選擇M2，將會導(dǎo)致M2和M3彼此死鎖，其原因與上相同；而如果選擇指向M1，就會導(dǎo)致M1、M2和M3三者構(gòu)成環(huán)形死鎖，因而對于這條M3所發(fā)出的落于A中的申請線，能回避死鎖的出線分支只能指向集合｛M4，…，Mi，…，Mn｝；依此類推，Mn －1 節(jié)點只能指向集合｛Mn｝，也即Mn－1勢必指向Mn；由于Mn也在A中，因此也應(yīng)有出線指向集合｛M1，M2，…，Mi，…，Mn－1｝，而無論選擇指向集合中哪一元素，均會產(chǎn)生刀具循環(huán)等待環(huán)路，刀具流死鎖，由此可知無論如何選擇可能的出線申請分支，死鎖一定發(fā)生，這與假設(shè)矛盾，必要性成立。

上述死鎖判定定理把考慮刀具壽命之后的刀具流死鎖和死鎖圖聯(lián)系了起來，利用死鎖圖來判定系統(tǒng)中是否存在刀具流的死鎖，揭示了刀具流死鎖問題的內(nèi)在本質(zhì)，進一步為考慮刀具壽命影響的刀具流死鎖檢測與回避奠定了技術(shù)分析基礎(chǔ)。

4 結(jié)語

死鎖問題是刀具流研究的核心內(nèi)容和主要難點，本文在前期研究工作的基礎(chǔ)上，將刀具壽命考慮進來，對該問題作了進一步的分析。通過引入全選線、死鎖塊和死鎖圖，使得TAAG能夠進一步描述考慮刀具壽命的刀具申請分配狀態(tài)，從而拓展了TAAG的適用范圍，并在此基礎(chǔ)上建立了刀具流死鎖判定定理，使得刀具流研究更加符合客觀實際，為后續(xù)的刀具流死鎖回避研究做好了準備。

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

［2］王志亮，汪惠芬，張友良.動態(tài)Job－Shop調(diào)度問題的一種自適應(yīng)遺傳算法［J］.中國機械工程，2004（11）：995 －999.

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

［4］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.

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

［6］歐陽普仁.FMS刀具管理系統(tǒng)體系結(jié)構(gòu)研究［J］.南京理工大學(xué)學(xué)報，1996，20（3）：273 －276.

［7］王解法，馮祖仁，李世敬，等.柔性制造系統(tǒng)（FMS）刀具建模、調(diào)度仿真研究［J］.系統(tǒng)仿真學(xué)報，2003（9）：1211 －1213.

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

［9］P.H.KOO，J.M.A.TANCHOCO，and J.J.TALAVAGE.Tool requirements in manufacturing systems under dynamic tool sharing［C］.In Proc.20thInt.Conf.Comput.Industr.Eng，1996：1271 －1274.

［10］畢諸明，姜浩，朱巖，等.FMS運控軟件調(diào)試環(huán)境中的刀具流死鎖的檢測［J］.組合機床與自動化加工技術(shù)，1996（1）：19 －22.

［11］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.

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

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

Research on the Deadlock of Tool Flow in FMS Based on Tool Life Constraint

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

The problem of tool flow deadlock is very important in flexible manufacturing system（FMS）scheduling.In order to realize reasonable deadlock avoidance，the attributes of tool flow deadlock should be analyzed deeply.On the basis of previous research，the influence of tool life on tool request was analyzed and tools applying allocation graph established based on tool life constraint.The related character of tool flow deadlock was analyzed and the theory of deadlock criterion of tool flow was set up with consideration of tool life which lay a foundation for the further research of deadlock detecting algorithm and deadlock avoidance.

FMS；Tool Flow；Deadlock；Tool Life

book=51,ebook=335

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

（編輯 蔡云生） （

2009－10－16）

10717