刀具寿命约束下柔性机床自修复遗传调度算法

朱旭东

(无锡工艺职业技术学院,江苏 宜兴 214200, E-mail: zhuxud1980@163.com)

传统单一、大批量的制造模式无法满足当前多样性、灵活性、个性化的多元化生产需求,因此诞生了适用于小批量、多品种的柔性生产模式。针对给定的生产任务,合理的机床调度方案能够有效提高企业的竞争力和经济效益[1]。刀具是机床加工的关键资源,刀具健康状态对机床调度方案的实施具有及其重要的影响[2]。因此,考虑刀具寿命的柔性机床调度问题具有重要的经济价值,可以提高企业竞争力。

柔性作业车间调度问题可以分为单目标调度和多目标调度。单目标调度是指通过合理安排工序和机床,达到某一指标意义下的最优,常用方法包括精确解法、启发式算法。精确求解法包括分支界定法[3]、混合整数规划法[4]等,该类方法能够得到精确的最优解,但是仅适用于小规模调度问题。启发式算法可以适用于大规模、复杂的车间调度问题,包括遗传算法、粒子群算法、差分进化算法等[5～8]。多目标车间调度与决策方法主要分为先验法和后验法,先验法是指通过权重系数将多目标调度问题转化为单目标调度问题,是先决策优化重心再优化的方法[9];后验法是先优化再决策的方法,首先优化得到Pareto前沿解,而后决策出最优解[10]。文献[11]针对机器和工序柔性的车间调度问题,使用离散回溯搜索算法得到了多目标的Pareto解集,通过实例验证了该方法的有效性。文献[12]建立了辅助资源约束柔性车间调度的混合整数线性规划模型,并使用遗传算法解决该问题,经验证提出的算法提供了实现最小完工时间所需辅助资源数量的准确结果。文献[13]结合入侵肿瘤生长优化算法和NSGAIII算法,提出了求解柔性作业调度问题的多目标优化算法,结果表明该方法求解速度更快、解集分布更加均匀。

在刀具资源约束的机床生产调度中,传统的调度方法只考虑机床调度,而假设刀具能够随时、完全满足机床生产要求。但是柔性车间生产是在机床和刀具的协作下完成的,仅考虑机床调度或仅考虑刀具调度,会存在刀具和机床不匹配的问题,进而影响车间的生产质量和生产效率[14-15]。另外,传统调度方法没有考虑刀具使用寿命问题,使得机床在生产过程中不得不停运换刀,然而每次换刀都会极大地降低生产效率,因此在机床调度过程中应当考虑刀具寿命约束。

为了解决机床或刀具独立调度时产生的不匹配问题,本文建立了工序、机床、刀具联合调度模型,同时考虑了刀具的使用寿命约束,提出了基于自重启遗传算法的联合调度算法。最后通过车间生产实例验证了本文方法的有效性。

1 柔性车间联合调度模型

1.1 问题描述

假设柔性制造车间共有N个工件加工任务,记为J=[J1,J2,…,JN];工件n(n=1,2,…,N)的工序数量为ni,记为Oi=[Oi1,Oi2,…,Oini];可以使用的制造机床为K台,记为M=[M1,M2,…,MK];刀具共有V把,记为T=[T1,T2,…,TV]。

考虑刀具使用寿命约束的工序、机床、刀具联合调度问题描述为:在满足工件各工序的生产顺序约束下,设计合理的工序加工顺序,为各工序安排一个满足加工要求的机床,同时从刀具中选择一把可用、满足寿命约束的刀具,实现生产时间最短、加工成本最小等目标。需要说明的是,根据实际加工情况,各工序的生产时间由机床和刀具共同决定。

将考虑刀具寿命约束的柔性车间联合调度问题进一步明确,主要包括以下子问题:

(1) 为各工序进行生产排序;

(2) 为各工序分配满足要求的加工机床;

(3) 为各工序分配可用刀具。

1.2 联合调度问题建模

为了建立科学合理、清晰可用的联合调度模型,结合柔性车间生产的实际情况,做出以下假设:

(1) 工序加工时间由机床和刀具共同决定,且已知;

(2) 任一工序开始加工后,不允许强制中断;

(3) 各工件之间无生产优先级,即优先级一致;

(4) 刀具的剩余寿命是已知的;

(5) 忽略刀具运输时间、机床间物流时间及成本;

(6) 工序加工过程中,机床和刀具不发生故障等突发情况;

(7) 各工序的加工机床和刀具确定后,不再更换。

在上述假设条件下,根据后文的自重启遗传算法和解空间迭代调整的特点,本文的优化目标为:在不增加完工时间的前提下,实现生产成本最小化,即优化目标为:

(1)

