文章快速检索  
  高级检索
面向机床状态波动的调度模型
孟飙1, 赵志刚2, 高建丽3     
1. 沈阳航空航天大学航空制造工艺数字化国防重点学科实验室, 沈阳 110136;
2. 金航数码科技有限责任公司, 北京 100028;
3. 武汉高德红外股份有限公司, 武汉 430000
摘要: 为提高作业计划对机床状态的自适应力,建立了质量数据驱动的作业车间计划调度模型.首先挖掘隐藏在质量数据中的关联规则,基于专家领域知识和关联分析结果,获得机床状态波动信息;构造基于损失时间函数的全局调度性能指标,实现机床状态波动对调度模型的循环优化调节,提高小时间尺度调度方案的可行性;并通过对比某制造企业的调度方案和机床状态变化时的调整方案,验证了调度模型的有效性.
关键词: 作业车间调度问题(JSSP)     数据挖掘     机床状态波动     遗传算法    
Job-shop Scheduling Model for Machine State Fluctuations
MENG Biao1, ZHAO Zhigang2, GAO Jianli3     
1. Key Laboratory of Fundamental Science for National Defense of Aeronautical Digital Manufacturing Process, Shenyang Aerospace University, Shenyang 110136, China;
2. AVIC Information Technology Co., Ltd., Beijing 100028, China;
3. Guide Infrared Group, Wuhan 430000, China
Abstract: To improve the adaptability of the work plan to the machine state, in this study, we establish a job-shop scheduling model driven by quality data. To do so, we first use expert domain knowledge and relevancy analysis to mine the association rules hidden in the quality data and identify the machine-state fluctuations. Then, we construct a global scheduling performance indicator based on the loss time function to enable the scheduling model to make cycle optimization adjustments in response to machine-state fluctuations and to ensure the feasibility of the small-time-scale scheduling scheme. Finally, we verifie the effectiveness of the model by successfully changing the scheduling in a manufacturing enterprise in response to changes in the machine state.
Keywords: job shop scheduling problem(JSSP)     data ming     machine state fluctuation     genetic algorithm    

0 引言

作业车间调度是生产管理中的关键工作.现阶段制造企业大多采用订单式生产模式,生产方式呈现“多品种、小批量、短周期”的特点.不同工艺的产品混排、频繁换线、交货期紧张等情况对生产管理提出了更大的挑战[1],同时对生产过程调度的可执行性、对动态环境的响应等方面提出了更高的要求.

通过数据挖掘获取小时间尺度内的实际生产环境状态,基于生产环境状态进行调度能够提高调度方案的可用性.数据驱动的调度模型调整相较于基于模型和基于知识的优化算法在提高调度方案可用性方面具有较大的优势,吸引了广大学者的研究和应用[1].

文[1-3]对基于数据的复杂制造过程调度方法的相关理论、方法和应用做了系统地阐述和展望. Zhang[4]和Nasiri[5]等从仿真数据中使用不同算法挖掘优先调度规则,提高了调度模型对动态生产环境的响应能力.张晶等[6]面向信息物理系统准确获得了任务的发生时间,保证了系统调度任务的准确性. Jongsawas等[7]通过RFID采集生产现场数据,从而发现生产过程中的延迟或者中断,基于这些可视化的信息对作业计划进行调整.朱雪初等[8]建立了基于支持向量回归方法的加工时间预测模型,并基于MES系统制造数据驱动对半导体制造仿真模型中的动态参数进行预测.龙田等[9]设计了免疫算法能够选出适应动态环境下的作业车间的调度规则以适应多目标调度.汤洪涛等[10]针对不同扰动对调度相关历史工业大数据进行聚类,通过改进随机森林算法从聚类后的每个簇中得到不同的调度规则,通过切换不用的调度规则提高系统对扰动的实时响应能力.

