数控加工中心任务与刀具集成调度模型及改进自适应遗传算法

周光辉,苗发祥,李彦广

(1.西安交通大学机械工程学院, 710049, 西安;2.西安交通大学机械制造系统工程国家重点实验室, 710049, 西安)

数控加工中心任务与刀具集成调度模型及改进自适应遗传算法

周光辉1,2,苗发祥1,李彦广1

(1.西安交通大学机械工程学院, 710049, 西安;2.西安交通大学机械制造系统工程国家重点实验室, 710049, 西安)

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

数控加工中心;刀具调度;并行加工;自适应遗传算法

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

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

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

1.1 变量符号定义

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

n:工件数。

Ji:工件i。

ki:工件i的工步数。

m:备选刀具数。

Mt:备选刀具编号。

Xij:工件i的工步j可使用的刀具集合。

Tijt:工件i的工步j用第t把刀具的加工时间。

Ct:刀具t单位时间的使用费用。

yijt:刀具使用系数,工件i的工步j使用刀具t时为1,否则为0。

Di:工件i的理想交货期。

ui:工件i拖期完工惩罚因子。

B:可并行加工工步组集合。

Sij:工件i的工步j的开始加工时间。

Eij:工件i的工步j的结束加工时间。

Ei:工件i的完工时间。

Ws:整个调度方案的刀具使用费用。

Wf:整个调度方案的任务拖期惩罚费用。

Wtotal:整个调度方案的加工费用指标。

1.2 任务与刀具集成调度数学模型

一台数控加工中心分配了n个工件{J1,J2,…,Jn}各工序(含1道或多道工步)加工任务,各工序包含的工步加工顺序由工艺要求预先确定,某些工步根据实际需要可并行加工。每道工步的可选加工刀具由工艺规程确定(对于特定加工特征,一般存在同类型的多把刀具可以满足要求),至少有一把待选刀具可对其进行加工,其加工时间随所选刀具的不同而不同,加工整批任务共有m把待选刀具{M1,M2,…,Mm}可供选择,n个待加工工件有各自的交货期要求{D1,D2,…,Dn}。调度的目标是确定所有工件的加工顺序并为每道工步选择合适的刀具,以使整批任务的加工费用指标达到最优。图1和表1描述了数控加工中心2工件、5刀具的集成调度问题。

图1 问题描述示意图

表1 问题加工信息表

注:“×”表示分配在该加工中心上的对应工步不可用该刀具进行加工;O11表示工件1的第1道工步,其余依次类推。

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

(1)不同工件的工步之间没有先后约束,同一工件的工步之间有先后关系,且提前已知,不可改动。

(2)同一工件的不同工步之间存在并行加工关系,并行加工情况提前已知。

(3)每个工件一旦开始加工不能中断。

(4)同一把刀具在某一时刻只能加工一个零件。

(5)工件具有各自的理想交货期和极限交货期。

(6)所有工件在零时刻都可以被加工。

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

(1)

零件拖期惩罚费用(此处假设这部分费用是滞后时间的线性函数)为

(2)

(3)

式中:Di,max为任务的极限交货期,与理想交货期Di的差值说明了工件的重要性。越重要的工件其交货期控制越严格,所允许的变动量就越小,反之越大。

据此得到加工费用指标的目标函数为

(4)

并受如下约束

(5)

(6)

(7)

Num{X11,…,X1k1,…,Xij,…,Xnkn}≤m

i=1,2,…,n;j=1,2,…,ki

(8)

Eij=Sij+Tijt,

i=1,2,…,n;j=1,2,…,ki;t∈Xij

(9)

Eij≤Si(j+1),i=1,2,…,n;j=1,2,…,ki

(10)

Ei≤S(i+1)j,i=1,2,…,n

(11)

Sij1=Sij2, [(i,j1),(i,j2)]∈B

(12)

式(5)说明,由于考虑了并行加工,可以有多把刀具同时进行加工;式(6)保证每把刀具同时只能加工一道任务;式(7)保证调度为所有任务的全排列;式(8)表示用于零件加工的所有刀具数量Num{·}不大于所提供的备选刀具数量;式(9)表示完工时间等于开始时间与加工时间之和;式(10)、式(11)保证后一道加工任务必须在前一道加工任务完成后开始;式(12)则保证并行加工的工步同时开始。

