隐性扰动下柔性作业车间重调度决策＊

宋李俊 徐志鹏 李 斐

（①重庆理工大学机械工程学院，重庆 400054；②中冶赛迪工程技术股份有限公司，重庆 400013）

柔性作业车间中的隐性扰动具有多变性和复杂性的特点，例如操作时间偏差、工件到达时间不准等隐性扰动以累积的形式存在，由于工序之间联系密切，导致这种扰动累积问题更加复杂。短时间的隐性扰动累积一般对生产计划影响较小，但当扰动累积到一定程度就会使当前加工情况严重偏离原调度计划，此时需要进行重调度[1]。由于隐性扰动重调度界限不明确，会出现误调度和调度不及时的情况，使企业遭受损失。因此，重调度时刻点的确定是解决隐性扰动下的重调度问题的关键之一。同时，当扰动发生后，选择合适的重调度方式也是重调度问题中不可缺少的一环。

为了明确重调度的界限，刘明周等[2]将扰动分为显性扰动和隐性扰动两类，以分析车间中随机扰动引起的不确定性问题。一般来说显性扰动对于原调度方案的影响较大，极易触发重调度；而隐性扰动的影响较小，不易触发重调度。目前对隐性扰动的研究较少[1-4]，其难点之一是由于隐性扰动的累加特性导致重调度界限难以确定，所以寻求有效的方法界定隐性扰动累积情况下的重调度界限是十分必要的。

改革开放40年间，茅台集团无论是酒产量、销售收入还是公司总资产都得到了惊人的发展。40年茅台的发展是所有茅台人汗水的结晶，也给了消费者一份满意的答卷。

关于隐性扰动重调度时刻点的确定，吴定会等[4]针对隐性扰动累积下的车间重调度问题，利用孪生网络建立扰动检测模型，以实时数据为输入，实现重调度的启动时刻的判定。Haruhiko Suwa[5]针对在线调度中何时触发重调度的问题，提出了一种基于累积延迟的重调度策略，综合了周期性重调度和事件驱动型重调度的特点。Can Akkan[6]深入了解了预调度的鲁棒性特征，在隐性扰动触发重调度决策上选用被动触发式重调度驱动原则。但现有重调度时刻点的研究多数加入了模糊数学的思想，没有严格的明确各种扰动情况下的重调度时刻点，导致在某些特定情况下重调度时刻点确定的不够准确，造成损失。

重调度时刻点确定后需要对重调度方式进行决策。金鹏博等[7]针对柔性作业车间中的机器故障问题，提出一种重调度方式决策模型，快速、高效地估计出最优重调度方式。李玉等[8]针对作业中不确定事件及信息不对称等问题，提出一种基于数字孪生的动态调度方法。宋李俊[9]针对动态环境下的柔性作业车间，基于滚动时域优化基本框架，设计一种周期和事件混合的动态调度策略。廖怡娜等[10]为解决调度中出现的作业返工而导致计划中断问题，提出一种前瞻性反应式调度算法。汤洪涛等[11]为提高柔性作业车间动态调度对扰动的实时响应能力,根据工业大数据特点，提出相关历史数据中挖掘调度规则的方法。由于3种重调度方式执行起来效果不一，故需要通过多方面进行评价选择。

为此，本文分析了柔性作业车间各工序之间的关联性，在不超出各工件交货期的前提下，确定了扰动累积条件下的重调度时刻点。基于遗传算法设计了3种重调度方式的程序，并建立了重调度方式决策模型，对重调度方案进行选择。

1 问题描述

柔性作业车间调度问题（flexible Job-shop scheduling problem, FJSP）是在传统的作业车间调度问题（job-shop scheduling problem, JSP）上增加了为工序分配机器的操作[12]。与JSP相比，FJSP更具有灵活性，其主要特点为一台机器可以加工多种工序，一道工序也可选择不同机器进行加工。FJSP相较于JSP更贴合当代生产实际，同时其工序、机器之间的联系也更加复杂。

法律中幸福人的预设背后是一种面向生活世界的思维，寄涵着法律对人类理想生活状况的关怀，它真挚关注每个个体的幸福，同时也构设理想的生活方式，以令人满意的法律方式来实现以“人的生活”为终极关怀，即人之优良幸福的生活。“一切有生命和爱的生物、一切生存着的和希望生存的生物之最基本的和最原始的活动就是对幸福的追求。人也同其他一切有感觉的生物一样，他所进行的任何一种意志活动，他的任何一种追求也都是对幸福的追求。”［10］29我们都确然渴望幸福地生活，追求幸福是我们行动的动力和终极目的。