数据驱动的生产过程调度已取得一些成果,但仍存在很多不足.在数据获取方面,用于数据挖掘的信息往往是与调度直接相关的数据(调度模型的输入和输出数据),间接相关的数据很少涉及,但是企业积累的历史数据中以间接数据为主;在模型关键参数预测方面,往往着眼于某一项基础数据,未能对多方面的信息加以综合考虑,一些预测结果也未直接应用于作业调度模型中,使得预测模型和作业调度模型完全分离,未能实现良好的应用效果;在数据建模和迭代优化方面,调度规则挖掘及算法的研究比较热门,对于机床状态挖掘方面尚未成熟应用.

在作业车间调度过程中考虑机床的实际加工能力和机床状态需要解决两个问题:一是挖掘实际机床状态,二是将动态的机床状态添加到作业调度模型中.本文参照吴启迪[3]提出的基于数据的复杂制造过程调度架构,提出了解决面向机床状态波动的作业调度架构(如图 1所示).一方面借助仿真技术、机器学习等技术,在大量离线数据和仿真数据的基础上提炼出知识、经验和规则,为调度决策提供准确的参数条件和决策策略;另一方面,通过实时采集的在线数据,批量地对采集的数据进行清洗与挖掘,对挖掘结果进行评价决策,跟踪当前机床的加工能力和加工状态,驱动调度模型的调整,保证小时间尺度调度方案的可行性和有效性.

图 1 面向机床状态波动的作业调度架构 Fig.1 Job scheduling architecture for machine state fluctuations
1 作业车间调度问题模型

作业车间调度问题(JSSP)解决的是n个零件(工艺不同)在m台机床上加工的调度问题,约束条件参见文[11].以机床状态波动下的最大完工时间(makespan-LT)最小为目标函数,建立数学模型:

其中,cijk表示第i个工件的第k道工序在机床j上的完工时间;LT(Xj)表示在机床j上加工可能产生的损失时间(定义及求解过程在2.2小节中阐述),Xj为机床j的可用性;max{ci+LT(Xj)}表示工件i的最大完成时间,工件的加工工序在机床上的不同的排序导致了不同的最大完成时间,即求解JSSP问题的本质就是排序的确定[12]. makespan-LT作为全局调度性能指标用于评价调度方案性能和指导算法寻优过程.

2 数据驱动的作业车间调度模型

忽略机床的不良状态(刀具磨损、电压不稳定、设备老化等)及机床动态信息(正常可用、停机故障、维修保养等)会造成计划的执行性差.数据驱动机床状态更新并不断调整作业调度模型,对于提高生产计划的可用性具有重大的意义.

探索基于动态环境的车间模型需要大量实时数据的支持,但是“多品种、少批量”的生产模式下加工件的数量很少,收集到数据(与具体产品关联)往往达不到传统统计方法的规模要求,因此本文采用的数据为企业历史数据中比较完善、数据量较大的质量数据和通过仿真实验得到的数据,建立了数据驱动的作业车间调度模型.模型主要包括:质量数据关联规则挖掘(2.1小节)、基于仿真实验的损失时间函数(2.2小节)、机床状态动态控制策略(2.3小节)、生产计划的编制(2.4小节).

模型通过对批量质量数据的深度挖掘获得机床一段时间内的状态,基于控制策略驱动调度模型进行调整,实现基于实际机床状态的车间生产计划编制及数据驱动的再调度.模型各个部分的关系如图 2所示.对质量数据的挖掘主要是为了获得能够反映机床实际加工状态的重要指标;基于仿真实验的损失时间函数部分主要探讨了损失时间函数求解过程,损失时间函数是沟通质量数据挖掘模型和生产调度模型的桥梁;最后基于makespan-LT指标进行计划的编制和再调度,调度过程充分考虑了机床状态波动的影响.

图 2 调度模型 Fig.2 Scheduling model
2.1 质量数据关联规则挖掘

机床实际加工状态和加工能力受到多方面因素的影响,单方面研究某一因素的影响得到的结果可能片面,可信度低.对机床状态的综合评估可以从机床的产出角度进行考虑,机床产出产品质量更高,则表示机床拥有更好的状态,也可以理解为机床的理论能力可用性更高.依据制造企业数据系统中实际数据,采用某时间间隔内(中间无停机故障、无维修保养)的所有订单信息及质量信息进行数据挖掘.使用FP-Grown挖掘算法挖掘频繁项集和生成规则发现机床状态与产品质量之间的关联关系,基于专家领域知识和关联分析结果,获得机床状态波动信息.

