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

舒海生 趙 剛 趙 丹

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

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

舒海生 趙 剛 趙 丹

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

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

FMS 刀具流 死鎖 刀具壽命

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

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

1 刀具壽命對TAAG的影響

刀具流死鎖表現為系統中的若干臺機床之間互相等待對方釋放相關刀具。這種循環等刀現象是在相關刀具資源不足情況下由不恰當的機床選擇工件策略和刀具分派策略所引發的。

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

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

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

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

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

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

（1）原復選線轉化為單一線

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

（2）原復選線轉化為新復選線

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

（3）原復選線轉化為全選線

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

（4）原復選線轉化為“復選+全選”線

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

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

（1）原爭用線轉化為新爭用線

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

（2）原爭用線轉化為“爭用+全選”線

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

（3）原爭用線轉化為“爭用+全選+復選”線

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

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

2 死鎖塊與死鎖圖的引入

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

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

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

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

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

定理

刀具流發生死鎖的充分必要條件是對應的TAAG是死鎖圖。

證明

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

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

上述死鎖判定定理把考慮刀具壽命之后的刀具流死鎖和死鎖圖聯系了起來，利用死鎖圖來判定系統中是否存在刀具流的死鎖，揭示了刀具流死鎖問題的內在本質，進一步為考慮刀具壽命影響的刀具流死鎖檢測與回避奠定了技術分析基礎。

4 結語

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

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

［2］王志亮，汪惠芬，張友良.動態Job－Shop調度問題的一種自適應遺傳算法［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刀具管理系統體系結構研究［J］.南京理工大學學報，1996，20（3）：273 －276.

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

［8］蘇加國，鄒福生.FMS中刀具優化管理的數學建模與分析［J］.昆明理工大學學報，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運控軟件調試環境中的刀具流死鎖的檢測［J］.組合機床與自動化加工技術，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］.哈爾濱工業大學學報，2006（10）：1681 －1688.

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

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年生，副教授，博士，主要從事生產計劃與調度和智能制造系統等方面的研究工作，已發表論文8篇。

（編輯 蔡云生） （

2009－10－16）

10717