摘要：刀具寿命是加工生产率的一个重要限制因素。特别在多品种小批量的生产环境中，数控机床的刀库容量有限，一次换刀不能完成所有任务的加工。在加工过程中会有寿命用尽的刀具，或者任务所需刀型不在刀库里，需要进行换刀以满足任务的加工要求。然而频繁换刀会增加停机次数、换刀数量和使用新刀具数量，从而降低生产效率，增加配置成本。为了解决以上问题，设计出一种依据单个任务加工平均加工成本(ACSTP)的启发式规则，确定每次停机所覆盖的待加工任务序列长度，在任务序列可知不可变并且考虑到刀具寿命的情况下，合理动态配置加工中心刀库的刀具，使得完成既定任务序列的加工后，总的配置成本最小。同时，在实验中，以某复合加工中心刀库作为研究对象，通过和当前主流的KTNS换刀策略相比，验证ACSTP能够有效控制整体的配置成本。

　　关键词：刀具动态配置；刀具寿命；启发式规则

　　0引言

　　随着生活水平的提升，从商品实用性、价格、质量等关注的转变，也侧面反映了生产模式的变化。个性化、定制化的商品需求，使得少类型大批量的生产模式难以应对其发展需求，取而代之的是多类型小批量，这为当前制造业带来一定的经营压力。柔性生产过程当中，复合加工中心是关键。

　　刀具配置问题是金属制品加工中心里面重要研究课题，在加工中心当中可以装载若干把刀具，依据任务序列加工需求调用各类型刀具，由于受到任务序列、任务加工刀具类型需求、寿命需求等不同，随着任务数增加，无法在短时间内找到刀具配置方案和加工方案。Bard[1]针对柔性加工设备的刀具配置问题，提出一种最小化刀具更换次数的启发式方法。Commare[2]在类似问题当中，提出刀具失效时的更换策略，适用于一般性随机刀具寿命分布。Tang[3]针对不考虑刀具寿命的刀具配置问题上，提出KTNS(保留最近加工任务所需刀具)换刀策略。在考虑刀具寿命的刀具配置问题上，Billatos[4]强调刀具磨损数据是随机不确定的，为此构建了概率模型进行描述。使用近似表达式求解刀具更换时间间隔，并且确定加工条件组合。由于任务序列可变，Srivastava[5]将刀具配置问题转化为生产分批问题，构建0-1整数规划模型和模拟退火算法。Koo[6]和Matzliach[7]均是研究动态环境下的刀具配置问题。王解法[8]在研究减少刀具库存成本的配置问题上，引入刀具购买成本作为重要约束。在算法求解上面，Al-Fawzan[9]提出禁忌搜索算法。Catanzaro[10]在Tang研究基础上，提出新的整数规划公式，相比之下更容易收敛。Song[11]提出一种t启发式方法，在任务序列不固定的情况下，相比KTNS策略效果更好。Furrer[12]创新性地提出一种分支定界算法框架，适用于小中规模的精确求解。钟南星[13]首次提出虚拟刀具和物理刀具概念，提出单库换刀算法流程和多库拼刀的协同过程。Bernard[14]研究了刀具寿命和可变加工速度的刀具配置问题。周喜稳[15]提出基于模糊理论的配置方法，并设计智能算法求解。张敏新[16]建了刀具磨损过程的过程能力指数，而Yuhao[17]针对刀具磨损问题，结合对数正态函数，给出刀具参考寿命分布函数。Raduly[18]所研究问题包括在线刀具模块和离线刀具模块。和以往的优化方向不同，曹乐[19]提出单位产品平均成本作为优化目标。较新的研究当中，王新刚[20]提出一种基于刀具失效率指标的刀具更换工序和停机时间的方法。Yang[21]提出了刀具重复利用问题。

　　刀具配置问题本质是一个高维的组合优化问题，本文针对考虑刀具寿命可重复利用的动态刀具配置问题，相对该问题的特征进行分析，然后针对换刀策略提出一种考虑单位任务加工成本指标的换刀策略，通过大量的仿真案例测试，并且越与KTNS换刀策略进行比较，表明该方法在某些情况下，仍然可以获得很不错的效果。

　　1问题描述及分析

　　刀库是复合加工中心里面刀具的载体，上面有若干个刀位，可以依据需要安装不同刀具类型。当刀库所有刀具不能满足任务序列上任务的加工要求时，可以停机，从机器刀库中拆卸刀具放进车间存放刀具的刀库中，并且从车间存放刀具的刀库选取刀具装载进机器刀库，如图1和图2所示。停机次数、新刀折旧和刀具装卸都是加工过程重要的可控成本，如何对刀库刀具配置，才能使得总耗费的可控成本最低，是一个复杂的科学问题。