2.1.1 基于关联规则挖掘质量特征联系

机床状态往往影响着产品的质量,对“人机料法环测”等多维度的质量数据进行分析,本文以设备的唯一编码作为事务的识别,将机床和人员作为同一特征考虑,排除物料、方法、环境等的影响,对不同状态下的机床和产品质量之间的关系进行挖掘.

数据库D={t1t2,…,tn}中存储着所有的事务;事务是指某一订单相关的信息,事务项表示为t={ID1,ID2,…,IDkq},其中ID表示某一批产品使用的机床编码,q表示为某批次产品的质量. ID和q在FP-Growth算法中均表示一个项目.某批次产品的工艺路线为M=(机床MID),其中MID∈{ID1,ID2,ID3,…,IDn};某批次产品质量为Q′=(产品的合格品率q),q∈R;M×Q′的组合能够表示所有的事务项可能.采用FP-Growth算法进行关联规则的挖掘,先将数据库中的事务项数据以频繁模式树(FP-Tree)的形式表示,然后从FP-Tree中获得频繁项集,最后利用统计的方法将频繁项集转化为某种关联规则R[13].

设工艺路线中设备的数目为n,产品的合格率为j,则事务的维度为n×j,可能的事务项有2n×j-1种.因为j∈R,所以事务项的数目是无穷大的,无法进行求解频繁项集.常用的处理方法是对产品质量进行分级,降低事务项维度使得问题可解[14].本文对企业管理知识中对某产品种类的期望合格品率进行提取,将实际合格品率与期望合格品率进行比较得到损失质量Q(Q也可以理解为不合格批次),Q=0代表实际合格品率大于等于期望合格品率,Q=1代表实际合格品率小于期望合格品率.同时依据企业实际机床数目,令n=5,则事务维度为10,事务可能性为210-1种.

对选取的数据进行分析前进行结构化处理,方便算法的理解和使用.订单批次表示为J-MID-q-qB表示,其中,J代表订单编号;MID代表加工路线中机床编号;q代表合格品率;qB表示期望合格品率.

2.1.2 关联结果分析

挖掘关联规则RMQ,即机床M与损失质量Q之间的关系.本文从项目项支持、概率表示等多个维度对关联结果的指标进行表示[15].其中EM表示包含项目M的事务组成的事件(数据库中一条实例);式(1)中P(EM)表示项目M的事务项在数据库D中所占的比例;式(2)中P(EMEQ)表示同时包含项目M和项目Q的事务在数据库中所占的比例.为表达简洁,用P(M)代替P(EM),用P(MQ)来代替P(EMEQ);支持度(式(2))和置信度(式(3))通常用来筛选频繁项集,从而产生规则;覆盖率(式(4))表示包含机床M的事务数所占的比例;提升度(式(5))、杠杆率(式(6))、确性度(式(7))[16]、强度(式(8))均可从不同角度刻画机床M与不合格批次Q的相关性.

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
2.2 基于仿真实验的损失时间函数

工件的实际加工时间和机床的状态有着很重要的关系,机床处于不良状态(可用性降低)最终对生产计划造成的影响是订单实际加工时间加长,损失时间函数(loss-time function)就是用来定量描述这一机制的.损失时间函数是makespan-LT调度目标的核心,是数据挖掘模型和生产调度模型的桥梁.下面通过仿真实验和广义线性回归的方法探索损失函数的表达形式.仿真数据驱动的机器学习系统主要分4个阶段进行:提出问题,数据收集及预处理,模型训练及评估,知识形成.

2.2.1 损失时间定义

实际生产中加工设备均可能发生故障,一般而言,两次故障间的时间间隔符合指数分布,故障平均修复时间(mean time to restoration,MTTR)符合爱尔朗分布[12],也可以用设备可利用率(availability)表示.本文提出并定义了损失时间(loss time)来描述机床的综合状态,损失时间是指由于设备不良状态等造成的零件加工时间延长或者是不合格件所对应的时间成本损失,数值上为实际加工产品所用的时间与理论加工合格产品所用的时间的差值.

