基于刀具寿命约束的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