FMS刀具流死锁控制策略与分派算法的研究

    在FMS动态调度系统的研究中，以往大多集中于工件流控制上[1-4]。近些年来，刀具流的研究开始受到学界的重视，不少学者针对刀具管理系统的功能和结构做了大量的工作[5-8]，而刀具流控制问题尤其是死锁控制和刀具分派问题的研究则不多见。

    刀具流控制问题主要包括死锁控制策略和刀具分派算法。它们一直是刀具流控制中的基本问题和难点问题，文献[9，10]分别采用了Petri网和图论工具定义了刀具流死锁的概念，并给出了相应的死锁检测算法，但他们并没有给出如何进行死锁控制以及如何实现刀具的实时分派。在前期工作[11]基础上，本文对考虑刀具流的FMS的动态调度做了进一步的分析，提出了一种解决刀具流调度问题的两级死锁控制策略，建立了动态调度模型，并给出了死锁检测算法和刀具分派算法。

1 刀具流死锁与两级死锁控制策略

    刀具流死锁表现为系统中的若干台机床之间互相等待对方释放相关刀具。这种循环等刀现象是在相关刀具资源不足情况下由不恰当的机床选择工件策略和刀具分派策略所引发的。

    以矩形表示机床刀具库，以有向线段表示机床之间的刀具申请(称作刀具申请线)，在各矩形之间加入系统中所有刀具申请线，从而形成一个有向图，该图称作刀具申请分配图[11](tools applying allocation graph．TAAG)。从图论的观点看，刀具流死锁与TAAG是死锁图二者是等价的，因此我们可以把对刀具流死锁问题的研究转换到图论域中对TAAG的研究。在文献[11]中，笔者曾详细证明了与之相关的定理和推论，为方便起见，此处直接给出。

    定理1刀具流发生死锁的充分必要条件是对应的TAAG是死锁图。

    推论如果系统中所有机床均有出线申请，则该系统刀具流必定死锁。

    定理2如果TAAG中存在无出线节点肘，那么删去指向肘的申请线后形成新的TAAG与原TAAG具有相同的死锁性。

    定理1揭示了刀具流发生死锁的一个重要原因，即系统中各台机床上的待加工工件的刀具占用状况和刀具需求状况之间相互矛盾，从而理论上表现为TAAG构成了死锁图，而实际运行中则表现为刀具流死锁，系统停滞。这种相互矛盾是在待加工工件选择时产生的。定理3表明在保证初始TAAG不形成死锁图的前提下，要想使得各个刀具申请都能顺利地满足并且不再导致后续TAAG形成死锁，必须按照一定的规则进行(即定理中的第3条)。这恰好指出了刀具流发生死锁的另一个成因，即刀具分派过程如果不合理，也会导致死锁的发生。

    总之，刀具流死锁的两大根源就在于工件选择不合理和刀具分派不合理。

    为此，本文给出一种两级死锁控制策略，并建立了动态调度模型如图1所示。整个调度过程从机床空闲或者完成当前工序加工的时刻t1开始，首先叛断机床输入缓冲区是否存在待加工工件，若存在，则判断该工件待加工工序所需刀具是否已齐备，若不齐备，则该机床当前为不可决策机床，不能进行下一待加工工件的选择，而应等待运刀小车的刀具运送；若齐备，则工件被搬上机床开始加工，当前时刻即成为系统决策点，此时机床可以在其所属的虚拟工序队列中选择工件作为下一待加工工件。随后就进入了两级死锁控制流程。

    两级控制的第1级是工件选择模块，也即图1中的“按无死锁要求选择活性工件”。在这个模块中，按照定理1分析各待加工工件所构成的TAAG，从中选择出相应的TAAG不是死锁图的从而可以确保刀具流在本级不会发生死锁的工件集。至此，第1级任务完成。然后进入第2级即刀具分派模块(图1中的“按无死锁要求决策活性刀具分派方案”)，在这一级中，应根据合理的刀具分派算法计算出当前系统中合理的刀具分派方案，该方案应使各工件的刀具需求都能满足，并且在分派过程中每一步产生的TAAG都不会形成死锁图。分页

图1 刀具流动态调度模型

    经过两级的监督和控制，刀具流死锁的两大根源均得以回避。从而实现了刀具流死锁控制。

2 死锁检测算法

    在第1级控制中，当机床从其所属的虚拟工序队列中选择工件时，以往大多是按某种优先权规则来对可选工件进行排序，并选择队头工件作为待加工工件。在考虑刀具流控制后，应对这些工件进行死锁检测，只有通过检测的工件才能被选中。根据推论和定理2可建立死锁检测算法如下：

    (1)决策点到达，建立TAAG，并设机床节点数为N；

    (2)计算有出线申请的机床台数n；

    (3)若n=N，则转至(6)；

    (4)若n=1或O，则转至(7)；

    (5)若1<n<N，则从原TAAG中删去(N-n)个无出线的机床节点，同时删去所有指向被删节点的申请线，建立新的TAAG，N=n，转到(2)；

    (6)死锁，结束；

    (7)无死锁，结束。