影响损失时间的因素包括机床状态和工件加工时间.物理模型中的机床状态通过设备可用性和故障平均修复时间表示,工件加工时间用额定工时表示.

2.2.2 数据收集及预处理

如果探讨多个输入与输出间的关系,一次改变一个变量的模型是无法获得多参数间的联动作用的影响,而实验设计方法(design of experiments,DOE)可以方便地获得多个输入如何共同对输出产生影响,能够获得反映损失时间与其它因素关系的数据,从而通过学习获得损失函数的重要参数.

1) 实验模型设计及数据收集.使用PlantSimulation提供的DOE工具建立如图 3所示的DOE实验模型模型,设置Source与Drain的处理时间为0,工件离开Drain时执行方法CalOutput,方法CalOutput的功能是获得工件实际加工时间和理论加工时间的差值,方法Set_Vars用来设置模型中M1对象的参数.重复实验次数10次,置信度水平为95%.

图 3 DOE模型 Fig.3 DOE model

2) 数据可视化及分析.从图 4的散点图中可以发现数据的特征和变化规律.由图 4(a)易知,损失时间大致随可用性的提高逐步减小;由图 4(b)易知,损失时间随着MTTR的增加而增加但MTTR对损失时间的影响不大;图 4(c)直观地表现了设备可用性、MTTR、损失时间之间的总体关系趋势.

图 4 散点图 Fig.4 Scatter plot

图 5为DOE2的两因子方差分析(因子分析)报告,在因子分析矩阵中,H代表因子主效应(因子从较低水平移动到较高水平造成目标值变化的均值),W表示交互效应(两因子同时从较低水平移动到较高水平造成目标变化的均值),H1≫H2,说明设备可用性的影响比平均故障修复时间(MTTR)的影响要显著的多,所以通过拟合设备可用性和损失时间的函数关系来探索机床状态对损失函数的影响.

图 5 方差分析矩阵 Fig.5 Factorial analysis

通过DOE3探究损失时间与零件额定工时之间的关系.从图 4(d)可以发现,相关性系数r=1,说明损失时间与额定工时是线性相关的.

综上所述,在加工时间不变的基础上,探索损失时间和设备可用性的函数关系,然后依据额定工时与假定工时的比例关系,可以得到损失时间的函数表达式.

2.2.3 模型训练及评估

图 4(a)散点图推断,损失时间(Y)和设备可用性(X)之间符合幂律分布规律[17].假设:

本文为拟合幂律分布函数设计了算法模型:给定数据集T={(X1Y1),(X2Y2),…,(XNYN)},N为训练集中的实例的个数,(XiYi)代表第i个实例.

θ=[θ0θ1]T,计算:

求解:

最终学习得到模型:

即求得幂律分布函数:

(9)

利用上述算法模型对DOE0的实验数据进行训练,对原始数据取不同的对数时得到如表 1结果,依据残差平方和最小的原则,采用log(X)的计算策略,对其进行线性拟合,得到如图 6(a)的拟合直线.由拟合图 6(a)可知,数据有明显的离群点,所以先去掉下垂的头部和弥散的尾部,再对数据进行进行线性拟合,得出图 6(b)的拟合直线.由表 1中lg(X)(图 6(a))与lg(X)(图 6(b))列数据比较可知,去除离群点后的曲线残差平方和更小,所以拟合效果更好.将θ1*=-1.565 906 89,θ0*=7.049 111 97代入到式(9)可以得到损失时间(Y)和设备可用性(X)之间的拟合方程为

表 1 函数拟合参数 Tab.1 Function fitting parameters
策略 lb(X) ln(X) lg(X)(图 6(a)) lg(X)(图 6(b))
残差平方和 1.360 532 56 0.653 671 97 0.123 290 18 0.011 933 93
θ1*(系数) -1.665 895 73 -1.665 895 73 -1.665 895 73 -1.565 906 89
θ0*(截距) 23.558 726 60 16.329 664 92 7.091 883 37 7.049 111 97
注:残差平方和
图 6 设备可用性与损失时间关系拟合 Fig.6 Fitting of availability and loss time
2.2.4 损失时间函数

