FMS混合调度中的两种启发式规则*

舒海生 赵 刚 赵 丹

（哈尔滨工程大学，黑龙江哈尔滨 150001）

FMS混合调度中的两种启发式规则*

舒海生 赵 刚 赵 丹

（哈尔滨工程大学，黑龙江哈尔滨 150001）

针对FMS混合调度系统中的工件选择和运刀小车的启发式调度问题，给出了两个新的启发式规则，即在机床选工件策略中建立了刀具外借量最少规则，在运刀小车任务调度策略中提出了目标机床当前工序完成时间最早规则，通过仿真实验验证了两种启发式规则的有效性。结果表明所提出的两种调度规则能够较好地改善FMS的各项性能指标。

FMS 刀具流 调度策略

传统的FMS动态调度研究［1－7］大多集中于工件流调度，较少考虑刀具流对工件流的影响，少量关于刀具方面的研究［8－10］也大都集中在管理系统的组织架构上以及单一刀具流系统中，现有的一些调度策略和规则在工件流和刀具流的混合调度系统中具有较大的局限性，不利于改善和提高系统综合性能。本文针对综合调度系统中的调度策略问题进行了分析，从工件流和刀具流的辩证统一关系出发，提出了两种新的调度策略：刀具外借量最少规则和目标机床当前工序完成时间最早规则，分别应用于机床选工件和运刀小车选任务的调度过程中。这两种规则的突出特点在于它们着眼于系统整体性能的提高，充分考虑了工件流和刀具流的相互作用关系，较之传统的调度规则更为合理，有效地提高了FMS混合调度各项性能指标。

1 FMS混合调度原理

本文在基于虚拟工序队列技术的工件流调度方法［2］的基础上，进一步将刀具流考虑进来，建立了FMS混合调度模型（图1）。

整个调度过程从机床完成当前工序加工时刻1开始，首先判断机床输入缓冲区是否存在待加工工件，若存在，则判断该工件待加工工序所需刀具是否已齐备，若不齐备，则该机床当前为不可决策机床，不能进行下一个待加工工件的选择，而应等待运刀小车的刀具运送；若刀具已齐备，则工件被搬上机床开始加工。当前时刻即成为系统决策点，可以进行机床选工件决策，利用刀具流死锁检测算法选择确保刀具流不发生死锁的工件，并根据刀具分派算法计算出当前系统中合理的刀具分配方案，之后发出工件运送命令启动工件流和刀具申请启动刀具流，并驱动小车适时运送。

由动态调度模型可以看出，工件选择模块是工件流进程和刀具流进程的接口，主要用于为机床选择合适的下道工序。当系统决策点到来时，可决策机床在各自的虚拟工序队列中决策选取下道工序，根据所选工序的刀具需求生成相应的刀具申请表，然后进行死锁判定，从中选择不会导致死锁的下道工序，最后生成相应的刀具申请表。

死锁判定的相关算法和原理已在另文［11］中详细阐述。此处主要针对工件流中的机床选工件策略和刀具流中的运刀小车服务策略进行重点分析。

2 机床选择工件策略

机床选择工件策略有很多，如处理时间最短策略、处理时间最长LPT策略、剩余工序加工时间最短策略、剩余工序加工时间最长策略、随机选择策略和松弛量最小策略等等［4］。这些传统的调度规则虽然各有其适用场合，但是它们大多没有考虑刀具流的影响。

在混合调度系统中，由于工件流和刀具流是相互影响和相互制约的，为提高系统效率，减小刀具流负荷，从控制刀具交换次数的角度给出了一种新规则，即刀具外借量最少规则：

设机床刀具库中现有的刀具集为P，P中已被其他机床预定借用的刀具集为Q，又设Wi为该机床可加工工序集W中的一道工序，WTi代表Wi所用的刀具集，Wi所需外借的刀具数量为wi，引入求集合元素个数的运算符“||”，则有下式成立：

于是该规则即可描述为

由定义不难发现，该规则优先选择向其它机床申请刀具数量最少的工序作为本机床的下一道待加工工序，这就使得任意时刻系统中的刀具申请数量得到尽可能的控制，从而能够显著地减少刀具交换次数，改善系统性能。

3 运刀小车的服务策略

运刀小车的服务策略问题是指当FMS中多台机床提出刀具运送申请时，从资源争用的角度出发，哪台机床应该最先得到服务；从作业选择角度出发，小车应首先选择哪台机床为服务对象，也即小车响应策略问题。运刀小车的服务策略一般有先进先出策略，按权优先策略，“瓶颈”优先策略，时间最短策略，数量最少策略，时间最长策略，数量最多策略，就近服务策略等等。

事实上，决定运刀小车的服务顺序是一个很复杂的问题，以上策略均是针对某一方面的问题而设置的，因而在实际应用中有其局限性。应同时考虑几种情况，并采用仿真的方法进行模拟，才能取得较佳的服务策略。

从工件流和刀具流相互作用关系出发，运刀小车应该首先满足最迫切需要相关刀具的任务，这样才能使得机床尽早进入加工状态。为此，本文给出一种新的服务策略——目标机床当前工序完成时间最早规则，即运刀小车优先运送任务队列中目的地机床的t1最小的任务。