经典调度问题的研究建立在理想的静态条件下，然而在实际生产过程中，各种不确定扰动的发生会打乱原定的生产计划，所以对于动态柔性作业车间调度问题的研究也更有意义[13]。现如今对动态调度问题的研究多数在于对算法的改进，而未考虑到是否需要进行重调度以及采用何种方式进行重调度，所以本文针对重调度时刻点和重调度方式选择进行了研究。

1.1 工序间的动态关联性

在柔性作业车间生产中，众多工序间的联系繁杂，当某一工序发生扰动时，往往导致多道工序受到影响。图1展现了调度方案的动态关联性[14]，并描述了在某一工序发生扰动时所带来的联动影响。

图1 调度方案的动态关联性

当O201发生扰动时，直接影响两道工序O202和O302，从而间接影响工序O203、O402、O303、O103。可以明显看出，每道工序最多直接影响两道工序，即机器上的后一紧邻工序以及该工件的下一紧邻工序。本文将这两种影响归纳为两个维度的影响，即机器维度和工件维度。

1.2 问题假设

①同一工件的加工顺序固定。

②不同工件的任意工序之间无顺序联系。

③每道工序同一时刻只能在1台机器上加工。

④每台机器同一时刻只能加工1道工序。

⑤不同工件的工序之间加工优先级相同。

⑥同一工序在不同机器上的加工时间可以不相同。

由于缺少工序A403，故“ -Inf”作为缺省标记，以便于在保证矩阵在运算过程中，该位置处的值一直为负无穷。

某生产线由n台机器组成，假设生产中需要对a个工件进行加工，第i个工件有bi道工序，主要参数见表1和表2。

表1 柔性作业车间参数

表2 重调度参数

2 重调度时刻点确定

柔性作业车间中发生的扰动，一般会降低原调度方案对实际生产的指导性能，此时一般需要对调度方案进行调整。应对扰动事件的调整主要体现在以下两个层次：①不改变工序的加工顺序及加工机器，且各工件不发生逾期完工的情况，适当的将某些工序进行延后（右移）排产，简称为右移调度。②在右移调度无法保证各工件如期完工的情况下，对某些工序重新安排，即重调度。所以，调度方案的调整可分为右移调度方法和重调度方法[14]。

本文针对柔性作业车间中的隐性扰动，以不超出各工件交货期为限定条件（即不触发重调度），不改变各工序的加工顺序及加工设备，只对工序进行简单的右移调度。目的是计算出各个工序最迟容许完工的时间点，并以此作为各工序触发重调度的时刻点。

根据已有研究结果[3]，按多元Logistic回归模型中样本容量的计算方法，利用2013年第五次国家卫生服务调查重庆农村地区的相关数据，失访率为50%，计算样本容量为270例。实际共抽糖尿病患者496例。利用Epidata录入问卷调查数据，数据整理和分析采用统计工具软件Stata 11.0。

2.1 重调度时刻点计算模型

当各工件的交货期固定时，可以理解为每个工件的最后一道工序不可超出各自的交货期，且所有工序在进行右移调度调整时也不能使任意工件超出交货期。这样在工件维度和机器维度上每道工序都会分别存在一个延迟完工时间的极限值。综合各个工序两个维度上的延迟完工时间极限值以及工序间的动态联系，计算出每道工序的容许延迟时间Aij，最后求出每道工序所对应的重调度时刻点。

式（1）中 :uij为0-1变量，当工序Oij工件维度的下一道工序Oi（j＋1）存在时为1，反之为0；同理,式（2）在工序Oij机器维度的下一道工序Oi′j′存在时,vij=1，反之vij=0；式（3）、（4）分别为工序Oij在工件维度和机器维度上的容许延迟时间，通过0-1变量u和v对不同情况进行界定；式（5）表示工序Oij的容许延迟时间，即两个维度上容许延迟时间的最小值；式（6）中R代表所有工序的容许延迟时间；式（7）表示工序Oij的重调度时刻点。