2 自适应遗传算法的设计

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

图2 自适应算法流程图

2.1 染色体编码与解码

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

为同时解决刀具选配和工件排序的问题,编码由两部分组成,aij是由整数部分和小数部分组成的实数。aij的整数部分是刀具染色体,表示工件i的第j道工步选择第[aij]把刀具进行加工([·]表示取整数),若[aij]=[aik], 且j≠k,则表示同一工件的不同工步采用相同刀具进行加工;aij的小数部分是加工顺序染色体,定义工件的加工顺序指标为

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

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

通过对矩阵元素的拆分后,即可确定调度方案,即先加工工件2,再加工工件1;工件2的2道工步分别采用刀具2和刀具1进行加工;工件1的3道工步分别采用刀具2、3、5进行加工。

2.2 适应度函数

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

(13)

式中:Wlk是第k代种群中第l个染色体的目标函数值;W*是第k代种群中最小的目标函数值;a是平均目标函数值与最小目标函数值之间的距离。

2.3 初始解的生成

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

对于图1,其工步-刀具关联矩阵见表2。

表2 工步刀具关联表

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

2.4 算法的进化操作

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

图3 改进自适应遗传算法交叉操作

图4 改进自适应遗传算法变异操作

类似交叉操作,变异也采用基于行和列的单点、两点和多点变异。在变异过程中,要保证[aij]∈Xij,从而保证染色体的合法性。

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

式中:Fmax为种群的最大适应度值;Fmin为最小适应度值;Favg为平均适应度值;F*为交叉个体中较小的适用度值;F为变异个体的适应度值。

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

(14)

(15)

如图5所示,在交叉操作中,当F*=Fmax时,Pc=Pc2,适应度最小的个体以最大的交叉概率将基因遗传至下一代。在变异操作中,当F=Fmax时,最优个体得到保护直接进入下一代,而当F=Fmin时,Pm=Pm2,最差的个体以最大的概率进行变异,以生成较为优良的个体。图5曲线的斜率可以清楚说明整个进化过程中各参数的变化趋势。同时,为保证每一代的优良个体不被破坏,本文采用精英选择策略,对前10%的优秀个体进行保护,确保算法的全局寻优性。

图5 遗传算法交叉、变异概率自适应变化曲线

3 实例验证与结果分析

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

3.1 加工实例介绍

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

表3 任务加工信息表

续表

表4 刀具使用成本表

改进自适应遗传算法采用MATLAB编程实现,最小、最大交叉概率Pc1=0.6、Pc2=0.9,最小、最大遗传概率Pm1=0.2、Pm2=0.5,种群规模设置为100,迭代次数为300次。

3.2 结果对比与分析

调度结果如图6所示,图中方框代表对应Z步加工过程,垂直线Di代表工件i的交货期。由图6a可知,在按交货期排序的加工方案中,从第3个工件开始拖期完工,拖期率达70%,拖期惩罚Wf=276元。在图6b工序优化后的方案中,只有工件1、2没有按交货期要求进行加工,拖期率降到20%,相应的拖期惩罚Wf=94.5元。

表5对两种方案的调度结果进行了对比,可以看出,采用遗传算法在对刀具进行选配的同时,对加工序列进行不断调整,可以最大限度地减少拖期工件数量,降低拖期惩罚,证明了本模型的可行性。

由以上结果可以看出,常规按照交货期顺序进行加工的调度方案会造成延误时间的叠加,从而影响任务整体的正常生产。采用本模型,通过损失部分不紧急子任务的准时生产,可以最大限度地换取任务整体加工的准时性。同时,本文的调度方案可以用于指导交货期的制定,如对工件1和工件2的交货期作适当调整,则整批任务的生产计划和调度方案则会更加合理。

由图7、图8实例求解的收敛过程可知,相比传统遗传算法,改进后的自适应遗传算法在最优值的收敛速度和平均值的稳定性方面都有较明显的提高,传统遗传算法需要250次迭代,而本算法只需要50次迭代,从而大大降低了算法收敛所需的迭代次数。

表5 调度结果对比表

(a)按工件交货期排序

(b)自适应遗传算法对工序进行优化