　　在M企业的制造车间当中，复合加工中心里面的刀库上刀位集合为Q(刀位元素i=1，2，3，…，q)。初始状态下，刀架上有所有类型刀具，其类型集合为K(刀具类型元素j=1，2，3，…，k)。待加工任务集合为T(任务集元素r=1，2，3，…，t)，ar表示完成任务r对刀具寿命的耗费。dr,j为0-1变量，取值为1时，表示第r个任务使用第j类型的刀具。Xi(r)是任务r加工之前到位i的状态向量，O表示零矩阵，其大小为q×k。

　　2方案设计

　　2.1背景

　　刀具配置问题是一个复杂组合优化问题，随着任务序列的长度、刀具类型、刀库刀位数量、刀具寿命等增加，问题计算复杂也指数增长，并且该问题具备动态规划问题的重要特征，后续决策过程，取决于当前刀库状态、待加工任务序列的组合等，如图3所示。与以往的刀具配置问题不同，本文所研究刀具配置问题，刀具在不达到报废标准的临界时，仍然可以暂时撤下存储刀刀架，在后续的换刀决策当中，依据需求更换上可用旧刀。

　　另外，实际制造过程中，任务序列长短不同，一方面，要求换刀决策能够快速反应，在极短时间内给出决策方案，另外一方面，针对不同长度的任务序列，换刀结果的鲁棒性要好。目前，暂且没有可以直接应用于该问题下的解决方案。考虑到问题规模大和决策时间短的特性，本文基于KTNS换刀策略，提出一种考虑刀具寿命、单位任务加工成本的启发式算法。

　　2.2方案设计

　　在初始状态下，复合加工中心的刀库上所有刀位均为空，刀架所有刀具均为新刀，当刀库中刀具剩余使用寿命或刀具类型不满足下一个任务加工时，停机，进行换刀，且每次换刀后刀库没有空刀位。由于情况相对简单，在初始决策过程中，采用贪心策略进行刀具配置，从第0个任务开始，判断刀库的刀具是否能够满足该任务加工，如果可以，则判断下一个任务；如果不可以，判断是否有空刀位，添加该任务所需刀具类型，如此直至刀库刀位均被装满，完成初始决策过程，开始加工。

　　启动加工之后，当刀库上刀具剩余使用寿命或刀具类型不满足下一个任务加工时，停机，进行换刀。在每次停机之后，换刀策略的选择可以直接影响配置成本。在任务序列足够长的情况下，往往无法在加工之前，对所有刀具配置过程方案进行筛选比较，即无法获取最优解。因此，该研究提出，一种依据单个任务加工平均加工成本(ACSTP)的决策指标，确定每次停机所覆盖的待加工任务序列长度，在换刀决策时综合考量刀库中刀具和刀架上已使用刀具的剩余使用寿命、使用新刀的成本，以使得在本次换刀时单个任务加工平均加工成本最优。

　　同时，为了减少剩余使用寿命低的刀具占据刀库刀位和重新装载进刀库，定义了刀库中刀具的移除优先级和刀具报废的寿命值，在移除刀库刀具时按优先级移除刀具。其中，在换刀时，若刀库中达到报废状态的刀具信息，将此类刀具列入移除列表，并将移除优先级为1；若刀库中未报废的但后续任务不需用到的刀具信息，将此类刀具列入移除列表，并将移除优先级为2；若刀库中未报废的后续任务需用到的刀具信息，考量此类刀具的剩余使用寿命、下一个任务用到此刀具的距离，来计算此类刀具的移除优先级，并将此类刀具列入移除列表。

　　对于需要装载进刀库的刀具，优先考虑将刀架上已使用过的且满足此次换刀决策加工要求的刀具，装载进刀库中。其大致过程如图4所示。

       3结果对比