由式（3）～（5）可以看出，在工序Oij两个维度上的下一工序的容许延迟时间已知的情况下才能计算Aij，所以计算出所有工序的容许延迟时间R矩阵是一个循环倒序遍历的过程，计算流程如图2所示。

图2 倒序遍历计算流程图

完全解出矩阵R后，由式（7）得出各工序的重调度时刻点。

2.2 重调度时刻点计算步骤

以图1调度方案为例，欲计算出工序102的容许延迟时间，其两个维度上的后序紧邻工序为工序103和工序203。工序103和工序203的容许延迟时间分别为A103、A203，则工序102的容许延迟时间

（1）维度关系建立

①工件维度工序关联矩阵G

游成令的事迹引起了市食品药品监管系统的高度关注，市局领导亲自慰问并组织捐款10万余元，但高昂的治疗费用，让这个家庭根本无法承受。无奈之下，游成令丈夫在网上发表“一岁半女儿身患白血病，求帮我留住她的生命！”求助帖子，最终筹集到近20万元善款，及时解决了孩子前期治疗费用。

⑦加工不可中断。

（2）遍历计算过程

具体到毕业设计的管理来说，面对新工科的要求，需要将毕业设计的总体目标分解成一系列任务，通过完成一系列的任务去实现社会岗位需求毕业生的人文素养、科技知识、实践技能、职业能力、伦理价值和行为规范的新工科目标。从选题到完成答辩的整个教学进程都应该在传统学科专业建设的基础上，重新审视培养方案、管理模式、教学平台建设的合理性,并提出对指导教师能力素质的新要求。

工序Oij的容许延迟时间Aij只有在该工序两个维度容许值Gij,Hij都计算出时才可得出，其中Gij,Hij分别代表取矩阵G,H中第i行j列的值。

将式（9）和式（10）对应位置取最小值，得到新矩阵R。

月－2011年5月对本市3～6周岁幼儿3 346人屈光状态进行调查，其中男童1 880人、女童1 466人，男女比例为1．28∶1；按年龄分成4组：3～岁组565人，4～岁组864人，5～岁组1 010人，6～7岁组907人。

① 输入：t1,t2,t3,t4。

按照图2的流程图进行计算，输入各工序交货期t1、t2、t3和t4，作为输入集合，遍历计算R矩阵。矩阵中计算出的已知值作为第一层输出值，将第一层输出值添加入输入集合，再次输入矩阵得到第二层输出值……将每层的输入集合循环遍历R矩阵各个元素，直至完全解出矩阵。

②第一次循环输出：A103、A203、A303、A403、A402。

② 第二次循环输出：A102、A202、A302、A401。

花垣—张家界断裂。花垣—张家界断裂带自黔东松桃经重庆秀山入湘，过本区茶洞、花垣、保靖、永顺、张家界向东延出区外入洞庭盆地。为矿区北部之边界，主要由6条大致平行的NE向断层组成，即F1、F1-1、F1-2、F1-3、F1-4、F1-5，其中F1为主断层，具多期次活动特点，倾向305°～335°，倾角65°～75°，北西盘下降，垂直断距500 m以上，水平断距6.5 km。为长期活动的区域性大断裂。自花垣—张家界一带多个大型金属矿床均分布其两侧，具区域性导矿特点。

③ 第三次循环输出：A101、A201、A301。

④ 完全解出，输出工序容许延时矩阵R。

将各工序的原计划完工时间加入矩阵R，得到重调度时刻点矩阵U。

3 重调度决策模型

重调度方式分为右移重调度（right shift rescheduling, RSR）、部分重调度（partial rescheduling, PR）和完全重调度（total rescheduling, TR）3种[15,16]。在重调度的3种方式中，右移重调度（RSR）对原调度方案的影响程度最小，部分重调（PR）度次之，完全重调度（TR）的影响程度最大。因此本文以逾期工件数最少、最大完工时间最小、对原调度方案影响程度最小为目标，找出使上述3个目标综合最优的重调度方式。

重调度方式决策流程如图3所示。

图3 重调度方式决策流程

重调度方式决策模型如下。

（2）部分重调度

表3 工序可选机器表示例

表4 工序加工时间表示例

按照以上数学模型对调度方案进行计算，可以得出各个工序的开始时间、结束时间以及调度方案的适应度函数值，并根据适应度函数值对调度方案进行选优操作。