图7 适应度最优值收敛曲线比较

图8 适应度平均值收敛曲线比较

4 结束语

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

[1] 王解法, 冯祖仁, 李世敬, 等. 柔性制造系统(FMS)刀具建模调度仿真研究 [J]. 系统仿真学报, 2003, 15(9): 1211-1213. WANG Jiefa, FENG Zuren, LI Shijing, et al. Research on tool assembly model and schedule simulation in FMS [J]. Journal of System Simulation, 2003, 15(9): 1211-1213.

[2] 付春林. 高端车铣复合加工中心的应用 [J]. CAD/CAM与制造信息化, 2008(4): 96-98. FU Chunlin. The application of high-end turning-milling center [J]. Digital Manufacturing Industry, 2008(4): 96-98.

[3] BUYURGAN N, SAYGIN C, KILIC S E. Tool allocation in flexible manufacturing systems with tool alternatives [J]. Robotics and Computer-Integrated Manufacturing, 2004, 20(4): 341-349.

[5] 边培莹. PSO算法在FMS刀具可复用调度中的应用与仿真 [J]. 机械设计与制造, 2012(3): 76-78. BIAN Peiying. Application and simulation of PSO in FMS based on tools reusable scheduling [J]. Machinery Design & Manufacture, 2012(3): 76-78.

[6] 张亮, 楼佩煌, 胡武茹, 等. 一种改进型遗传算法在FMS刀具调度中的应用 [J]. 工业控制计算机, 2009, 22(9): 75-78. ZHANG Liang, LOU Peihuang, HU Wuru, et al. Application of an improved genetic algorithm for tool scheduling in FMS [J]. Industrial Control Computer, 2009, 22(9): 75-78.

[7] PRABAHARAN T, NAKKEERAN P R, JAWAHAR N. Sequencing and scheduling of job and tool in a flexible manufacturing cell [J]. The International Journal of Advanced Manufacturing Technology, 2006, 29: 729-745.

[8] 赵丹, 张家泰, 舒海生, 等. 基于双重遗传算法的工件流与刀具流综合调度优化 [J]. 西南交通大学学报, 2010, 45(6): 926-931. ZHAO Dan, ZHANG Jiatai, SHU Haisheng, et al. Double layer genetic algorithm for integrated scheduling optimization of part and tool flows [J]. Journal of Southwest Jiaotong University, 2010, 45(6): 926-931.

[9] 陈世哲, 刘国栋, 浦欣, 等. 基于优势遗传的自适应遗传算法 [J]. 哈尔滨工业大学学报, 2007, 39(7): 1021-1024. CHEN Shizhe, LIU Guodong, PU Xin, et al. Adaptive genetic algorithm based on superiority inheritance [J]. Journal of Harbin Institute of Technology, 2007, 39(7): 1021-1024.

(编辑 杜秀杰)

JobandToolIntegrativeSchedulingModelinCNCMachiningCenterandImprovedAdaptiveGeneticAlgorithm

ZHOU Guanghui1,2,MIAO Faxiang1,LI Yanguang1

(1. School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2. State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

To solve the integrated scheduling for job and tools in computer numerical control(CNC) machining center, a model considering delivery time and parallel processing of working steps is presented. And the minimized total cost of production is taken as the objective to achieve the collaborative optimization. An improved adaptive genetic algorithm is proposed where a job-tool relationship matrix is adopted to guarantee the legality of solutions, and a rational chromosome encoding and adaptive genetic operations are designed to accelerate the convergence rate and improve solving efficiency. The experimental examples are comparatively analyzed to verify correctness of the model. The proposed algorithm enables to maximally reduce processing cost and job tardiness rate and to improve the convergence rate and stability with greatly reduced iterations.

CNC machining center; tool schedule; parallel machining; adaptive genetic algorithm

2014-03-14。

周光辉(1972—),男,教授,博士生导师。

国家自然科学基金资助项目(51175414);教育部新世纪优秀人才支持计划资助项目(NCET-12-0452);国家科技支撑计划资助项目(2012BAH08F02)。

时间:2014-07-28

10.7652/xjtuxb201412001

TH166

:A

:0253-987X(2014)12-0001-07

网络出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20140728.1037.005.html