摘要：为解决数控加工中心任务与刀具的集成优化调度问题，以生产总成本最小为优化目标，建立了考虑任务交货期和工步并行加工的数控加工中心任务与刀具集成调度模型，产生面向数控加工中心任务与刀具的协同优化调度结果。为实现对该调度模型的优化求解，提出了一种改进自适应遗传算法，设计了合理的编码方式和自适应进化操作，并通过任务－刀具关联矩阵保证搜索过程中解的可行性，从而显著提高了算法的收敛性能和求解效率。算例结果表明，该模型能够最大限度地降低加工成本和拖期率，同时算法的收敛速度和稳定性也得到了明显提高，大大降低了问题求解的迭代次数。

      关键词：数控加工中心；刀具调度；并行加工；自适应遗传算法

　    随着车间加工自动化程度的日益提高，数控装备逐渐取代传统的加工机床，成为企业加工的核心，显著提高了企业的加工质量与效率，而刀具作为数控加工中心的重要组成部分，受到了越来越多的关注［１］。与传统的加工机床相比，数控装备特别是高端数控加工中心（如车铣复合加工中心）更能适应多品种、小批量生产模式需求，具有多工序、多工步并行加工的特点，能满足复杂多尺度产品的加工需求［２］。但是，在数控加工中心的加工过程中，为保证其多任务的柔性、高效、高质量、低成本加工需求，加工任务（工序、工步）的合理排序与刀具资源的合理选配已经成为迫切需要解决的关键问题，二者相辅相成、缺一不可。特别是刀具资源在逐步成为企业瓶颈资源的基础上，刀具选配的合理与否将直接关系到任务的加工效率和生产成本。在此环境下，探求一种合适的任务与刀具集成调度方案对提升数控加工中心的加工质量与效率就显得尤为重要［３－６］。

      在传统的数控加工中心加工中，任务与刀具规划调度是割裂开来的［７－８］。加工任务的规划与调度过程中未考虑刀具的制约因素，并假定刀具资源是充足的，而刀具的选配则是依据规划好的加工任务（加工顺序）来直接分配，二者是一种串行的因果关系。显然，该方法并未充分考虑任务与刀具之间的制约关系，从加工成本、加工效率等角度考虑，得出的方案往往是可行方案，而非最佳方案，甚至导致不可行方案的产生。为此，本文针对单台数控加工中心，从任务与刀具调度协同优化的角度出发，提出一种数控加工中心任务与刀具集成调度方法与模型，并采用自适应遗传算法实现对模型的优化求解，得出任务与刀具优化分配、调度结果，达到提升数控加工中心的加工效率、刀具资源利用率及降低加工成本的目标。

      １　、数控加工中心任务与刀具集成调度模型

      １．１　变量符号定义

      在建立数控加工中心任务与刀具集成调度数学模型之前，首先定义如下变量符号。

      １．２　任务与刀具集成调度数学模型

      一台数控加工中心分配了ｎ 个工件｛Ｊ１，Ｊ２，…，Ｊｎ｝各工序（含１道或多道工步）加工任务，各工序包含的工步加工顺序由工艺要求预先确定，某些工步根据实际需要可并行加工。每道工步的可选加工刀具由工艺规程确定（对于特定加工特征，一般存在同类型的多把刀具可以满足要求），至少有一把待选刀具可对其进行加工，其加工时间随所选刀具的不同而不同，加工整批任务共有ｍ 把待选刀具｛Ｍ１，Ｍ２，…，Ｍｍ｝可供选择，ｎ个待加工工件有各自的交货期要求｛Ｄ１，Ｄ２，…，Ｄｎ｝。调度的目标是确定所有工件的加工顺序并为每道工步选择合适的刀具，以使整批任务的加工费用指标达到最优。图１和表１描述了数控加工中心２工件、５刀具的集成调度问题。

  
      加工过程中需要满足以下约束条件。

     （１）不同工件的工步之间没有先后约束，同一工件的工步之间有先后关系，且提前已知，不可改动。
     （２）同一工件的不同工步之间存在并行加工关系，并行加工情况提前已知。
     （３）每个工件一旦开始加工不能中断。
     （４）同一把刀具在某一时刻只能加工一个零件。
     （５）工件具有各自的理想交货期和极限交货期。
     （６）所有工件在零时刻都可以被加工。

      基于以上假设，本文以最小化加工费用为优化目标，除刀具使用费用外，由于考虑交货期要求，可能会存在工件不能准时完工的情况，所以如何减小拖期工件数量，降低拖期惩罚费用也是本问题的关键。综上，总费用应包括刀具使用费用和拖期惩罚费用，由问题定义易知刀具使用费用为

      式中：Ｄｉ，ｍａｘ为任务的极限交货期，与理想交货期Ｄｉ的差值说明了工件的重要性。越重要的工件其交货期控制越严格，所允许的变动量就越小，反之越大。据此得到加工费用指标的目标函数为

      式（５）说明，由于考虑了并行加工，可以有多把刀具同时进行加工；式（６）保证每把刀具同时只能加工一道任务；式（７）保证调度为所有任务的全排列；式（８）表示用于零件加工的所有刀具数量Ｎｕｍ｛·｝不大于所提供的备选刀具数量；式（９）表示完工时间等于开始时间与加工时间之和；式（１０）、式（１１）保证后一道加工任务必须在前一道加工任务完成后开始；式（１２）则保证并行加工的工步同时开始。

      ２　、自适应遗传算法的设计

      由于传统遗传算法在求解类似问题过程中，存在着收敛速度慢，常陷于局部最优值的缺点。本文为实现对刀具与任务集成调度问题的综合求解，采用自适应遗传算法，通过在搜索过程中，交叉、变异概率的自动变化来提高算法的收敛速度，跳出局部最优解。算法流程如图２所示。

      ２．１　染色体编码与解码

      数控加工中心的刀具与任务集成调度问题需要为每个工件的每道工步选择一把刀具，并对所有待加工任务进行排序，因此编码需同时考虑这两方面的问题。总体上采用如下实数矩阵编码结构

      ｛·｝表示取小数。约定按Ｐｉ值由小到大确定各工件的加工顺序。融合这两部分编码，便可形成一个表示刀具与任务集成调度方案的矩阵编码。

      为保证整个矩阵的维数相同，约定凡小于最大工步数的工件整数部分编码用０表示。例如图１的工件２、刀具５调度问题，其矩阵编码为

      通过对矩阵元素的拆分后，即可确定调度方案，即先加工工件２，再加工工件１；工件２的２道工步分别采用刀具２和刀具１进行加工；工件１的３道工步分别采用刀具２、３、５进行加工。

      ２．２　适应度函数

      适应度值是评价解的优良性能的重要指标，本文是求解目标函数最小化问题，故采用如下反比例函数作为适应度函数

      ２．３　初始解的生成

      初始解的质量对于遗传算法的求解效果有较大影响，采用随机初始化会产生较多的不可行解，需要算法在优化过程中不断剔除，这就增加了搜索过程的迭代次数和收敛时间。本文通过引入工步－刀具关联矩阵来保证进化过程中刀具分配方案的可行性。若用ｙｉｊｔ表示矩阵元素（ｉ为工件号，ｊ 为工步号，ｔ为刀具号），其取值规则为

      在解编码的初始化与交叉、变异过程中，始终对照该矩阵，选择ｙｉｊｔ＝１的刀具号生成编码，从而产生可行调度方案，提高算法搜索过程的稳定性。

      ２．４　算法的进化操作

      交叉操作主要为保留父代个体的优秀基因。为保证交叉之后染色体的合法性，本文采用染色体同位置基因互换的方法，基于该原则，交叉操作可以多样化设计。本文针对矩阵编码分别采用基于行和列的单点、两点和多点交叉，如图３、图４所示。

      类似交叉操作，变异也采用基于行和列的单点、两点和多点变异。在变异过程中，要保证［ａｉｊ］∈Ｘｉｊ，从而保证染色体的合法性。

      对于交叉、变异过程，优良个体以较高的概率交叉更符合自然法则；低劣个体以较大概率变异，这更有利于保护并产生新的优良解。这一原则应该体现在整个进化操作过程中。文献［９］对自适应遗传算法的Ｐｃ、Ｐｍ做以下调整

      上述调整一定程度上改进了遗传性能，但不足之处在于，用线性函数表示交叉、变异概率的变化过程，无法描述整个进化过程中参数的变化幅度。为了更清晰地说明在进化不同阶段参数变化的幅度区别，进一步提高算法的自适应性，本文引入三角函数来表示这一变化过程，重新给出交叉、变异概率的计算公式如下

      ３　、实例验证与结果分析

      为了验证模型的正确性，并比较本文自适应遗传算法在解决该问题中的优越性，特设计加工实例进行分析。在模型方面，设计按交货期顺序加工模型与本模型进行对比；在算法上，设计传统遗传算法与本算法进行比较。

      ３．１　加工实例介绍

      本文以西安西电开关有限公司机加车间为应用示范基地，以型号ＮＨ６３００－ＤＣＧ的数控加工中心的一批实例加工任务为例，计算其调度过程。实例中，该加工中心分配了１０个工件某一道工序的加工任务，每道工序包含了多道工步。现提供１２把待选刀具对整批任务进行加工，与任务相关的刀具需求信息、加工时间、刀具使用成本、并行加工信息及各加工任务交货期等信息如表３、表４所示。

      改进自适应遗传算法采用ＭＡＴＬＡＢ编程实现，最小、最大交叉概率Ｐｃ１＝０．６、Ｐｃ２＝０．９，最小、最大遗传概率Ｐｍ１＝０．２、Ｐｍ２＝０．５，种群规模设置为１００，迭代次数为３００次。

      ３．２　结果对比与分析

      调度结果如图６所示，图中方框代表对应Ｚ 步加工过程，垂直线Ｄｉ代表工件ｉ的交货期。由图６ａ可知，在按交货期排序的加工方案中，从第３个工件开始拖期完工，拖期率达７０％，拖期惩罚Ｗｆ＝２７６元。在图６ｂ工序优化后的方案中，只有工件１、２没有按交货期要求进行加工，拖期率降到２０％，相应的拖期惩罚Ｗｆ＝９４．５元。

      表５对两种方案的调度结果进行了对比，可以看出，采用遗传算法在对刀具进行选配的同时，对加工序列进行不断调整，可以最大限度地减少拖期工件数量，降低拖期惩罚，证明了本模型的可行性。由以上结果可以看出，常规按照交货期顺序进行加工的调度方案会造成延误时间的叠加，从而影响任务整体的正常生产。采用本模型，通过损失部分不紧急子任务的准时生产，可以最大限度地换取任务整体加工的准时性。同时，本文的调度方案可以用于指导交货期的制定，如对工件１和工件２的交货期作适当调整，则整批任务的生产计划和调度方案则会更加合理。

      ４、　结束语
 

       对于数控加工中心的一批加工任务来讲，刀具选配与任务规划是影响加工总成本的两个关键环节，只有将两者结合在一起共同优化，才有可能得到该批任务加工总成本的全局最优解。为此，本文提出了数控加工中心任务与刀具的集成调度方法与模型，并利用改进后的自适应遗传算法对该问题进行求解，最后设计加工实例对问题模型和算法进行分析。结果证明，结合本模型和改进后的自适应遗传算法，可在实际生产中得到更为满意的结果。