基于2.2.3小节损失时间Y的表达式,定义损失时间函数:

其中,LT表示损失时间(单位为s),X为机床可用性(单位%),α表示主成分系数(α∈[0, 1]),T表示额定工时(单位为min),Y表示总处理时间为500 min前提下的损失时间(500 min大约为8 h).

2.3 机床状态动态控制策略

企业最终核实成本往往都是按照工时长短进行计算,不同的产品质量可以用不同的时间来进行核算,产品不合格率越高,时间成本越大.如果某一机床与产品质量不合格率关联性大,实际业务场景中可能是该机床状态不良,从而带来质量波动,也可以解释为在机床上加工产品所需要的工时比额定工时要长.所以,可以定性地认为在关联规则、机床的可用性与实际加工时间之间存在着确定的趋势:关联性越大,机床的可用性越低(机床状态不良),实际加工时间就会越长.基于时间成本核算,关联性指标和机床可用性之间存在映射关系.

将机床M与损失时间Q的相关程度划分为:不相关、弱相关、中等相关、强相关.使用杠杆率lev(R)的大小衡量相关程度,定义-1≤lev(R)≤0.03表示XY为不相关;0.03 < lev(R)≤0.1表示XY为弱相关;0.1 < lev(R)≤0.5表示XY中等相关;0.5 < lev(R)≤1表示XY强相关.基于对加工时间相似的影响效果,用离散的机床可用性映射相关性指标lev(R),得到如图 7的映射矩阵.

图 7 映射矩阵 Fig.7 Mapping matrix

对实时数据进行监控,设置触发式控制策略:如果发生停机故障,则可用性变为0;如果正在进行保养维修,则可用性变为0;保养维修结束,则可用性变为100;每隔一段时间获取最近时间段内(不包含可用性为0的时间间隔)的质量数据进行数据挖掘,挖掘得到指标Lev(R)的值,通过映射矩阵获得当前机床可用性.

根据获得的可用性对当前调度计划进行调整,调整策略为:机床可用性不变,则调度计划不发生改变;如果可用性发生改变,当前加工的零件继续加工完成,后续加工计划执行调整后的调度计划.

2.4 生产计划编制

建立作业车间仿真模型和基于遗传算法的车间作业调度模型.使用机床状态驱动调度模型进行计划编制和再调度过程,保证小时间尺度调度方案的可行性.遗传算法基本组成包括[12]:基于加工工序序列的遗传编码与解码;创建初始种群;根据个体适应度值对其进行优劣判定的评价函数(适应度函数);用来搜索可行解的遗传操作(选择算子、交叉算子、变异算子);遗传算法的参数值(种群大小M、交叉概率Pc、变异概率Pm和种群代数T).

2.4.1 遗传算法构建过程

1) 编码

基于工序表达法的JSSP问题求解[11]以各工件的加工工序序列作为遗传编码,对于n×m调度问题对应的染色体长度为n×m,每个基因代表一个工序,但不代表具体的某一工序,需要通过上下文解码才能确定具体的工序.每个作业在染色体中出现恰好n次,第j次出现表示该作业的第j道工序.考虑到现实情况下可能各工件的加工工序数量不一定等于机床数,所以同时引入基于工序总数的自然数顺序编码,以表 2中3×3调度问题[11]为例,每个工件有3道序,染色体的长度为3×3=9,则基因值的范围为0~9.基于工序总数的整数编码直接代表加工工序.如果得到基于工序总数的编码为[5 6 4 3 7 8 9 2 1],按照映射关系,对应的基于工序表达法的编码为[2 2 2 1 3 3 3 1 1].采用这样的映射主要是因为可以采用通用遗传算法和通用交叉算法[12].

表 2 3×3 JSSP Tab.2 3×3 JSSP
工件 工序
加工时间 设备顺序
1 2 3 1 2 3
J1 3 3 2 M1 M2 M3
J2 1 5 3 M1 M3 M2
J3 3 2 3 M2 M1 M3

2) 解码

