基于优先调度规则实时选择模型解决加工车间调度问题

□ 王 磊 □ 张 贺 □ 刘 毅 □ 石 刚

宁波吉利罗佑发动机零部件有限公司 浙江宁波 315336

随着制造业的高速发展,市场对产品的个性化要求越来越高,需要解决在快速变化的市场环境下小批量、定制化需求和复杂多变的内外部因素等问题。挖掘制造企业产能是解决上述问题的有效方式。影响产能的因素有很多,其中包括工艺规划的合理性、生产调度的合理性等。生产调度是影响生产的重要因素,合理的生产调度能保证生产过程高效有序地运行,激发企业的生产潜力。为有效保证生产调度的最优化,需要将传统的生产调度方式与新一代的信息技术进行融合,使生产调度过程更具准确性、柔性化。

在优化生产调度策略时,需要考虑的参数众多,且具有动态性,在理论研究和实际应用上都具有复杂性。在学术界,根据调度的复杂度不同,形成许多优化调度问题的方法,主要分为四类。第一,预留调度时间的优化方法。预留出因为设备故障而影响调度的时间,该方法能够很好地解决因意外而导致调度调整的问题,且具有很强的鲁棒性,但是因设备故障具有不确定性,容易导致预留时间的准确性较低。第二,基于优先调度规则的方法。诸多文献证明,多个优先调度规则的联合使用,根据生产状况的变化不断切换,要比单个优先调度规则在整个生产范围内表现出更好的性能,在生产过程标准化程度高的企业表现得更好。第三,仿真方法。能在较短的时间内呈现出未来生产过程和得出结果,但是无法实时改变生产工艺流程,且解决调度问题方法不一,优选过程工作量巨大。第四,生产调度问题优化建模及算法。在实际生产中,存在诸多限制,以一个或多个目标构建数学模型后,用尽可能优的算法以尽量短的时间得出尽可能优的解,问题针对性高,解决能力强,但在高随机性和动态性的生产环境下,自适应和自学习能力差,易导致解决问题的滞后性。

笔者以生产的标准化、信息化为基础,为降低生产调度问题的复杂性和解决问题的滞后性,构造出一个能实时为每个设备选择优先调度规则的系统,以最小化完工时间、最小化延迟时间、最小化完工时间和延迟时间之和为目标。当生产能力满足时,优化设备利用率。当生产能力不足时,优化设备利用率和减少订单上产品的延迟时间。对此,笔者首先利用仿真工具找出各个目标下应该施加给设备上的优先调度规则组合,然后从获取的数据组合中提取知识,构建模型,最后检验该模型的适应性。

加工车间生产调度过程是极其复杂的,有文献总结得出在每个设备上具有α个操作的β个设备和γ个工件的加工车间中将可能出现(βα×α！)j×(j!)个加工序列。如果α=β=γ=2,将可能出现256个加工序列,如果α=β=γ=3,将可能出现91 833 048个加工序列,即随着α、β、γ的增加,加工车间调度的复杂度将呈现爆炸式增长。

笔者主要考虑优化加工车间调度问题,把生产能力足够和生产能力不足的情况分开研究。对于定制化、多品种小批量生产方式的企业,订单到达率高且订单中包含多种类别的产品,面对这些工艺流程、加工时间不一的产品,如何在生产能力足够的情况下保证该订单上所有类别产品的完工时间,在生产能力不足的情况下降低订单延迟时间,已成为优化生产资源配置、最大满足客户需求的重中之中。订单中产品最小化完工时间Tmin为:

(1)

式(1)确保了生产资源的最高利用率。如生产能力不足,订单中产品最小化延迟时间Qmin为:

(2)

式(2)能最大化减少订单延迟时间。最小化订单上产品完工时间和延迟时间之和Cmin为:

(3)

式(3)既能优化生产资源配置,又能最大化满足客户需求。Tij为产品i在设备j上的加工时间,i=1,2,3,…,m,j=1,2,3,…,n,Di为第i产品的交货期。

方法研究主要分为三个步骤。

(1) 以单类型产品的批量为单位,借助仿真工具针对每一设备使用不同调度规则,寻找出同一类别中产品最小化延迟时间、最小化完工时间、最小化产品延迟时间和完工时间之和的优先调度规则组合。

(2) 避免对比所有调度规则组合的情况,找出同类别产品的最优调度组合,基于步骤(1)收集到的数据,使用数据挖掘技术提取数据,寻找出每一个设备的最优调度规则。