设运刀小车的任务队列为Taskqueue［］，其中的任务对象为Taskqueue［i］，（i=0，1，2，…，k）包含了三个属性，即：起始运送地i－Start，目的运送地i－Destination，刀具编号 i－ToolNo，并设 i－Destination 表示机床编号，t1（i）表示i－Destination机床的当前工序完成加工时刻t1，那么这种服务策略事实上就是选择任务Taskqueue［i］作为当前任务，使之满足下式：

Min（t1（i）），（i=0，1，2，…，k）该策略在运送机床加工所需刀具时考虑了对工件流效率的影响，使得系统中最迫切需要相关刀具的机床能迅速得到运刀小车的服务，减少了机床等待刀具的时间，提高了系统的生产效率。

4 实验与分析

为检验这两种新的调度规则对系统性能的影响，下面给出了两个仿真对比实验，比较了传统的调度规则与本文提出的两种启发式规则的优劣。

实验1：考察了运刀小车任务选择策略的影响，主要比较了随机选择策略和目标机床当前工序完成时间最早规则。

采用随机选择策略，在不配备中央刀库的情况下对生产计划如表1所示的64个工件进行了综合调度仿真，结果如表2所示。

然后采用目标机床当前工序完成时间最早规则进行仿真，结果如表3所示。

由表2可计算出各机床总等刀时间值为503 min，平均等刀时间值为125.75 min，由表3则可计算出各机床总等刀时间值为352 min，平均等刀时间值为88 min。实验结果表明，采用目标机床当前工序完成时间最早规则后系统中机床的平均等刀时间由125.75 min减少到88 min，减小幅度达到30.01%。正是因为等刀时间得到大幅降低，所以后者的系统总生产率 有了较大提高，由2 202件/h提高到2 265件/h，增加了2.25%。说明本文提出的新规则是十分有效的。由仿真结果还可发现，运刀小车选任务策略对换刀次数影响很小。

表1 生产计划

表2 随机规则仿真结果

实验2：考察了机床选择工件策略的影响，主要比较了随机选择策略和刀具外借量最小策略对系统性能的影响。

首先采用随机选择策略，在不含中央刀库的情况下进行仿真，结果与表2相同。其次采用刀具外借量最小规则进行仿真，结果如表4所示。

由表2可计算出各机床总等刀时间值为503 min，平均等刀时间值为125.75 min，由表4可计算出各机床总等刀时间值为484 min，平均等刀时间值为121 min。实验结果表明，采用刀具外借量最小规则后系统中机床的平均等刀时间有小幅减少，系统生产率也有少量提高。由此可见，机床选工件规则对于等刀时间和系统生产率的影响是较小的。但是通过表2和表4的比较可以发现，采用刀具外借量最小规则后系统总换刀次数有了大幅度的减少，由随机规则下的225次下降到现在的84次，降幅达66.7%，这说明机床选工件规则对于换刀次数有着重要影响，本文给出的刀具外借量最小规则可以有效地减少换刀次数，从而能在实际生产中降低刀具交换频率、缩短辅助时间，并能减少因刀具交换频繁导致设备故障发生的概率。

表3 目标机床当前工序完成时间最早规则仿真结果

表4 刀具外借量最小规则仿真结果

5 结语

FMS混合调度中工件流和刀具流是相互联系、相互作用的，机床选择工件策略的确定必须充分考虑所选工件对刀具流的影响，运刀小车选择任务策略的确定也必须考虑到要尽可能减少工件流的等刀时间，只有这样才能获得较好的综合效益。本文提出的两种启发式调度规则能够有效地改善系统运行性能，提高系统生产率。仿真结果表明：

（1）运刀小车选择任务策略对系统等刀时间和系统生产率有很大影响，目标机床当前工序完成时间最早规则可以有效地减少系统等刀时间，同时提高了系统生产率；

（2）机床选择工件策略对于系统等刀时间和系统生产率的影响较小，但是对于系统总换刀次数却有着重要影响，刀具外借量最小规则可以十分有效地减少总换刀次数。

［1］周炳海，蔡建国.基于定向搜索的FMS调度优化算法［J］.组合机床与自动化加工技术，2001（10）：1 －4.

［2］赵天奇，陈禹六，李培根.基于零件虚拟工序队列的FMS动态调度研究［J］.中国机械工程，1999，10（12）：1367 －1369.

［3］徐刚，吴智铭.一种运用图论进行FMS无死锁调度的方法［J］.机械科学与技术，2004（4）：412 －415.

［4］王志亮，汪惠芬，张友良.动态Job－Shop调度问题的一种自适应遗传算法［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中刀具优化管理的数学建模与分析［J］.昆明理工大学学报，2002（4）：38 －41.

［9］欧阳普仁.FMS刀具管理系统体系结构研究［J］.南京理工大学学报，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］.哈尔滨工业大学学报，2006（10）：1681 －1688.

如果您想发表对本文的看法，请将文章编号填入读者意见调查表中的相应位置。

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

* 黑龙江省自然科学基金（E0312）资助项目

舒海生，男，1976年生，副教授，博士，主要从事生产计划与调度和智能制造系统等方面的研究工作，已发表论文10篇。

（编辑 周富荣） （收修改稿日期：2010－02－23）

10713