操作οijk表示工件i的第j工序在机床k上加工,可行解[2 2 2 1 3 3 3 1 1]的解码结果为[ο211 ο223 ο232 ο111 ο312 ο321 ο333 ο122 ο133].

3) 初始种群的生成

初次排产时,初始种群通过依次读取订单中的工序获得,编码为[1 1 1 2 2 2 3 3 3],对应得工序总数编码为[1 2 3 4 5 6 7 8 9].

4) 评价及选择

为提高作业车间调度计划对动态环境的自适应力,调度方案性能指标采用makespan-LT指标.目标函数f的计算表达式为

f的值越小,说明调度方案的性能越好. makespan-LT指标作用机理如图 8所示.假设机床的某时间段检测到机床2可用性低,通过损失时间函数LT计算得到损失时间为1 s,执行到机床2上的任务时会进行时间松弛的操作,即通过损失时间函数添加由于机床状态不良带来的时间延长.

图 8 makespan-LT指标作用机理 Fig.8 The mechanism of the makespan-LT

5) 遗传算子

交叉算子采用部分映射交叉算子.变异算子选择随机变异算子,即在染色体中随机选取两个基因,以概率Pm进行交换,得到新的子代.

6) 终止条件

重复步骤4)和步骤5),直到算法迭代次数达到给定的种群代数N为止.

2.4.2 构建仿真模型

基于Tecnomatix Plant Simulation 14建立了如图 9(b)的JSSP问题求解模型,并在图 9(a)中将模型中的方法和对象与解决思路的流程图进行一一对应.

图 9 作业车间生产排程仿真 Fig.9 JSSP simulation model
3 模型验证与分析

面向机床状态波动的作业车间调度模型解决了两个问题:通过数据挖掘得出机床当前状态:通过makespan-LT指标将动态的机床状态添加到调度模型中去,指导调度模型寻找更优解.下面对这两个子问题分别进行验证.

通过数据挖掘得出机床当前状态的验证步骤,从某军工企业机械加工试验线数据库中读取产品订单,截取从上次机床保养/维修后的所有订单信息;并提取产品的工艺路线、产品合格率、产品所属种类及该种类的期望合格率;对提取的数据进行结构化处理(形成Tab文件),并将数据映射为如图 10(b)的事务分析矩阵.

图 10 结构化事务数据及衍生 Fig.10 Structured transaction data and derivatives

事务分析矩阵中描述了某订单中工艺路线和产品质量信息,其中Mi=1表示该订单的工艺路线中包含设备Mi;损失质量Q=ConformanceRate < ConformanceRateStandard?1:0.

通过python第三方库Orange3-Associate1.1.5进行挖掘,得到频繁项集,设置minsupp(R)=10%和minconf(R)=40%选择合适的关联规则.通过分析,过滤掉由于工艺原因产生的质量问题(机床之间的频繁项),得到损失质量(Q=1)与机床(Mi=1)的关联规则,得到如表 3所示的结果参数.

表 3 MQ关联分析结果参数 Tab.3 Selected mining results
序号 M Q supp conf lift lev strg
1 M1=1 Q=1 0.186 0.369 0.836 -0.036 0.874
2 M2=1 Q=1 0.348 0.683 1.547 0.123 0.865
3 M3=1 Q=1 0.206 0.412 0.933 -0.015 0.882
4 M4=1 Q=1 0.235 0.471 1.067 0.015 0.882
5 M5=1 Q=1 0.216 0.431 0.978 -0.005 0.882

表 3中可以看出,规则1,3,5(第1,3,5行)中lift(R) < 1且lev(R) < 0,说明机床1,3,5与产品质量损失没有关系.规则2,4(第2,4行)中lift(R)>1,lev(R)>0,说明机床2,4对产品质量带来消极影响,同时规则2的杠杆率和提升度均明显高于规则4,则说明机床2对产品质量的消极影响更大.

机床2机床综合状态不良.根据2.3节的映射矩阵可知,机床2的lev(R)=0.123,得到其对应的可用性为80%,其它机床lev∈[-1,0.03),得到其对应的可用性为100%.

