基于Drools 规则引擎的柔性化钣金产线优化排程①
2022-03-09王梓林
任 彬 王梓林
(上海大学机电工程与自动化学院上海市智能制造及机器人重点实验室 上海 200444)
0 引言
柔性化产线作为新一代智能制造系统的基础,是智能生产的主要载体。柔性化产线自感知、自适应、自学习、自决策的形成,是我国实现产品制造向现代化、数字化、智能化靠近的关键一步[1]。钣金柔性生产线也向着自动化、智能化方向发展。由于钣金加工具有多品种、小批量的离散制造典型特征,传统的人工调度和排程方法不能满足生产需求。通过应用现代智能优化算法对生产排程问题求解,可以有效提高排程效率并搜寻出复杂排程问题的最优解,解决生产制造多目标、多任务、多工序的生产排程问题。
生产排程的求解寻优问题一直是国内外学者研究的热点,研究方向主要集中在求解算法方面[2-4]。文献[5]开发出一种双目标随机局部搜索启发式算法,通过在搜索路径上生成多个非支配解改善寻优方式。文献[6]提出用于实际的聚类算法以解决钣金成型行业在单机系统中依赖于序列相关转换时间的问题。文献[7]结合整数编程方法和分解方法实现更短时间内提供更高质量的解决方案。国内关于排程算法方面也有大量的研究[8-9]。文献[10]提出优先级策略改进非支配排序遗传算法(NSGA2)解决炼钢-连铸调度中求解精度问题。文献[11]针对智能车间复杂性程度高、动态不确定性明显等问题提出一种将离散仿真与遗传算法相结合的调度规则挖掘方法。文献[12]针对大规模置换流水车间调度问题,提出一种改进的模拟退火算法求解调度问题。
随着智能制造时代的到来,工业物联网技术推动下的高级计划与排程系统(advanced planning and scheduling,APS)发展呈现“协同社会化”,智能车间的APS 需能够发挥出智能的优势[13]。车间生产过程中面对复杂的情况往往需要考虑多种目标建立规则约束条件以最大化利益,如在钣金生产过程中,需考虑时间及诸多成本消耗等。由此寻优过程中目标增多,现代智能优化算法在判断方案优劣时,复杂程度增加,迭代寻优过程消耗较多的时间。而小批量、离散化特征的钣金加工订单具有较多不可预估的临时插单情况,要求能快速更新排程方案,传统的方案优劣判断难以满足要求。
针对上述柔性化钣金产线生产排程问题,本文在订单按时交货的基础上以最小化综合成本及损耗为目标,引入Drools 规则约束引擎,通过约束匹配取代多目标寻优中复杂的适应度计算,研究适用于柔性化钣金产线快速寻优生产排程方法。最后通过柔性化钣金产线的结果分析,验证了排程方法的有效性。
1 柔性化钣金产线的排程问题
1.1 柔性化钣金产线的需求
钣金加工生产多品种、小批量的离散制造特征使得人工排程变得困难。传统离散制造业的生产计划大多是用办公软件手工进行排程,计划的优劣程度主要由计划员的经验决定,在订单量较大的情况下难以短时间得出较好的生产计划,紧急插单的情况更是难以快速更新计划,且传统生产计划大多较为粗糙,对车间生产只具有简单的指导意义。如此,传统的排程方式不能满足柔性化车间生产需求,它不仅需耗费大量的人力,难以保证计划的时效性,且不能发挥出柔性化钣金产线的信息化管理优势、产能优势[14]。
图1 所示为柔性落料折弯钣金产线。该柔性钣金产线由数控设备和机器人组成,自动化程度高,可用来加工多种钣金零件或产品。各加工单元任务相对独立,互不干扰,由管理系统统一按照生产流程下发任务清单,不需严格工序衔接。
图1 柔性落料折弯钣金产线
柔性化钣金产线加工订单从下单到成品入库的一般生产流程如图2 所示。为保证订单能按时完成加工,计划排程是生产流程中不可缺少的一环。
图2 钣金加工生产流程
柔性化钣金生产线相对于传统的钣金生产线产能提升很高,而由于钣金订单需求一般为小批量,且品种繁多,发挥产能优势代表订单量巨大。将紧急插单的情况考虑在内,以保证订单按时加工完成为基础,迅速形成或更新生产计划成为生产排程的关键。此外,考虑最小成本、最小设备损耗,多目标寻优成为迅速排程的难点。
1.2 柔性化钣金生产的排程规划
钣金生产排程规划问题的求解可以视为求解约束满足问题(constraint satisfaction problem,CSP)[15]。CSP 由一个变量集合和一个约束集合组成,约束描述一个变量子集与子集内各变量的相容赋值,所有约束的逻辑“与”构成了问题的一个实例[16]。CSP的求解即找到满足所有约束或能最大化满足约束的变量赋值。实际情况中更多要求为在满足约束的条件下得到CSP 优化解。而当CSP 约束增加、目标变多时,解的优劣性确定将变得复杂,为快速得到解的优劣情况以便下一步迭代优化,引入规则引擎对解进行评价函数计算。本文结合Drools 规则引擎建立生产规则约束,利用Java 的多线程优势,研究适用于柔性化钣金产线的快速寻优生产排程方法。
规划问题包括规划实体、规划变量和问题事实。规划实体是指被规划的对象,如车间生产的生产线及其设备,生产排程的任务即对生产线上的设备进行时间及任务分配,从而优化生产线产能;规划变量是指对规划实体的最终效益产生影响的可调整的量,即规划过程中需要确定的变量,如确定生产任务的生产设备及生产时间;问题事实则为规划问题中的业务情况,为问题提供资料,如生产排程问题中设备数量等。
为求解钣金生产排程CSP 问题,结合规划问题定义提出如图3 所示的Drools 规划问题求解方法。该方法包括生产实况了解、规则约束建立、Drools 规则引擎邻域搜索法求解及结果表达4 个步骤。针对前述问题,该方法将算法迭代寻优过程与Drools 规则引擎相结合,通过规则引擎表达并匹配约束与目标,以此对迭代过程中的解集进行优劣性的判断,并通过评分模型对优劣性进行量化表示。采用Drools规则引擎表达匹配约束目标,清晰简单表示生产过程中复杂的约束及多个目标,方便规则调整以适应多变的车间生产状况,并可逐条快速匹配约束情况。
图3 规划问题求解方法
在明确规划实体、规划变量、问题事实的关系并确定规划问题的求解方法后,采用该方法求得柔性化钣金产线优化排程方案。优化排程方案求解的核心为结合Drools 规则引擎的邻域搜索法,包括求解器和评价器两部分,求解器主要功能为迭代搜索解决方案,在实际生产问题事实(fact)基础上,通过邻域搜索迭代新的方案。评价器的核心为Drools 规则引擎,将生产实际约束及目标表达为规则(rules),结合三级评分模型对搜索方案进行得分计算,量化表示方案优劣情况。最终得出优化排程方案,结果表示为甘特图。
2 规则约束建立
2.1 优化目标表述
在制造行业中,按期交货和降低成本是生产商重视的。由此建立以最小综合成本及设备损耗为优化目标约束模型,考虑到生产过程所有成本如用电成本、人工成本等,此外还考虑所有设备损耗,确立目标如下。
制定生产计划,在实现按期交货的前提下,以最小成本为指标,减小设备损耗。
式(1)和式(2)分别表示生产过程中的综合成本和设备损耗。式中i 表示订单任务的序号;j 为生产线序号;n、m 分别为生产订单数量和生产线数量;fm1为最低成本消耗,主要考虑比重较大的人力资源成本fP和电力成本fQ;Qej、Qoi和Qss分别为空闲电耗、生产电耗和启停电耗;fm2表示最低设备损耗;Loi、Lss分别表示生产损耗和启停损耗;Sj为生产期间各生产线的启停次数。
2.2 生产约束表述
综合考虑生产过程中的约束,包括在交货期前完成加工生产及加工生产固有约束等。此外,钣金加工生产情况变化频繁,生产商习惯对订单设定加工紧急等级来附加额外的加工顺序,并希望尽量按照紧急等级顺序进行加工。为方便量化表示解的优劣情况,将约束分为三级以配合评分模型量化表示,并将优化目标作为中等约束以便通过Drools 规则引擎表达。由此建立如下约束。
(1)硬约束
1)按期交货:订单必须在订单下达之后开始生产并在交期之前完成。
2)最大容量:每条生产线有一定加工容量,加工生产需占用一定加工容量,要求所排任务量占用容量不得超过对应生产线的最大容量。
式(3)和式(4)分别表示按期交货及生产线生产最大容量限制。式中To、Ts、Td分别为下单时间、订单开始生产时间、收货截止时间,Ni、Nj为某个时刻排入的生产订单占用容量和生产线允许加工容量。
(2)中等约束
1)人力资源成本:生产期间需技术管理人员并消耗人力成本。
2)电力成本:生产线运行消耗电力成本。
3)设备损耗:生产线运行会造成一定设备损耗。
4)设备功耗:不同生产线加工和空闲都消耗不同电功。
5)任务功耗:不同产品生产消耗不同电功。
6)启停消耗:设备启动或关闭需额外的电功并造成一定损耗。
中等约束为优化目标的前提,具体表现如式(1)、式(2)所示。
(3)软约束
1)尽早生产:订单尽早开始生产。
2)紧急顺序:加工生产顺序尽量按照订单紧急等级进行。
3)仓库成本:原材料及成品的存储需要仓库成本。
式(5)～(7)为软约束,表现为次要目标,相较主要目标而言比重较小,故仅作为软约束考虑。其中fs1表示尽早生产,fs2为按照紧急等级排序的量化分,fs3表示最低仓库成本,St表示按照紧急加工等级顺序的排序量化分,Cdm、Cdp分别为材料仓库成本和成品仓库成本。
2.3 目标函数
由图3 规划问题求解方法中,在建立约束后对调度问题进行迭代求解。在求解过程中智能优化算法决定寻优路径,如遗传算法通过染色体(解集编码)的选择、交叉、变异产生新族群(解集),粒子群算法通过粒子(解)的运动产生新粒子群等。本文针对钣金排程问题拟采用局部搜索法对生产方案进行搜索寻优。传统解的优劣情况通过适应度(fitness)的计算确定。适应度在实际情况中表现为对所提出的规则约束和目标要求的符合程度,根据钣金实际加工生产状况提出的目标及约束要求,适应度的计算如下。
式中,Hs表示硬约束违反情况,Hs=0 时表明硬约束没有被违反,为可行解;反之硬约束被违反,解不适用,适应度为0。
当Hs=0 时,适应度为两部分之和,分别表示软约束和中等约束的符合情况。分子中ws、wm分别为软约束和中等约束的权重系数,中等约束的权重大。分母中各项分别对应相应约束,见式(1)、(2)、(5)～(7),rsi、rmi(i=1,2,3)则表示约束的权重。
由式(9)可见,适应度的计算非常复杂,这是由多目标寻优的性质决定的,当目标函数较多时,解优劣的确定也随之复杂起来。本文采用Drools 规则匹配代替适应度计算,通过Drools 引擎表达规则极大地利用Java 多线程的优势[17],并可通过规则引擎的规则匹配功能,实现约束的快速匹配。Drools 作为主流的规则引擎之一,适合在复杂、变动频繁的业务规则上应用[18]。由此适应度可以通过匹配结果量化简单表示为
式中Ss和Ms分别为Drools 匹配软约束和中等约束的量化得分。
3 评价与求解
3.1 Drools 规则引擎
Drools 规则引擎主要由规则库、匹配引擎和工作空间三部分组成[19],如图3 所示,规则库加载被访问的规则(rule),工作空间加载规划问题的问题事实(fact),匹配引擎推动规则匹配器(pattern matcher)和执行管理(agenda)的运行。Drools 采用的模式匹配算法有Rete 和Leaps 等,Rete-OO 算法是对Rete 算法的加强和优化[20]。Drools 规则引擎推理步骤如下。
(1)分别将规则和问题事实加载到规则库和工作空间中。
(2)通过规则匹配器比较规则和泛化问题事实,检验匹配性。
(3)若检验结果无规则冲突,将激活规则放入执行管理器,若有冲突,将冲突规则放入冲突区。
(4)解决冲突规则区的问题,再将激活规则放入执行管理器。
(5)运行执行管理器中激活的规则。
(6)重复步骤(2)～(5)直到没有规则与约束匹配。
具体规则约束匹配表现如图4 所示。
图4 Drools 约束匹配
其中RULE
3.2 三级评分模型
问题事实的解决方案不可避免地违反所建立的约束,Drools 规则引擎需结合评分模型量化表示解的优劣情况。通过计算解的评分,判断解的优劣。
评分模型一般为两级评分模型,软硬约束分别对应软硬分,硬分数表明方案是否可行,软分数则表明方案的优劣。本文中采用三级评分模型,引入中等约束的性质,中等约束与所求的目标函数相关,见式(1)、(2)。软约束为相对不重要的要求,见式(5)～(7)。硬约束为必须满足的基本约束见式(3)、(4)。通过引入中等约束的性质以区分约束的重要程度,并更加直观地表示出目标函数的满足情况。
各约束分别匹配解决方案时,触发规则后,
3.3 邻域搜索求解
适应度计算方式确认后即可通过智能优化算法搜索寻优。本文针对钣金排程问题拟采用局部搜索法进行求解,算法相关规则及步骤如下。
(1)随机选择初始可行解x0∈D,xb=x0,P=N(xb)。
(2)选择邻域P 的一个子集P′,计算子集各解的得分,xn为其中最优解。
(3)如果xn得分较原有xb大,则有xb=xn,P=N(xn),否则P=P -P′。
(4)判断是否满足终止条件,满足则寻优结束,输出最优结果,否则执行步骤(2)。
其中D 为钣金排程问题中的可行解域,P 为当前最优可行解的邻域,所有可选择的元素皆为可行解。用结合评分模型的Drools 规则引擎对所选解进行得分计算。由于快速形成生产计划是需求,故算法中引入时间元素,以10 s 时间为终止条件。邻域动作则为对某个任务进行生产设备或开始加工时间上的移动。最后通过该方法对钣金排程问题进行搜索寻优。
4 柔性化钣金产线排程实例
以某安防门生产线为例,该生产线是柔性落料折弯钣金产线,用于门板自动折弯成型,是集成料库、单张取料、CCD 识别、激光切割、打码、数控转塔冲床、长边折弯、短边折边、堆垛为一体的自动化加工生产线。在柔性化钣金产线排程中,包括成本单价信息、生产线信息以及订单信息。根据钣金实际生产状况,信息部分内容拟定分别如表1、2、3 所示。
成本单价信息以人工成本为例,表示可选时间段内所有时间的人工成本单价。本例中可选时间段为288 h,各时刻的单价如表1 所示。
表1 成本单价信息
拟定生产线由3 条相同的钣金生产线组成,可加工5 种不同类型的产品,生产线信息包括工作功耗、启动功耗、停止功耗及物种产品可生产容量等,部分参数如表2 所示,大小为功耗的量化表示。
表2 生产线信息
拟定任务有50 个订单,订单信息包括订单序号、生产所需总时长、订期、交期、任务功耗等,部分参数如表3 所示。
表3 订单信息
根据上述问题事实采用所提出的优化排程方法求解得出的最优方案甘特图如图5 所示,其中横、纵轴分别表示时间、订单序号,不同图标表示不同加工生产线。从生产排程的甘特图结果可以看出,50 个订单任务生产计划全在对应要求的定期和交期之间,满足生产时间要求。排程优化求解时间在6 s内达到稳定,满足及时性要求。
图5 排程结果甘特图
约束匹配得分情况如表4、5 所示,从得分结果和得分明细中可以看出,硬分数为0,没有生产线加工容量不足的情况,方案可行;尽早生产约束得分次数为50 次,50 个订单均有开始时间,符合实际情况;中等分数中启停次数为24,小于订单数50,符合优化方向。
表4 得分结果
邻域搜索法的搜索寻优过程如图6 所示,分别表示中等分数和软分数的优化过程。由于本例中以中等约束作为优化目标,故寻优过程应以中等分数的优化为主,由图6 可得,搜索路径迅速收敛。
表5 得分明细
图6 搜索优化过程
5 结论
本文针对钣金加工订单呈现多品种、小批量离散化特征的问题,研究了柔性化钣金产线的生产排程优化方法。引入Drools 规则引擎,以在交货日期前完成生产为基本约束,以最小化成本及设备损耗为主要目标,依据实际生产状况建立了包括尽早生产的三级生产约束并进行了数学模型表达。研究规划问题三要素,结合Drools 规则引擎和邻域搜索法形成优化排程方法。通过实例的运行对方法的有效性进行了验证,结果表明,订单按期交货率达到100%,并且符合实际寻优方向。
通过对优化排程方法有效性的验证表明,本文所提出的方法对现代柔性化钣金产线的生产排程要求有较好的满足情况,可发挥出柔性化产线的产能优势。本文所提出的基于Drools 规则引擎匹配约束的寻优求解方式对于同类型的问题也提供了新的思路。
未来研究可以引入不同算法对比,还可通过在柔性化钣金产线上的实际运行,考虑突发干扰事件的影响。