（1）右移重调度

右移重调度（RSR）是指只对工序进行推迟加工操作，而不改变各工序的加工顺序与加工位置，在甘特图中表现为工序向右移动。在本文中右移调度和右移重调度（RSR）虽然操作相同，但却是两种不同的调度方法。前者发生在重调度时刻点前，后者发生在重调度时刻点后。

假设扰动工序为工序Oij，发生扰动后，其实际加工时长为

式（14）、（15）对Fi(j-1)、Fiojo进行了补充说明，当该维度的前一工序不存在时，值为0，其中Tij[xij]代表原调度方案中工序Oij的加工时长，Tij是工序Oij的加工时间集合，系数xij使工序加工时间表和工序可选机器表一一对应（如表3、表4所示），代表选择机器集合中的第xij号机器进行加工。式（16）代表工序Oij的开始时间Bij，取工件维度前一工序结束时间Fi(j-1)与机器维度前一工序结束时间两者的最大值；式（17）表示工序Oij的加工结束时间Fij；式（18）中的 δi代表当工件i的最后一道工序Oibi的结束时间大于交货期时， δi=1，反之，δi=0；式（19）为适应度函数f，max{Fibi}代表最大完工时间，代表超出交货期工件数，乘以一个极大数L，代表逾期工件数为第一决定因素，适应度函数值越小，代表方案越好。式（20）中 θ的取值为1、2、3分别代表右移重调度、部分重调度、完全重调度，s是一个极小的正数，其作用是在多种重调度方案的适应度函数值fθ相等时，选用对原调度方案影响程度最小的重调度方案，即选用Fθ最小的重调度方案。

部分重调度（PR），也叫受影响工序重调度[16]，是指对受影响的工序进行重新安排，未受影响的工序仍保持原调度方案加工。由于工序间的影响关系是在工件和机器两个维度上进行传递，故部分重调度的调度工序集合 Zpr可以用二叉树的形式表示。

2.6 施工安全与企业法人的关系企业法人是第一责任者。在我们走向依法治理国家的形势下，建筑安全也将走向依法治理的轨道，因此，企业法人对本企业的安全负有全盘责任。根据“谁主管谁负责”的安全管理原则，企业法人对员工的生命安全负全责，在经营决策上必须顾及安全，把安全摆到企业运作的非常重要的位置。

图4中二叉树顶端为发生扰动的工序，除顶端工序外的其他工序组成部分重调度工序集合 Zpr。在原调度方案的基础上，对部分重调度工序集合Zpr进行重新安排， Zpr集合外的工序保持不变。利用遗传算法将变异和交叉位置限定在 Zpr工序集合内，以适应度函数值为评价标准，进行多次迭代选优操作，最后得出部分重调度方案以及其适应度函数值f2。

图4 受影响工序二叉树

（3）完全重调度

②机器维度工序关联矩阵H

完全重调度（TR）是对重调度触发时还未加工的所有工序进行重新安排的一种调度方式。首先确定完全重调度的调度工序集合 Ztr。假设工序Oij发生扰动并触发重调度，则完全重调度工序集合为以下两个集合的并集：

Sink节点主要完成组网、接收路由节点和终端节点的数据信号，通过RS-232发送到上位机，同时接收上位机控制命令并下发；路由节点和终端节点功能类似，只是多了一个数据/命令转发功能，采用定时器中断模式，不工作时处于休眠状态，减少能量消耗。协调器和终端节点工作流程如图3和图4所示。

②部分重调度工序集合 Zpr。与部分重调度操作相同，利用遗传算法将变异和交叉位置限定在 Ztr工序集合内，得出完全重调度方案以及其适应度函数值f3。

3.多层次农业保险体系的不断构建与完善。发展中国农业大灾保险，不仅要在完全成本保险、收入保险的险种上进行突破，必然还要不断构建一整套多层次的农业保险体系。该体系内既要包含补贴资金“一卡(折)通”等形式兑付、电商与政务平台等信息进村入户一站式市场化服务、农村大数据和高级人工智能分析等技术性成分，又需要在政策上倾斜、支持符合条件的涉农企业发行上市IPO、新三板挂牌和融资、并购重组等资本市场因素，农产品期货期权市场建设、“保险+期货”、“订单农业+保险+期货(权)”等农业风险保障形式上的扩大也不可或缺。这是中国农业大灾保险发展路径的第三步。