至此得到当前机床实际状态,并依据该军工企业进行生产线建模.使用JSSP典型问题FT20(20×5)[18]数据集来测试该模型,设置T=90,M=36,采用部分映射交叉算子(PMX交叉算子),交叉概率Pc=0.9,采用随机变异,变异概率Pm=0.1.

为验证该方法的有效性设计验证方案:在机床为理想状态的前提下(机床可用性均为100),得到调度方案1,此时加工序列为L1,在调整后的模型中执行序列L1得到最大完工时间为T1;考虑机床当前状态(机床2可用性为80,其它机床可用性为100),并以采用2.4.1节的初始种群作为重调度的初始种群,得到方案2,此时加工序列为L2,最大加工时间为T2;考虑机床当前状态(机床2可用性为80,其它机床可用性为100),并以调整前调度方案为初始种群进行重调度,得到调度方案3,此时加工序列为L3,最大加工时间为T3.

调度方案在最大完成时间、优化的运行时间(寻优模型运行时间)、最优方案收敛代数及有效寻优时间四项指标上的比较如表 4所示.优化的运行时间是模型进行90代迭代所需要的时间,其值大小反映了模型的复杂程度;最优方案收敛代数反映了算法的寻优搜索更加高效,其值大小反映了算法的性能;有效寻优时间是平衡了模型复杂度和算法性能后提出的指标,其值越小,说明调度过程越高效;最大完成时间是指得到的方案在实际模型中执行消耗的时间.由表 4可知,与调整前(方案1)相比,采用机床状态进行调整后的方案(方案2、方案3),可以得到更好的最大完成时间和有效寻优时间.综上所述,本文提出的基于质量分析的作业车间调度模型能够更好地适应机床状态的变化,得出的调度方案在实际生产中具备更高的可执行性.

表 4 方案对比 Tab.4 Scheme comparison
方案类型 指标
最大完成时间/s 优化的运行时间/s 最优方案收敛代数/代 有效寻优时间/s
方案1 1516 28 63 19.6
方案2 1392 40 35 15.5
方案3 1400 44 25 12.2
注:有效寻优时间=优化运行时间×(最优方案收敛代数/种群代数)
4 总结

本文对作业车间生产排程与质量数据分析相关问题进行了研究,构建了质量数据分析驱动的作业车间排程模型.本文提出了损失时间用于描述机床状态波动对加工时间的影响机制,同时构造makespan-LT调度指标用以选出执行性更好的方案.下一阶段将此方法应用到柔性作业车间调度等问题上,用于指导机床的选择和工件的排序,同时提高系统的计算能力和对实时数据的响应能力.