式中:f为目标函数;ni为工件Ji的工序数量;CMk为机床k的单位时间使用成本;CTv为刀具v的单位时间使用成本;Tijkv为工序Oij在机床k和刀具v的加工时间;xijkv为标识字,定义如下:

(2)

工序、机床、刀具的联合调度约束条件如下:

(3)

式中:Cij为工序Oij的完工时间,Sij为工序Oij的开始时间,RLkv为刀具Tv的剩余寿命。

约束条件中第一式表示工序顺序约束,即工序Oij与Oi(j-1)的完工时间差需大于工序Oij的加工时间;第二式表示每个机床和刀具只能同时对一个工序进行加工;第三式表示刀具的使用时间需在寿命范围内;第四式和第五式表示每个工序只能由一台机床和一个刀具加工;第六式为参数的非负约束。

2 自修复遗传算法

本文基于遗传算法对工序、机床、刀具联合调度问题进行求解,但是当算法中种群的多样性较低时,算法容易陷入局部最优,极大地影响求解质量[16-18]。为了解决这一问题,本节提出了自修复遗传算法,主要包括多样性计算和自修复策略两个方面。

2.1 染色体多样性计算

▲图1 染色体编码

在遗传算法中,使用工序链、机床链、刀具链等三条基因链编码方式。以3工件7工序、3机床、5刀具为例,某染色体编码如图1所示。该染色体解码为:工序加工顺序为:O11→O21→O12→O31→O22→O32→O13,机床链和刀具链为对应使用的机床和刀具编码。

染色体多样性需同时对工序多样性、机床多样性和刀具多样性进行衡量,按照这一原则,染色体多样性计算步骤如下:

Step 1:假设工序总数为Q,设计一个位置多样性矩阵P=[Pab]Q×Q,其中Pab是指第a个工序在第b列出现的频次。

Step 2:当Pab>1时,说明工序a在第b列多次出现,此时统计工序a对应的机床和刀具连接矩阵,为

(4)

Step 3:设计一个中间变量Dab,将其定义为:

(5)

Step 4:综合考虑工序、机床和刀具连接多样性,将染色体多样性定义为:

(6)

2.2 自修复策略

设计一个多样性阈值wth,当染色体多样性存在w≥wth时算法继续;当w

在染色体的自修复中,工序链使用随机生成方式进行修复,机床和刀具使用定向修复策略。所谓定向修复,是指统计机床链和刀具链中的机床和刀具频次,将最高频次的机床和刀具不断进行替换的过程,步骤如下:

Step 1:以随机方式产生染色体中的基因链和满足要求的机床链、刀具链;

Step 2:统计机床链和刀具链中各机床和刀具的频次;

Step 3:将频次最大的机床和刀具替换为可选机床和刀具,而后返回至Step 2;

Step 4:达到设置的修复次数时,修复过程结束。

2.3 基于自修复遗传算法的初步调度流程

本节使用自修复遗传算法对工序、机床、刀具联合调度问题进行初步求解,具体流程如下:

Step 1:设置调度场景,包括工件加工任务、可用机床、可用刀具、使用成本、加工时间等参数;

Step 2:设置算法参数,包括染色体规模、算法迭代次数、交叉概率、变异概率、染色体多样性阈值、自修复次数;

Step 3:染色体执行交叉、变异等遗传操作,并进行自然选择;

Step 4:若算法未达到最大迭代次数,算法转至Step 3;若达到最大迭代次数,输出最优染色体,算法结束。

由于工序加工顺序和频次约束,传统的交叉、变异操作后需要进行人工交叉和调整,为了避免这一问题,本文使用文献[19]的POX交叉和有向变异操作。

3 解空间迭代调整的再调度算法

3.1 解空间迭代调整的再调度流程

为了直观表达基于自修复遗传算法的初步调度流程、基于解空间迭代调整的再调度流程以及两者之间的耦合关系,以流程图的形式给出算法框架,如图2所示。

▲图2 调度流程图

3.2 解空间迭代调整策略

对于某工序Oij,可能存在多种机床与刀具组合,且不同组合方式的加工成本是不一致的。将工序Oij的当前加工成本与最低加工成本差值定义为:

ΔMCijkv=MCijkv-min(MCijkv)

(7)

式中:MCijkv为工序Oij的当前加工成本,min(MCijkv)为工序Oij的最低加工成本。

对于任一工序Oij,ΔMCijkv越大表示该工序成本减少空间越大,因此将ΔMCijkv最大的工序确定为关键工序,其对应的工件、机床和刀具确定为关键工件、关键机床和关键刀具。

若工序Oij具有多个机床和刀具组合,在满足加工时序约束前提下,通过将Oij替换为其余机床和刀具组合,实现加工时间不增加前提下生产成本减少。其中时间约束为:

(8)

综上所述,解空间迭代调整过程如下:

Step 1:计算当前调度方案中的每个工序的ΔMCijkv;