　　在本节中，将本文提出的ACSTP算法和文献中现有的KTNS算法进行比较，其中修改KTNS算法以处理考虑刀具寿命的刀具配置问题。根据前面的数学模型，设定问题的规模为T=600，K=15，Q=10。同时，设定刀具报废系数和不同的成本参数，比较在不同的刀具报废系数(LE)和不同的成本参数(RC)下两种算法的优劣性。其中：LE=0.1，0.2，…，0.8；RC=0.03，0.05，0.1，0.2，…，0.9，1，2，3，…，10。RC=停机成本/(新刀成本+换刀成本)。为了研究两种算法的优劣性，通过随机生成任务虚列，随机生成刀具初始使用寿命，生成10个数据集进行实验。图5所示为两种算法10个数据集的平均成本之差(ACSTP平均成本-KTNS平均成本)，从图中可以看出，在刀具报废系数小于1或大于6时，ACSTP算法的表现优于KTNS算法，刀具报废系数约在[1，5]区间时，KTNS算法表现的优于ACSTP算法。通过分析换刀过程，发现刀具报废系数小于1，ACSTP算法得出的停机次数多于KTNS算法，使用新刀的数量和换刀的数量则相对少于KTNS算法；而刀具报废系数约在[1，5]区间时，ACSTP算法得出的停机次数多于KTNS算法，使用新刀的数量和换刀的数量则相对少于KTNS算法择差距较小；发现在刀具报废系数大于6时，ACSTP算法得出的停机次数和使用新刀的数量于KTNS算法的差异较小，换刀的数量则相对少于KTNS算法。

　　图6所示为两种算法在不同的成本参数比值下的平均总成本，从图中可以看出在刀具报废参数为0.45时，ACSTP算法明显优于KTNS算法。图7所示为两种算法在不同的刀具报废参数下的平均总成本，从图中可以看出在成本参数比值为0.2时，ACSTP算法也明显优于KTNS算法，并且，随着刀具报废系数的增加，KTNS算法下的平均总成本增长大于ACSTP算法。

　　4结束语

　　考虑刀具寿命的刀库配置问题，先前的研究省略了由于刀具寿命耗尽而导致的刀具切换，集中在单一的刀具类型的问题上，换下的刀具没有再次使用。基于此，本文综合考虑了停机成本、使用新刀成本和换刀成本，以最小化总换刀成本为研究目标，提出基于换刀规则和局部搜索的启发式算法，通过和现常用于刀具更换的KTNS算法进行比较，测试本文算法的相对性能。可以看出，本文提出的算法在停机成本小于新刀成本和换刀成本时优于KTNS算法。显然，本文提出的算法使用新刀的数量和换刀次数小于KTNS算法。将来，在本文的基础上，计划将刀具指派加工任务考虑在本问题，以提高刀具的使用率，减少换刀次数。此外，计划优化搜索空间避免进入局部最优。

　　参考文献：

　　[1]BARD,Jonathan F.A Heuristic for Minimizing the Number of Tool Switches on a Flexible Machine[J].AIIE Transactions,1988,20(4):382-391.

　　[2]Commare UL,Diega SNL,Passannanti A.Optimum tool re⁃placement policies with penalty cost for unforeseen tool fail⁃ure[J].International Journal of Machine Tool Design&Reasarch,1983,23(4):237-243.

　　[3]Tang C S,Denardo E V.Models arising from a flexible manufac⁃turing machine(Part I:Minimization of the number of tool switch⁃es.Part II:Minimization of the number of switching instants)[J].INFORMS,1988.

　　[4]Billatos SB,LA Kendall.A general optimization for multi-tool manufacturing systems[J].Journal of Manufacturing Science&Engineering,1991,113(1):10-16.

　　[5]Srivastava B,Chen W H.Batching in production planning for flexible manufacturing systems[J].International Journal of Pro⁃duction Economics,1996,43(2-3):127-137.

　　[6]Pyun Hoi Koo,JM A Tanchoco,Jeseph J Talavage.Tool Require⁃ments in Manufacturing Systems under Dynamic Tool Sharing[J].Computers&Industrial Engineering,1997,33(3-4):537-540.

　　[7]Matzliach B,Tzur M.The online tool switching problem with non-uniform tool size[J].International Journal of Production Re⁃search,1998,36(12):3407-3420.

　　[8]王解法,冯祖仁,李世敬,等.数控车间中央刀具库的资源调度与配置研究[J].信息与控制,2003,32(5):448-452.

　　[9]Al Fawzan M A,Al Sultan K S.A tabu search based algorithm for minimizing the number of tool switches on a flexible machine–Science Direct[J].Computers&Industrial Engineering,2003,44(1):35-47.

　　[10]Catanzaro D,Gouveia L,LabbéM.Improved integer linear pro⁃gramming formulations for the job Sequencing and tool Switch⁃ing Problem[J].European Journal of Operational Research,2015,244(3):766-777.

　　[11]Song C Y,Seongwhan S.The tool switching problem on a flexi⁃ble machine in a dynamic environment[J].2009,25(1):84-88.

　　[12]Martina,Furrer,Torsten,et al.An algorithmic framework for tool switching problems with multiple objectives[J].European Journal of Operational Research,2017.