3 刀具分派算法

    经过第1级的控制，当前系统的TAAG图一定是非死锁图。定理3指出针对这个非死锁的TAAG一定存在着可行的刀具分派方案使得各机床的下道工序都能顺利地得到加工，并且不会导致刀具流死锁。但是第1级控制并没有给出确切的分派方案来指导刀具流，还必须经过刀具分派模块的计算才能寻找出这些可行的方案，这正是第2级死锁控制的任务。

    可行的刀具分派方案可以用刀具分派计划表(tool allocation plan，TAP)来描述，TAP中存储了可行的刀具分派进程，它应该保证进程中每一次刀具分派形成新的TAAG都应该是非死锁图。分页

    结合银行家算法原理[12]和定理3。下面给出了一种刀具分派算法：

    为更好地理解上述过程，以下给出了该算法示例。如图2所示，图2中肘。一眠分别是系统中的6台机床。

    图2(a)是给定的一个非死锁的TAAG，图中有2条单一线，1条复选线和1条争用线：

    M6-(s)M1：单一线，表示机床6向机床1申请刀具t1；

    M6-(s)M4：单一线，表示机床6向机床4申请刀具t2；

    M1-[M5，M6]：复选线，表示机床1向机床5和6申请刀具t3；

    [M3，M3，M4]-[M1，M6]：争用线，表示机床2，3，4向机床1，6申请刀具t4。

图2 刀具分派过程示意图分页

    算法过程如下：

    (1)TAP置空；

    (2)分析图2(a)所示的TAAG，M5为无出线节点，而M1获得M5上的刀具t3后就可以进行下道工序的加工，于是在TAP中加入一条分派记录：M5[t3]-M1，同时删去复选线M1-[M5，M6]；

    (3)重新生成TAAG如图2(b)所示，其中M1和M5为无出线节点，而M2，M2，M4获得M1上的刀具t4后都可以进行下道工序的加工，任选其一进行刀具分派，不妨令M4获得t4，则在TAP中加入一条分派记录：M1[t4]-M4，同时改变原争用线[M2，M3，M4]-[M1，M6]为[M2，M3]-[M4，M6]；

    (4)重新生成TAAG如图2(c)所示，其中M4，M1和M5为无出线节点，而M2，M3和M6获得相关刀具后都可以进行下道工序的加工，选择其一(如M2)获得所申请刀具，即在TAP中加入一条分派记录：M4[t4]-[M2]；

    (5)重新生成新的TAAG如图2(d)所示，此时争用线转化为复选线M3-[M2，M6]，图中M3和M6获得相关刀具后都可以进行下道工序的加工，选择其一(如M6)获得所申请刀具，即在TAP中加入两条分派记录：M4[t2]-M6，M1[t1]-M6，刀具分派后M6成为无出线节点；

    (6)重新生成新的TAAG如图2(e)所示，M6和M2都已成为无出线节点，选择其一(如M2)完成下道工序的加工，释放所占用的刀具t4，分派给M3，M3即可进行下道工序的加工，所以应在TAP中加入新的刀具分派记录：M2[t4]-M3；

    (7)重新生成TAAG如图2(f)所示，各节点均无出线，完成了刀具分派，输出TAP如下：

    M5[t3]-M1

    M1[t4]-M4

    M4[t4]-M2

    M4[t2]-M6，M1[t1]-M6

    M2[t4]-M3

    (8)结束。

4 结束语

    FMS中的刀具流死锁控制问题是工件流和刀具流联合调度的关键点和难点。本文在前期研究工作的基础上，对该问题作了进一步的分析。根据刀具流死锁的相关性质，指出了刀具流死锁的两大根源，并由此提出了两级死锁控制策略用以回避死锁的发生，建立了动态调度原理模型，最后给出了两级控制中的死锁检测算法和刀具分派算法。这些工作为下一步的深入研究准备了框架和基础。

[参考文献]
[1] 王志亮．汪惠芬．张友良．动态Job-Shop调度问题的一种自适应遗传算法[J]．中国机械工程，2004，(11)：995-999
[2] 赵天奇，陈禹六，李培根．基于零件虚拟工序队列的FMS动态调度研究[J]．中国机械工程．1999，(12)：1367-1369
[3] Korlam O。es al．A NeW cyclic schedding algorithm for flexible manufacturing systems[J]．International Journal of Flexible Manufacturing Systems，2002，14：177-191
[4] Mark A L Deadlock avoidance for production systems with flexible routing[J]．IEEE Transections on Robotics and Automation，1999，15(3)：497-508
[5] 欧阳普仁．FMS刀具管理系统体系结构研究[J]．南京理工大学学报，1996，20(3)：273-276
[6] 王解法，冯祖仁，李世敬等．柔性制造系统(FMS)刀具建模、词度仿真研究[J]．系统仿真学报，2003，(9)：1211-1213
[7] 苏加国，邹福生．FMS中刀具优化管理的数学建模与分析[J]．昆明理工大学学报，2002，(4)：38-41
[8] Koo P H，et al. Tool requirements in manufacturing system under dynamic tool sharing[A]．In：Proc．20th Int．Conf．comput Industr．Eng．[c]，1996
[9] 毕诸明，姜浩，朱岩等．FMS运控软件调试环境中的刀具流死锁的检测[J]．组合机床与自动化加工技术，1996，(1)：19-22
[10] Gebraed N Z．Lawley M A．Deadlock detection，prevention，and avoidance for automated tool sharing system[J]．IEEE Transactions on Robotics and Automation．2001，17(3)：342-356
[11] 舒海生，李庆芬，赵刚．一种解决FMS刀具流死锁问题的方法[J]．中国机械工程，2005，(11)t：965-969
[12] 侯刚．深入解析银行家算法[J]．潍坊学院学报,2006．(2)：46-48