(3) 实际生产中,订单依据客户需求的紧急程度可分为紧急订单和普通订单两种,合理安排这两种订单,最大化地满足客户需求。

笔者提出的方法分为仿真模块、学习模块和应用模块。仿真模块满足数据要求,学习模块创造出调度规则选择的模型,应用模块满足处理新订单的需求,验证在实际生产过程中模型运用的效果。

使用机器学习算法对数据进行分析。总模块架构如图1所示。

▲图1 总模块架构

(1) 对原始数据库的产品进行分类,划分的依据为各产品在工序上的加工时间、开始加工前的创建时间、工艺流程、该类别中产品的总数。

(2) 从优先调度规则库中选出一个或多个调度规则,确定设备前将要加工的产品的加工队列。

(3) 计算出优先调度规则下的该类别下所有产品在某设备下的完工时间、延迟时间、完工时间与延迟时间之和,并以最小化为目标选出最优的优先调度规则组合。

(4) 将该类别相关数据与其最终确定的最优优先调度规则组合联系起来存入标签数据库中,以备知识提取时使用。

▲图2 标签数据库生成

随机选取的样本数据见表1。Ti为第i类产品的加工时间,Fi为第i类产品的加工数量,Ei为第i类产品的交货期,DR1、DR2、DR3表示事先构建好的调度规则1、调度规则2、调度规则3。

表1 部分样本数据表

以随机森林分类器为例,预测效果统计见表2。训练样本和测试样本同为表1样本,其中P列对训练集预测出的结果,R列为预测结果的置信度,与表1实际最优调度规则相比,表现出较好的性能。

表2 预测效果统计

选取最优完工时间与延迟时间之和对应的优先调度规则与最优完工时间或最优延迟时间所对应的规则不一样的样本,Tmin对应的优先调度规则与保证Qmin和Cmin的优先调度规则效果差距很小,甚至持平,表明同时考虑完工时间和延迟时间所使用的调度规则既能较好保证优化产品延迟时间,又能保证优化产品总加工时间。Tmin与Qmin+Cmin对比如图3所示。

▲图3 Tmin与Qmin+Cmin对比▲图4 模型应用过程

在实际生产过程中,依照客户对交货期的需求,管理人员依照车间制造能力将新到达订单分为普通订单和紧急订单,然后利用已构建好的模型,确定该订单生产过程所经过设备的优先调度规则。模型应用过程如图4所示,数据库包含所有类别下属性。

当产品总交货时间大于产品实际加工时间时,说明车间生产能力足够,按照以最优化产品完工时间为目标构建的模型2去指派优先调度规则,以优化源配置,提高生产效率。当产品总交货时间小于产品实际加工时间时,说明生产能力不足,按照以最优化产品完工时间与延迟时间之和为目标构建的模型1去指派优先调度规则,以达到最小化订单的交货延迟的目的。

为了验证以上结果,笔者首先使用仿真工具找出每个目标最优化下每个设备所对应的优先调度规则,把优先调度规则分为两类。一类是单个优先调度规则,如先进先出原则、最短生产时间规则等。另一类是混合优先调度规则,如产品经过所有设备的总加工时间与最短路径树混合、产品的总剩余工作时间与产品在设备上的处理时间混合等。

所提出的混合优先调度规则所对应的参数则为产品在设备上的处理时间、产品经过所有设备的总加工时间、产品的总剩余工作时间、产品的交货期两两混合,表达式为:

Z=PijGij

(4)

式中:Pij为第i个工件在第j个设备上加工时的具体参数值;Gij为第i个工件在第j个设备上加工时的具体参数值。

110株可育大豆ms1轮回群体核心种质的单株产量在2.13～29.05 g，其中，单株产量超过区域试验对照品种黔豆7号(13.38 g)的有23株，占20.91%；
超过地方品种铜科豆2号(12.78 g)的有24株，占21.82%。说明，大豆ms1轮回群体核心种质对本地区的大豆高产育种具有利用潜力。

以上选取的优先调度规则都以参数值从小到大或从大到小确定队列中作业的加工优先级。

试验所考虑的问题是Lenstra提出的经典的四台设备车间调度问题,该问题一直被广泛地探讨和研究。针对提出的四台设备车间调度问题,提出以下假设:① 单个设备一次只能连续处理一个工件;② 设备故障时间和工件在设备与设备之间的运送时间不予考虑。

