1．武汉科技大学生产系统工程研究所，武汉，4300812．武汉科技大学冶金装备及其控制教育部重点实验室，武汉，4300813．武汉科技大学机械传动与制造工程湖北省重点实验室，武汉，430081
关键词：重调度方式选择；遗传仿真；降维；支持向量机分类
为此，本文提出了一种隐性扰动累积下基于学习的重调度决策机制。
隐性扰动问题复杂多变，基于学习的扰动累积下重调度方式选择问题需将隐性扰动量化，用数据表征生产状况。此外，由于隐性扰动的累积效应，需决策何时启动重调度，进一步需确定启用何种重调度。
在实际生产中，加工时长变动、生产物流衔接等，都会导致工序开始加工时刻的变化。
对于隐性扰动问题，判定重调度启动与否的具体时刻点对重调度的使用频次、车间稳定性和生产连续性具有较大的影响。当累积误差为正时，实际调度已经显著偏离计划，有可能出现交货期延迟等问题。由于鲁棒优化下的原计划调度具有一定程度的抗干扰能力，可削弱隐性扰动的影响，故将实际生产中累积误差为正的任务开始时刻选为重调度时刻点，在一定程度保持系统稳定性并对生产状况进行响应。
基于学习的重调度方式选择，是在海量带标签样本的基础上，通过采用机器学习等方法，决策不同扰动累积情形下的最优重调度方式。其中，每个数据样本均以最优重调度决策方式作为标签。
已知工件集I={i|1,2,…,I}，工序集J={j|1,2,…,J}，机器集K={k|1,2,…,K}，机器上的加工次序T={t|1,2,…,T}，oij表示工件i的工序j，当其在机器k上加工时则mijk=1。决策标签y可取1或-1，分别表示右移重调度或完全重调度。同时，定义重调度时刻点为分别表示在重调度发生之前机器k第t个任务的开始和结束时刻。为描述问题方便，定义Fij、Cij、Wij分别为重调度时刻已经完成加工、正在加工、等待加工的工序，且有
(1)
(2)
式中，分别为工件i的工序j在机器k上的计划加工时长、实际加工时长；为经过重调度后余下尚需完成工序的剩余加工时长。
重调度实质是对正在执行和等待加工的工序集进行重新定时或重新分配，以满足重调度后制造周期最短、车间调整最小等目标。其中，定义分别为重调度发生后机器k第t个任务的开始和结束时刻，且将重新分配决策变量表示为
重调度数学模型约束条件可表示为
(3)
k,t=T
(4)
i，j≤J,oijFij
(5)
(6)
(7)
(8)
(9)
i,j 重调度方式选择的目标函数可表示为 (10) 为实现快速、智能、实时决策，本文构建了图1所示的基于数据学习的重调度方式选择框架。具体包括重调度大样本生成、重调度选择模型构建以及实际生产中重调度方式选择模型应用。 图1重调度方式选择框架Fig.1Frameworkofreschedulingmodeselection 由于设备、技术等原因，直接从实际生产中获得所需的研究数据代价极大。本文通过模拟仿真产生实验研究数据，将隐性扰动问题量化，用数据反映现实加工状况。如图2所示，所采集数据包括重调度前、重调度启动后表征生产状况的数据，以及重调度方式选择标签数据。 图2数据采集框架Fig.2Frameworkofdataacquisition (1)加工数据生成。隐性扰动造成工序加工时长变化，从而改变原调度计划，故可利用3种随机数改变加工时长来生成大量加工数据以模拟实际扰动：第一种随机数是产生扰动的工序总道数；第二种是某个工件的某道工序产生的扰动；第三种是扰动量大小。各工序鲁棒阈的设定是将归一化的原加工时长作为权重乘以(0,1)之间的随机数。 (3)重调度后评价因素。分析和处理需要进入重调度的工序。此过程可用进入重调度的工序加工情况评估生产状况。鉴于前期文献缺乏此方面的研究，故考虑因子时应尽可能多地收集与生产状况有关的数据。此外，限于篇幅，将在后续单样本实例中具体展示所需因子数据。 (5)获取大样本数据。重复以上步骤，可获得多维样本数据(最后一维是决策标签)。 数据样本的质量对数据分析以及模型建立有直接影响。以下是针对所采集数据的初步处理。 (1)缺失值。采用平均值填充方式对数据进行处理。 (3)平衡两类样本。通过使用重复、自举或合成少数类过采样(SMOTE)等方法来生成新的稀有样本。 不同特征数据的处理方式不一样，故在运用数据建模之前，有必要对数据特征进行简单分析，了解数据形态。 图3统计了36个工序、4000个样本获得各自在不同重调度时刻点的生产情形。它表明生成的样本中，除已加工工序数{1,2,35}没有对应样本外，其他重调度情况都有对应样本。此结果表明，除极端情况外，生成的样本能有效覆盖实际生成状况。 图3样本整体概括Fig.3Samplegeneralization Tab.1Pearsoncorrelation 设重调度样本D={(x1,y1),(x2,y2),…,(xm,ym)}，y为重调度决策标签，yi∈{-1,1}，Nj为第j类样本的个数，Xj为第j类样本的集合，μj为第j类样本的均值向量，Σj为第j类样本的协方差矩阵,则有 (11) (12) j=-1,1 为保证同一重调度方式样本的投影点尽可能接近，而不同重调度方式样本中心之间的距离尽可能大，将LDA模型简化为 argmax (13) 分类预测方法众多，如决策树、贝叶斯分类器等，但不同分类器对数据特征的要求不同，如贝叶斯分类器、决策树等不易于对样本属性值连续的数据进行分类预测；而神经网络训练分类器时，其训练过程是使网络全局误差趋于极小值，易出现过拟合状况从而使预测准确率降低；支持向量机(supportvectormachine,SVM)训练的分类器在解决连续属性分类问题上有一定成效，能在分类准确的基础上，最大化容忍犯错，有效避免过拟合，较好地对二类问题进行分类预测[12]。由于重调度方式选择的样本数据属性连续,故考虑用SVM进行分类预测。 在SVM中，支持向量表示在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例。定义y为重调度决策标签,y∈{-1,1}，ω为法向量，b为偏置，n为重调度样本总数，xi表示第i个样本,则有 (14) (15) 式(14)为一般计算点到直线的距离d的公式。在SVM中，式(15)描述函数能够正确划分点到超平面(能将两类重调度方式样本分隔的面)的距离dd。若定义支持向量到超平面的距离为1，即y(ωTx+b)=1,为保证模型准确，其他样本需满足y(ωTx+b)>1,此时SVM模型求解过程变为 (16) 为证实所选降维方法LDA的有效性，以非线性降维ISOMAP和无监督线性降维主成分分析(principalcomponentanalysis,PCA)为代表，进行对比实验。 其中，ISOMAP是一种等距映射算法。利用ISOMAP降维时，从二维到三维残差方差下降最快，将数据降到三维时，两类数据样本分布见图4。 图4ISOMAP降维Fig.4DimensionreductionofISOMAP 利用PCA对数据降维，前三个主成分贡献了92.65%的信息，将数据降到三维时，两类数据样本的分布图见图5。可看出其分类效果优于ISOMAP，说明采用PCA更有利于不同扰动累积情形下的重调度方式样本数据分类。 图5PCA降维Fig.5DimensionreductionofPCA 对比线性无监督降维PCA与线性有监督降维LDA可知，PCA方法不考虑数据标签，只选择样本点投影具有最大方差的方向，而LDA使得同类样例投影点尽可能接近、异类样例投影点尽可能远离，因此选用LDA对此类数据降维更有利于样本的分类。 图6是基于LDA将高维大样本数据降到一维时的两类样本分布图，由图可看出第二类样本的数值基本小于第一类样本，两类样本基本可区分；图7是采用LDA将数据降到二维时两类样本的分布图，由图可看出样本点间虽有融合，但大体可区分。由于将数据降到3维以上时出现复数，其降维效果将以分类准确率的形式量化。 图6一维样本分布图Fig.61Dsampledistributionmap 图7二维样本分布图Fig.72Dsampledistributionmap 为精确比较降维效果好坏，基于4000个样本，用不同降维方法处理的数据训练了三维输入下的SVM模型，并进行预测。其中，训练样本与测试样本比例为7∶3。从图8可看出，直接用原始高维数据建立SVM模型，模型准确率83.8%，但数据维度高，存储和计算代价高；基于PCA的SVM模型，准确率为0.788，数据储存等代价降低，但可能由于损失了数据精度，准确率下降；基于ISOMAP的SVM模型，准确率为0.62；而利用LDA方法对数据处理后，模型准确率为83.7%，既去除了高维数据中的冗余信息，降低了计算代价，又保证了数据精度。 图8不同降维方法的准确率Fig.8Accuracyofdifferentdimensionreductionmethods 为测试LDA降维维度对LDA-SVM模型的影响，实验中，从4000组训练样本中随机抽取2800组训练模型。训练模型输入由LDA处理得到，测试输入由LDA降维时主特征值对应特征向量映射得到，模型输出为对应决策标签。由图9可看出，基于LDA降维数据的SVM模型分类准确率在80%以上。与一维特征量相比，二维特征量表达的信息更多，分类准确率提升0.027。但数据维度降到三维以上时，由于数据冗余等干扰，分类准确率略有下降。 图9分类准确率对比Fig.9Comparisonofclassificationaccuracy 确定降维方式及最佳降维维度后，为测试LDA-SVM组合模型的有效性，在样本规模为10000的实验环境下进行了表2所示实验。其中，训练样本与测试样本比例为7∶3。实验结果显示，同一样本下LDA-SVM预测准确率最高。 为进一步测试LDA-SVM模型的稳定性，需要进行不同样本规模下的模型测试实验。表3中，所有实验的训练、测试样本比例为7∶3，数据维度为2。表3表明，随着样本规模的改变，模型准确率稍有变动，但总体准确率保持在83%。此外，样本规模为4000时，模型已学习到数据基本特征，尽管样本规模进一步扩大，准确率却难有提升，模型基本稳定。 表2不同决策模型对比实验(样本规模10000) Tab.2Contrastexperimentofdifferentdecisionmodels(samplesize10000) 模型训练输入训练输出预测输入预测输出准确率(%)LDA-SVM7000270001300023000183.9LDA-GRNN7000270001300023000182.3LDA-PNN7000270001300023000183.0LDA-logistic7000270001300023000183.5 表3不同规模下LDA-SVM模型预测实验 Tab.3LDA-SVMpredictionondifferentscales 样本规模SVM训练输入SVM训练输出SVM预测输入SVM预测输出准确率(%)1000700270013002300180.340002800228001120021200183.770004900249001210022100183.5100007000270001300023000183.920000140002140001600026000182.230000210002210001900029000183.3 Tab.4Time-tablewithrobustoptimization 工序1工序2工序3工序4工序5工序6工件13.7511.251053.7512.5工件26.258.753.752.53.753.75工件33.7557.56.2511.257工件48.752.53.753.7563.75工件56.2511.257.5106.255工件62.511.258.7511.25511.25 Tab.5Simulatedactualtime-tablewithdisturbance 工序1工序2工序3工序4工序5工序6工件13984310工件215732153工件3346594工件47163333工件5596854工件62197949 通过调度模型、遗传算法可得到最优原计划调度方案。图10给出了调度甘特图，从图中可看出各工序加工顺序以及开始结束时刻，以及makespan。 图10原计划调度图Fig.10Originalscheduling 图11实际调度图Fig.11Actualscheduling 确定重调度时刻点后，根据重调度模型、遗传算法得到图12、图13所示的右移、完全重调度方案。此过程可得到重调度后评价因子数据及决策标签。 图12右移重调度图Fig.12Rightshiftrescheduling 图13完全重调度图Fig.13Totalrescheduling 以上步骤获得了表征生产状况以及影响决策标签的19个评价因子数据以及决策标签，完成了数据采集工作，具体数据见表6。为检验结果，表6给出了右移和完全重调度的makespan。 表6所采集数据汇总 Tab.6Summaryofthecollecteddata 获得数据后，通过LDA建立的映射可得到三维映射数据，输入SVM得到预测结果为-1，其结果与实验数据一致。 (1)本文基于随机仿真获得大量的生产情形，基于数学模型和优化算法生成对应情形下的重调度决策样本，提供了一种低成本的、在无法获取海量样本前提下的重调度决策样本生成方法。 (2)通过分析数据特征，构建了LDA-SVM模型，便于管理者决策。 (3)将数据仿真、智能优化和机器学习进行结合，并用于重调度方式选择问题中，为研究隐性扰动下的重调度问题提供了新思路。后续工作将集中在影响因子组合选择、决策模型参数优化等方面，以便进一步提升预测精度。 参考文献： [1]KATRAGJINIK,VALLADAE,RUIZR.FlowShopReschedulingunderDifferentTypesofDisruption[J].InternationalJournalofProductionResearch,2013,51(3):780-797. [2]WANGC,JIANGPY.ManifoldLearningBasedReschedulingDecisionMechanismforRecessiveDisturbancesinRFID-drivenJobShops[J].JournalofIntelligentManufacturing,2016:1-16. [3]PETROVICD,DUENASA.AFuzzyLogicBasedProductionScheduling/ReschedulinginthePresenceofUncertainDisruptions[J].FuzzySetsandSystems,2006,157(16):2273-2285. [4]乔非,李莉,王遵彤,等.面向半导体生产的改进的混合重调度策略研究[J].计算机集成制造系统,2007,13(3):558-562. QIAOFei,LILi,WANGZuntong,etal.ImprovedHybridReschedulingStrategyforSemiconductorManufacturing[J].ComputerIntegratedManufacturingSystem,2007,13(3):558-562. [5]单晖.基于实时工况的JobShop动态随机重调度方法研究[D].合肥：合肥工业大学,2008. SHANHui.ResearchonJobShopDynamicRandomReschedulingMethodBasedonReal-timeOperatingConditions[D].Hefei:HefeiUniversityofTechnology,2008. [6]陈静云.车间物联网数据采集关键技术研究[D].南京:南京航空航天大学,2014. CHENJingyun.ResearchonKeyTechnologiesofDataAcquisitionofInternetofThingsinWorkshop[D].Nanjing:NanjingUniversityofAeronauticsandAstronautics,2014. [7]JIANGP,CAOW.AnRFID-drivenGraphicalFormalizedDeductionforDescribingtheTime-sensitiveStateandPositionChangesofWork-in-progressMaterialFlowsinaJob-shopFloor[J].JournalofManufacturingScienceandEngineering,2013,135(3):189-197. [8]刘明周,单晖,蒋增强,等.不确定条件下车间动态重调度优化方法[J].机械工程学报,2009,45(10):137-142. LIUMingzhou,SHANHui,JIANGZengqiang,etal.DynamicReschedulingOptimizationofJob-shopunderUncertainConditions[J].JournalofMechanicalEngineering,2009,45(10):137-142. [9]刘壮,张中敏,杜先军.基于改进TOPSIS的制造车间重调度决策方法研究[J].组合机床与自动化加工技术,2017(1):157-160. LIUZhuang,ZHANGZhongmin,DUXianjun.ReschedulingDecisionMethodofManufacturingShopBasedonImprovedTOPSIS[J].ModularMachineToolandAutomaticMachiningTechnology,2017(1):157-160. [10]AKKANC.ImprovingScheduleStabilityinSingle-machineReschedulingforNewOperationInsertion[J].Computers&OperationsResearch,2015,64:198-209. [11]毕达天,邱长波,张晗.数据降维技术研究现状及其进展[J].情报理论与实践,2013,36(2):125-128. BIDatian,QIUChangbo,ZHANGHan.ResearchStatusandProgressofDataDimensionReductionTechnology[J].InformationTheoryandPractice,2013,36(2):125-128. [12]刘萌萌,刘亚岚,孙国庆,等.结合纹理特征的SVM样本分层土地覆盖分类[J].遥感技术与应用,2014,29(2):315-323. LIUMengmeng,LIUYalan,SUNGuoqing,etal.StratifiedLandCoverClassificationBasedonSVMSampleswithTextureCharacteristics[J].RemoteSensingTechnologyandApplication,2014,29(2):315-323. TANGQiuhua1,2,3CHENGLixin1,2,3ZHANGLiping1,2,3 1．InstituteofProductionSystemsEngineering,WuhanUniversityofScienceandTechnology,Wuhan,4300812．KeyLaboratoryofMetallurgicalEquipmentandControlTechnology,WuhanUniversityofScienceandTechnology,Wuhan,4300813．HubeiKeyLaboratoryofMechanicalTransmissionandManufacturingEngineering,WuhanUniversityofScienceandTechnology,Wuhan,430081 Abstract:Amethodofreschedulingmodeselectionwasproposedtosolvetheproblemsofdisturbancecumulativereschedulingschemeselectionbasedondatalearning.Thecumulativedisturbancetimewasusedtoquantifytheimplicitdisturbance,andthereal-timeproductionandprocessingstatuswerereflectedbydata.Thecumulativedisturbancereschedulingmodelwasconstructed,andthefactorsanddecisionlabelsofreschedulingdecisionwereobtainedbasedongeneticsimulation.Thecharacteristicsofthesimulationsampleswereanalyzed,andbasedonthedatafeaturereductionmapping,theSVM-basedclassificationdecisionmodelwasconstructedtolearntheinternalrelationshipbetweentheproductionsituationandthereschedulingmode,whichwouldhelptheproductionmanagerstomakethedecisionquicklyandimprovetheresponsespeed.Finally,therationalityandeffectivenessofthereschedulingselectionframeworkwereverifiedbyexperiments. Keywords:reschedulingmodeselection;geneticsimulation;dimensionreduction;supportvectormachine(SVM)classification 中图分类号：TP181 DOI：10.3969/j.issn.1004-132X.2019.04.014 开放科学(资源服务)标识码(OSID)： 收稿日期：2018-05-31 基金项目：国家自然科学基金资助项目(51875421，51875420) (编辑王旻玥) 作者简介：唐秋华,女，1970年生，教授、博士研究生导师。研究方向为生产过程与调度。E-mail:tangqiuhua@wust.edu.cn。