参考文献
[1] 刘民. 基于数据的生产过程调度方法研究综述[J]. 自动化学报, 2009, 35(6): 785–806.
Liu M. A survey of data-based production scheduling methods[J]. Acta Automatica Sinica, 2009, 35(6): 785–806.
[2] 王红卫, 祁超, 魏永长, 等. 基于数据的决策方法综述[J]. 自动化学报, 2009, 35(6): 820–833.
Wang H W, Qi C, Wei Y C, et al. Review on data-based decision making methodologies[J]. Acta Automatica Sinica, 2009, 35(6): 820–833.
[3] 吴启迪, 乔非, 李莉, 等. 基于数据的复杂制造过程调度[J]. 自动化学报, 2009, 35(6): 807–813.
Wu Q D, Qiao F, Li L, et al. Data-based scheduling for complex manufacturing processes[J]. Acta Automatica Sinica, 2009, 35(6): 807–813.
[4] Zhang Z C, Zheng L, Li N, et al. Minimizing mean weighted tardiness in unrelated parallel machine scheduling with reinforcement learning[J]. Computers and Operations Research, 2012, 39(7): 1315–1324. DOI:10.1016/j.cor.2011.07.019
[5] Nasiri M M, Yazdanparast R, Jolai F. A simulation optimisation approach for real-time scheduling in an openshop environment using a composite dispatching rule[J]. International Journal of Computer Integrated Manufacturing, 2017, 30(12): 1239–1252. DOI:10.1080/0951192X.2017.1307452
[6] 张晶, 熊梅惠, 陈垚, 等. 面向信息物理系统的时间不确定任务流动态实时调度算法[J]. 信息与控制, 2018, 47(1): 81–89.
Zhang J, Xiong M H, Chen Y, et al. Dynamic real-time scheduling algorithm for time-indefinite task flow in cyber-physical systems[J]. Information and Control, 2018, 47(1): 81–89.
[7] Jongsawas C, Ramesh S. RFID-enabled track and traceability in jolrshop scheduling environment[J]. European Journal of Operational Research, 2013, 227(3): 453–463.
[8] Zhu X C, Qiao F. Processing time prediction method based on SVR in semiconductor manufacturing[J]. Journal of Donghua University(English Edition), 2014, 31(2): 98–101.
[9] 龙田, 王俊佳. 基于调度规则和免疫算法的作业车间多目标调度[J]. 信息与控制, 2016, 45(3): 278–286.
Long T, Wang J J. Multi-objective job shop scheduling based on scheduling rules and immune algorithm[J]. Information and Control, 2016, 45(3): 278–286.
[10] 汤洪涛, 费永辉, 陈青丰, 等.基于工业大数据的柔性作业车间动态调度研究[J/OL].计算机集成制造系统. (2019-04-16)[2019-10-10].http://kns.cnki.net/kcms/detail/11.5946.TP.20190412.1637.020.html.
Tang H T, Fei Y H, Chen Q F, et al. Study on flexible job shop dynamic scheduling based on industrial big data[J]. Computer Integrated Manufacturing Systems, 2019.(2019-04-16)[2019-10-10]. http://kns.cnki.net/kcms/detail/11.5946.TP.20190412.1637.020.html.
[11] Cheng R W, Gen M, Tsujimura Y. A tutorial survey of job-shop scheduling problems using genetic algorithms[J]. Computers and Industrial Engineering, 1996, 30(4): 983–997. DOI:10.1016/0360-8352(96)00047-2
[12] 周金平. 生产系统仿真:Plant Simulation应用教程[M]. 北京: 电子工业出版社, 2011: 214-243.
Zhou J P. Production system simulation:Application tutorial of plant simulation[M]. Beijing: Publishing House of Electronics Industry, 2011: 214-243.
[13] Tsung F, Li Y T, Jin M. Statistical process control for multistage manufacturing and service operations:A review and some extensions[J]. Inderscience Publishers, 2008, 3(2): 191–204.
[14] 孟飙, 周飞, 王旭东, 等. 面向飞机装配质量数据深度分析方法研究[J]. 科学技术与工程, 2015, 34(15): 235–241.
Meng B, Zhou F, Wang X D. Research on depth analysis method for aircraft assembly quality data[J]. Science Technology and Engineering, 2015, 34(15): 235–241.
[15] Geng L Q, Hamilton, et al. Interestingness measures for data mining:A survey[J]. ACM Computing Surveys, 2006, 38(3): 3.
[16] Brin, Sergey, Motwani, et al. Dynamic itemset counting and implication rules for market basket data[J]. SIGMOD Record (ACM Special Interest Group on Management of Data), 1997, 26(2): 255–264.
[17] Clauset A, Shalizi C R, Newman M E J. Power-law distributions in empirical data[J]. Society for Industrial and Applied Mathematics, 2009, 51(4): 661–703.
[18] 王凌. 车间调度及其遗传算法[M]. 北京: 清华大学出版社, 2003.
Wang L. Shop scheduling with genetic algorithms[M]. Beijing: Tsinghua University Press, 2003.
http://dx.doi.org/10.13976/j.cnki.xk.2020.0574
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

孟飙, 赵志刚, 高建丽
MENG Biao, ZHAO Zhigang, GAO Jianli
面向机床状态波动的调度模型
Job-shop Scheduling Model for Machine State Fluctuations
信息与控制, 2020, 49(4): 499-506, 512.
Information and Control, 2020, 49(4): 499-506, 512.
http://dx.doi.org/10.13976/j.cnki.xk.2020.0574

文章历史

收稿/录用/修回: 2019-10-18/2020-01-21/2020-05-08

工作空间