4 仿真分析

本文使用了Matlab软件对重调度时刻点计算程序以及3种重调度方式程序进行编写。机器数为10，工件数为6，工序数为6，种群数量200，循环迭代60代，变异率取0.6，交叉率取0.8。工序可选加工机器表以及工序加工时间表如表5、表6所示。

① 原调度方案中在重调度时刻点Uij还未开始加工的工序集合。

表5 工序可选加工机器表

表6 工序加工时间表

根据表5、表6中的数据，利用遗传算法，生成原调度方案如图5所示。

图5 原调度方案

原调度方案的最大完工时间tmax为51。假设6个工件的交货期都等于最大完工时间（t1=t2=t3=t4=t5=t6=51），根据重调度时刻点计算模型计算出该调度方案的重调度时刻表，如表7所示。

创新学习的研究目标是：培训教师改变教学观念，指导学生“树立创新志向，开展创新性活动”；建立和完善创新学习理论体系；总结提炼创新学习教学思想，建构创新学习课堂教学模式，设计创新学习的教与学的策略；建构创新学习文化，主要采用文献分析、调查分析、行动研究等研究方法，通过理论建构、状态分析、策略建构及推广应用等阶段达成研究目标。

表7 重调度时刻表

假设发生扰动的工序为301工序，扰动时长为8.1，此时工序301结束时间由4延长至12.1。由重调度时刻表可知，工序301加工至时间为11时触发重调度，3种重调度方案如图6～8所示。

图6 右移重调度方案

图7 部分重调度方案

进行右移重调度的工序为105、106、203、204、205、206、302、303、304、305、306、403、404、405、406、505、506、604、605和606，共20道工序。

图8 完全重调度方案

进行完全重调度的工序为103、104、105、106、203、204、205、206、302、303、304、305、306、402、403、404、405、406、502、503、504、505、506、603、604、605和606，共27道工序。

右移重调度的最大完工时间tmax1为52.1，逾期工件数为1；部分重调度的最大完工时间tmax2为51，逾期工件数为0；完全重调度的最大完工时间tmax3为50，逾期工件数为0。

由图6可知，右移重调度方案的最大完工时间相较于原调度方案超出了1.1，恰好是扰动工序完工时间超出重调度时刻点的值。也就是说在扰动时刻点内的扰动，只需进行右移调整就不会出现逾期，间接证明了重调度时刻点的正确性。

对3种重调度方案进行决策：

F1=f1＋l·1=52.1＋L＋l

F2=f2＋l·2=51＋2l

（一）设岗定职，自主管理。在践行志愿活动时，应该努力把“管”的权利下放给学生。在工作分配当中，根据少先队员不同的特点、个性、擅长领域进行合理分工，从而使队员的个人能力得到最大程度地发挥，实现个人的成长，获得新的体验，成就展翅的雏鹰[1]。这样在志愿活动中，每个队员都有自己的服务岗位，人人有职，个个尽责，每个队员都发挥特长，各显其能，真正实现“自己的事情自己做，自己的活动自己搞”的少先队行动名言，切实提升了其自主管理能力。

F3=f3＋l·3=50＋3l

显然F3最小，故选用完全重调度方案。

5 结语

（1）针对柔性作业车间的隐性扰动，通过分析工序之间的动态关联性建立数学模型，在工序和机器两个维度上进行倒序遍历计算，得到了准确的重调度时刻点。

2010—2011年四季总降雨90h，总降雨量27.7mm，雨量年最大值为2.0 mm。该区春季4月降水偏多（1.0 mm），3月降水最少为0；夏季8月降水偏多（5.7 mm），6月降水最少（2.9 m）：秋季9月最 多（11.2 mm）；11月最少为0；冬季则降水为0。 夏秋季降水次数略多，春季降水次数较少，冬季则无降雨出现，降雨强度均以小雨为主。

（2）基于遗传算法对右移重调度、部分重调度、完全重调度3种重调度方案进行了设计，综合考虑逾期工件数、最大完工时间、对原调度方案影响程度3个指标，构建了重调度方式决策模型，在重调度触发时，可得到最合适的重调度方案。

（3）运用Matlab软件进行仿真，验证了柔性作业车间隐性扰动下重调度时刻点的准确性和重调度方式选择的有效性。