基于文献生成数据的方法,随机生成100个类别的产品,以各产品在工序上的加工时间、开始加工前的创建时间、工艺流程、该类别中产品的总数来划分类别。每个类别下产品数量服从[10,50]的随机分布,产品加工时间服从[20,400]的随机分布,并用工序上加工时间0表示未经过该工序,该产品的交货期以产品的瓶颈工序加工时间为均值、方差为20的正态分布。部分生成样本数据见表3。Ji为设备,每个类别包含多种产品,每个类别的设备加工时间为该类别下所有产品在该设备加工的时间,数量为该类别下产品数量的总和,交货期为该类别对应订单的交货期。

表3 部分样本数据

在实际生产中,虽然经过仿真能为每个类别的产品在加工过程中优选出优先调度规则组合,但是以笔者选取的22个优先调度规则和四台设备交货期,需要仿真的次数为23 425次,这是极其庞大的工作量。为解决此问题,构建一个能快速选择优先调度规则的模型是十分必要的。结合仿真结果,很明显是一个多标签分类问题,在使用各类分类器以时间成本和准确率构建模型时,发现决策树分类器和随机森林分类器效果较好。决策树分类器如图5所示。

▲图5 决策树分类器

决策树分类器中每个节点表示要分类的样本中的特征,每个分支表示节点可以采用的值。实例从根节点开始进行分类,并根据其特征值的重要程度进行排序,A1、A2、A3为三个属性,a、b、c为属性值,PDRi为最优调度规则。

随机森林训练预测流程如图6所示。把整个数据集D划分为训练集和测试集,训练集数据为数据集的子集。训练集包括多个子集,由决策树对这些子集分别训练学习,形成多个决策树,即多个规则。测试数据中的测试样本按照多个规则进行学习,每一规则会使该测试样本分到一类中,对划分到的类进行计数,统计次数,最后得到最大的和的对应类就是该测试样本的最终预测结果。

▲图6 随机森林训练预测流程

模型构建时,将训练集和测试集划分为7∶3对模型进行训练验证。使用五次交叉验证,以正确率和时间为指标。使用随机森林分类器和决策树分类器的分类结果见表4、表5、表6。

表4 Tmin为目标分类结果

表5 Qmin为目标分类结果

表6 Cmin为目标分类结果

由表4、表5、表6可知,在正确率上,随机森林分类器表现出更好的效果,但是模型构建的时间则较长。如果允许模型更新间隔时间较长,选用随机森林分类器效果更佳。但是如果模型更新间隔时间要求短,为了保证模型适应性的滞后性低,选用决策树分类器效果更佳。分类器的良好选择对模型依靠生产环境的不断变化进行实时更新具有重要意义。

笔者选取单个优先调度规则和混合优先调度规则,联合使用仿真技术和数据挖掘技术构建了一个能实时且高效的为设备指派优先调度规则的模型,消除了使用单纯的使用仿真技术优选优先调度规则工作量大的弊端,减轻了解决车间调度问题的复杂性,并且对研究比在多项式复杂度内被验证问题更困难解决的问题具有重要意义。

相比于前人的研究,优化了产品最小化完工时间和产品的延迟时间,进一步挖掘了制造车间的生产能力,解决了在生产力不足时同时进行多订单生产情况下,既能优化产品完工时间,又能优化产品交付延迟时间的双目标问题,更高质量地满足客户的需求。

猜你喜欢 延迟时间分类器优先 二氧化碳对乙烷燃烧着火延迟时间的影响煤气与热力(2021年3期)2021-06-09添加非平衡等离子体对甲烷着火性能的影响沈阳航空航天大学学报(2021年1期)2021-03-18LTE 系统下行链路FDRX 节能机制研究湖南邮电职业技术学院学报(2020年3期)2020-10-1340年，教育优先商周刊(2018年25期)2019-01-08多端传播，何者优先?传媒评论(2018年5期)2018-07-09基于差异性测度的遥感自适应分类器选择电子技术与软件工程(2017年14期)2017-09-08基于实例的强分类器快速集成方法计算机应用(2017年4期)2017-06-27站在“健康优先”的风口上中国卫生(2016年12期)2016-11-23延迟时间对气辅注射成型气体穿透行为影响的数值模拟和实验研究中国塑料(2016年8期)2016-06-27基于层次化分类器的遥感图像飞机目标检测航天返回与遥感(2014年5期)2014-07-31

推荐访问:调度 车间 实时