Step 2:将ΔMCijkv按照由大到小的顺序排列,记为ΔMC={ΔMC1,ΔMC2,…,ΔMCN};

Step 3:将ΔMC1对应的工件、工序、机床和刀具确定为关键工件、关键工序、关键机床和关键刀具;

Step 4:判断是否存在可用机床和刀具使关键工序的生产成本减少,若不存在则从ΔMC中去除ΔMC1,而后返回Step 2;若存在则算法继续;

Step 5:修改关键工件的解空间,从关键工序的可用机床中去除关键机床;

Step 6:输出调整后的生产调度解空间。

4 实验与分析

4.1 实验设置

本文以某航空公司的飞机结构件为加工对象,该结构件以钛合金和复合材料为主,因此硬度极大。如此硬度的结构件需要整体硬质合金刀具才能进行加工,此类刀具价格昂贵且使用寿命较短。因此,可以通过合理的机床和刀具联合调度,达到减少换刀次数和降低生产成本的目的。

飞机结构件生产车间具有5个加工位,其中加工位1～4放置有制造机床M1～M4,加工位5为预留位置,如图3所示。除此之外,该生产车间还具有物流小车、托盘、物流缓存库等。

▲图3 柔性生产线

机床M1～M4的生产成本分别为600 元/h、500 元/h、400 元/h、300 元/h。加工任务为10个飞机结构件,每个结构件均具有11个工序,结构件各工序的可用机床、刀具、加工时间均一致,如表1所示。

表1 各工序可用机床与刀具

各刀具的使用成本及单次使用寿命如表2所示。

表2 刀具使用成本及寿命

4.2 实验结果分析

为了验证本文自修复遗传算法的工序、机床、刀具联合调度效果,同时使用该生产线自带的调度控制系统、文献[20]基于TGS算法的调度方法、本文基于自修复遗传算法的调度方法等,TGS算法参数按照原文进行设置,自修复遗传算法参数设置为:染色体规模为100、算法迭代次数为500、交叉概率为0.3、变异概率为0.1、染色体多样性阈值为0.15、自修复次数为5。

使用自带调度系统、TGS算法、自修复遗传算法对5.1节的生产案例进行调度,各自独立运行10次,取10次结果中的最优调度方案进行比较,结果如表3所示。

表3 联合调度结果

由表3可知,基于自修复遗传算法的最优调度方案生产成本为92 240元,比自带调度系统减少了16.55%,比TGS算法的调度方案减少了8.20%;加工时间为51.6 h,比自带调度系统减少了7.36%,比TGS算法的调度方案减少了2.46%;换刀次数为0次,比比自带调度系统减少了10次,比TGS算法的调度方案减少了3次。上述数据表明,自修复遗传算法的调度方案实现了生产成本、加工时间的双重优化,且换刀次数也最少,与自带调度系统、TGS调度算法相比有效提高了生产效率。

这是因为自修复遗传算法在对生产成本进行优化时,前提是不增加加工时间,因此实现了生产成本和加工时间的双重优化;另外,自修复遗传算法实时关注种群中染色体多样性,当染色体多样性较低时,启动自修复策略用于提高染色体多样性,从而提高了解的质量和调度方案的质量。

将自修复遗传算法搜索的最优染色体进行解码,得到最优调度方案的Gant图如图4所示。图4中方框内为刀具编号,方框下方为该机床和刀具加工的工序编号。由图4可以直观看出,该生产方案的工序均满足生产顺序约束,同一工件的后一工序均在前一工序加工完成后开始;另外,各机床的生产负担大致相当,意味着机床负载较为均衡。

统计每个刀具在各机床上的合计加工时间,结果如表4所示。

表4 刀具在各机床累计使用时间

以刀具T1为例分析表4可知,其在机床M1上累计使用了7.9h,在机床M2上累计使用了5.9 h,在机床M3上累计使用了5.0 h,在机床M4上累计使用了4.8 h,均未超过刀具T1的使用寿命,即在刀具T1的使用寿命范围约束内。按照同样的分析方法可知,刀具T1～T8在各机床上的使用时间均未超过其使用寿命,这意味着自修复遗传算法的调度方案满足刀具寿命约束,这也意味着在生产加工过程中无需更换刀具,可以有效提高车间的生产效率。

▲图4 生产方案甘特图

5 结论

本文研究了刀具寿命约束下的柔性车间工序、机床、刀具的联合调度问题,提出了基于自修复遗传算法和解空间迭代调整的联合调度方法。经验证得出以下结论:在10个飞机结构件、各结构件11个工序的柔性加工实验中,本文算法得到的调度方案具有最小的生产成本、最少的加工时间和刀具更换次数,验证了自修复遗传算法和解空间迭代调整策略在柔性车间联合调度问题中的优越性。