1 引言
按照工件的处理方式，柔性制造系统(FMS)可分为两类：工件移动系统和刀具移动系统。在工件移动系统中，一旦工件的调度确定下来，加工中心所配置的刀具就不会再改变，除非刀具断裂或磨损；而在刀具移动系统中，每个工件在一个加工中心执行完所有的操作后才能卸下来，所以必须在该工件加工开始之前，准备好所有必须的刀具。刀具移动的系统比工件移动的系统具有以下优势而得到广泛使用，①刀具较小，而工件较重，实现刀具移动的自动化系统成本较低；②容易实现刀具的自动安装和定位。在刀具移动系统中，每把刀具都是作为整体在机床之间频繁借用的，这种借用会产生刀具延迟，进而对工件的加工产生时间上的拖延，这种拖延由两部分组成：刀具运输时间和刀具等待时间，所谓刀具运输时间就是把刀具从一个机床运送到另一个机床的时间，所谓刀具等待时间就是等待正在使用被借刀具的机床加工完当前工件的时间。一般刀具运送时间远小于工件的加工时间，且对工件的在制时间没有明显的影响，所以减小刀具等待时间是解决刀具延迟的主要途径。
刀具是制造过程中的一个重要资源，占到各种制造成本的25%～30%。在制造车间，不合理的刀具配置常常使16%的生产调度无法进行，40～80%的时间都用来寻找或补充刀具。由于刀具引发的问题严重影响了车间的生产效率，所以加强刀具管理已越来越得到人们的重视。
所谓刀具需求规划，就是如何配置柔性制造系统所需刀具规格的数量，使得刀具资源对生产过程的影响尽可能小。本文以一个刀具移动的柔性制造系统为背景，研究了在允许的刀具购买资金预算下，如何规划给定任务的刀具需求并尽量减小任务的在制时间。
2 问题描述
本文研究的刀具移动柔性制造系统包含若干相同的箱体类数控机床和一个中央刀具库。每台数控机床都有一个容量有限的机床刀具库，而中央刀具库的容量比较大 (可认为无穷大 )。当有工件加工完后，工人把当前机床不用的刀具 (包括磨损刀具 )从机床刀具库中卸下并送入中央刀具库，同时把下一个工件所需的剩余刀具从中央刀具库装入机床刀具库；若该工件所需的刀具不能全部装入机床刀具库时，多余的刀具暂时存放在中央刀具库中，当该工件的部分工序结束后，再装入其它刀具以进行以后工序的加工。一旦工件装配到某个机床上，它应该在完成所有的工序后才卸下来。每个工件加工所需的刀具全部都安装到机床刀具库，机床才能对该工件进行加工。加工过程中的刀具借用由人工来完成。
由于加工过程中有刀具的磨损，我们假定每个刀具都有可以估计的使用寿命，当刀具的使用寿命小于所有使用该刀具的工序时间长度时，我们认为该刀具不能再使用。为了保证生产的正常进行，一定数量的同规格刀具必须同时装载到中央刀具库中以供备用。如果每种规格的刀具数量较多，加工中的刀具借用次数就少，刀具的等待时间就短，任务的在制时间就小；反之，如果每种规格的刀具数量较少，加工中的刀具借用次数就多，刀具的等待时间就长，任务的在制时间就大。如何在一个容许的刀具购买资金预算下配置中央刀具库中的刀具规格和数量，并最大限度的减少任务的在制时间，是本文研究的内容。在本文中，假定：
不考虑机器故障；
每台机床最多只分配一把同一规格的刀具；
每把刀具只占用一个刀盘位置；
每一个工序的执行时间确定，且事先已知；
3 求解在制时间和刀具等待时间的递归算法
3.1 问题简化
在刀具移动的柔性制造系统中，刀具的控制策略决定了哪把刀具从哪个机床借用以及用完后是否归还，所以刀具控制策略是产生刀具等待时间和运送时间的根源。但是，大量的实验数据表明，刀具控制策略对任务的在制时间没有明显的影响；实际生产车间布局范围都比较小，刀具的运送时间远远小于刀具的等待时间，也远远小于工件的加工时间。
所以，在下文中，我们均不考虑刀具的运送时间和刀具的控制策略。这样，所有机床对刀具的申请都可以看成是向中央刀具库提出来的，而机床刀具库仅仅变成对机床所能使用刀具数的一种形式上的约束。因此，整个加工过程中中央刀具库配置的修改可以看成这样：当机床加工完机床刀具库所允许的所有工序后，把后面工序不再需要的刀具放回中央刀具库，同时把后面工序需要的刀具装入机床刀具库。在工件的调度策略确定下，求解任务的在制时间和每个机床对所需刀具的等待时间可以采用递归的方法来计算。要注意的是，当某种规格的一把刀具的使用寿命到达时，可以看成该规格刀具的总数量减1，当某种规格的刀具数量为0时，则所有等待该规格刀具的时间都为无穷大。整个加工过程类似于资源约束下的项目调度问题。在下文中，为了简化计算，我们假定每个工件仅需要一道工序，这种假设对问题的分析不会产生影响。
3.2 算法步骤
令W为所有刀具规格集合，称向F=(n1，n2，…，n|W|)为中央刀具库的状态或配置，其中ni表示刀具规格i的数量，ni≥0，iÎ W。为了方便描述，在不会引起混淆的情况下，当特指“一个具体规格的刀具”时，我们在下文中有时也用“刀具”简化称呼，读者可联系上下文理解。
记M为柔性制造系统中的机床数目，Pim机床m在时刻ti时当前工件剩余的加工时间长度。ti的修改方程为：
| ti=ti-1+min(Pi-11，Pi-12，…，Pi-1n)。 | (1) |
用Om表示指定给机床m加工的工件集合，Ajm表示机床m加工工件j时最后得到的刀具集合，Om表示指定给机床m加工的工件集合，Tj表示工件j所需的全部刀具集合，djm表示机床m等待Ajm的有效等待时间长度，它表示工件j最后一次借到刀具的时间和上一次借到刀具的时间差，j Î Om，mÎM。为了防止由于刀具的短缺而产生无限制的等待，我们在算法中设计了一个定时器Timer，当其计数值超过设定的最大时间时，说明算法进入了无限制的等待，从而自动退出。求解在制时间和刀具等待时间的递归算法(算法1)的主要步骤如下：
step1 i=0，ti=0，Ajm=Tj，djm=0，lm=0，" 1 £ m £ M，" j £ Om，初始化所有机床的状态为空闲，初始化Timer为一个较大的整数；
Step2 如果所有机床的状态都为空闲且其队列都为空，Makespan=ti，停止。如果Timer定时时间到达，Makespan=¥，停止。
Step3 卸载所有在ti时刻状态为空闲的机床上的工件，并把所有闲置的刀具归还中央刀具库；
Step4 按机床正在装载时间的长度非递增排序得到机床序列m1，m2，…，mM；
Step5 令k=1；
Step6 如果机床的状态为空闲，则
Step6.1 如果机床mk的等待队列为空，Step8；
Step6.2 如果机床mk的等待队列不为空，从该机床的等待队列中取优先级最高的工件j并装载到该机床上，令djmk=¥，修改该机床的状态为正在装载，lm=ti；
Step7 如果机床mk的状态为正在装载，如果中央刀具库中有工件j所缺的闲置刀具，则选择这些刀具，修改中央刀具库的状态。如果工件j所需的刀具还没有装载完毕，修改Ajm中的集合元素，lm=ti；否则，=ti-lmdjmk，修改该机床的状态为正在加工。
Step8 k=k+l，如果k≤M，转Step6；
Step9 i=i+1，按公式(1)移动ti到下一次正在加工工件的完时刻，并置相应机床状态为空闲，转Step2；
（图片）
图1 算法迭代示意图 4 规划中央刀具库配置的启发式算法
本节介绍的启发式算法就是逐步增加关键机床上的关键刀具的数量，所谓关键机床就是指所有机床中最后一个加工完工件的机床，所为关键刀具就是指“刀具的等待时间之和/刀具成本”最大的刀具。算法的重复执行过程可以用图1来描述。假定机床3在当前这一步是关键机床，任务的在制时间在A点结束，那么在初始中央刀具库状态中增加机床3加工过程中关键刀具的数量，重新计算任务的在制时间和关键机床，并确定关键机床上的关键刀具。假设机床3在B点结束，这一步任务的在制时间在C点结束，机床1变成了关键机床，则在初始中央刀具库中增加机床1加工过程中的关键刀具的数量，依此类推。整个过程不断重复，直到超过允许的刀具购买资金。本文的算法综合了一些其它文献的思想。
本文仅研究刀具需求规划问题。虽然工件调度对在制时间影响很大，但这是一个非常复杂的问题。我们可以认为在制时间由两部分组成：一部分由工件调度引起，另一部分由刀具配置引起。性能最好的工件调度策略可以通过比较来选择，但这不是本文的重点。在以后的描述中，我们均假定工件调度策略已经确定。
令B为允许的刀具购买资金，Ci为刀具规格i的购买价格。则规划中央刀具库配置的算法(算法2)如下：
step1 ni=1，对所有iÎ W，；
step2 采用算法1求的关键机床(如果有多台关键机床，任意取其中一台作为关键机床)，记为c，同时得到Ajc和djc，" j Î Oc；
step3 令i=1；
step4 令j=1，xi=0；
step5 如果 i ÎAjc，则xi=djc+xi；
step6 j=j+1，如果j≤|Oc|，转Step5；
step7 i=i+1，如果i≤|W|，转step4；
step8 按xi/Ci非递增的顺序排列得到刀具序列t1，t2，…，t|Oc|；
step9 令k=1
step10 如果Ctk£ B'，则ntk=ntk+1，B'=B'-Ctk，转Step2；
step11 k=k+1，如果k > |W|，停止。否则，转Step10；
5 计算结果与比较
计算环境如下：机床数4～8，工件数目30～80，每个工件所需得刀具规格数30～50，刀具规格总数50～100，每个工件的执行时间50～100，每种规格刀具的价格10～100，使用寿命为2000～3000，每台机床的机床刀具库容量固定为60，允许的刀具购买资金预算取任务所需的最小刀具成本的1.5倍，最小刀具成本就是当在制时间不为无穷大时任务所需的最小刀具集合的成本。
工件调度策略采用如下两个经常使用的策略：
加工时间最短的优先(SPT)；
加工时间最长的优先(LPT)；
我们随机产生了60个问题来测试，并和其它某文献中最优算法TGSA进行比较。为了使其具有可比性，我们在编写TGSA算法时，令刀具的运送时间为0，并修改本文介绍的递归算法来求解任务的在制时间和每把刀具的实际等待时间。由于无法得到最优解，我们取相对性能比(relative performance ratio，RPR)作为评价标准，RPR定义为(Sa-SB)/SB，Sa表示采用算法a得到的解，SB表示两个算法中的最优解。表1列出了两种算法的比较结果。
表1| 工作调度策略 | 问题规模(M，P，T) | 问题数量 | RPR | NBS | | 本文 | TGSA | 本文 | TGSA | | SPT | (4，40，50) | 10 | 0.11 | 0.13 | 10 | 7 | | SPT | (6，70，40) | 10 | 0.17 | 0.21 | 8 | 8 | | SPT | (8，60，40) | 10 | 0.14 | 0.23 | 10 | 9 | | LPT | (4，70，50) | 10 | 0.09 | 0.14 | 9 | 8 | | LPT | (6，40，50) | 10 | 0.16 | 0.21 | 7 | 7 | | LPT | (8，50，40) | 10 | 0.10 | 0.12 | 9 | 8 | 1 M、P、T表示机床数目、工件数、每个工件所需的刀具规格数目；
2 平均RPR；
3 最优解次数
从表1可以看出，无论采取什么工件调度策略，本文介绍的算法和TGSA相比，都有较优的解。我们分析原因如下：
TGSA增加刀具时不考虑关键机床，导致某些等待时间较长而对在制时间没有影响的刀具浪费了刀具购买资金，而本文算法恰恰避免了这种情况的出现；
TGSA严格的把刀具按其成本分为A，B，C三类，没有综合考虑其对在制时间的影响，本文以刀具在关键机床上的等待时间之和与刀具成本之比来定义关键刀具，综合了单位成本上的等待时间，有效利用了刀具购买资金；
6 结论
文章主要讨论了柔性制造系统的刀具需求规划问题，首先利用已有文献所报道的结论简化了实际问题，给出了求解在制时间和刀具等待时间的递归算法，同时给出了一个求解刀具需求规划的启发式算法。为了观察该算法的性能，我们通过随机数据产生并构成了60个刀具需求规划问题，并采用两种不同的刀具调度策略进行了数据测试。和已有算法进行比较后，我们发现无论采取什么工件调度策略，文章介绍的算法都具有较优的解。
5/29/2004
|
