基于双层遗传编码的柔性作业车间自适应重调度研究

李 平 唐秋华 夏绪辉 陈平和

1.武汉科技大学，武汉，430081 2.湖北理工学院，黄石，435000 3.武汉神龙汽车公司技术中心，武汉，430056

0 引言

由于多种产品间存在巨大差异，故在其大规模混合生产过程中，常出现订单频繁异动、操作时间调整、机器出现故障等各种不确定事件。为应对上述不确定情形，生产调度中常用措施有实时调度、预测调度和重调度等［1－2］。

实时调度是在当前任务完成后，根据设备可用情况，在当前待完成任务集中实时地选择下一任务［3］。预测调度是在生产调度前预先估计可能发生的意外和扰动，在编制调度方案时预先设置一定的冗余时间，当生产过程中出现不确定因素时，通过调整冗余时间而主动吸收计划内的不确定扰动，按照预定调度方案完成生产任务［4－5］。比较而言，实时调度强调了不确定事件发生后的响应速度，这种调度方法灵活、易于调整，但难以关注整体生产效率，不可能实现全局最优。预测调度的主要目标是维护生产过程的稳定性，有利于在某些不确定事件发生后，保障生产有序进行，但冗余时间大小不好确定，设置过小满足不了应付扰动的要求，设置过大又易造成生产浪费和效率低下。

不同于实时调度及预测调度，重调度是在扰动发生后，以调整量最小或生产效率最大等为目标重新编制调度方案，对生产进行局部或全局重新调度［6－7］。由于重调度是在扰动发生后的系统行为，故又常被称为反应调度。重调度既避免了实时调度中不考虑全局最优的缺陷，又避免了预测调度中冗余时间的浪费，是一种兼顾全局和效率的折中方案。

目前，关于重调度的研究主要集中在单台机器、并行机器、流水车间（Flow Shop）和作业车间（Job Shop）的重调度方法、重调度对动态制造系统性能的影响等方面［8－9］。Parviz等［10］研究了在时间冲突情况下的柔性作业车间重调度方法，Sabuncuoglu等［11］探索了机器可靠性较差条件下的柔性作业车间重调度，李铁克等［12］研究了在机器故障情况下混合流水车间的重调度。上述重调度方法都只能应对单一类型的扰动，缺乏应对多种扰动类型的能力。

为此，本文以柔性作业车间为研究对象，探索对多种扰动具有自适应能力的重调度框架和算法，以期快速普适地求解重调度问题。

1 具有自适应能力的作业车间重调度

1.1 车间重调度问题描述

常见作业车间调度问题可以描述为：给定一组任务、各任务的工艺顺序、各任务中每道工序的可选机器集及其在这些机器上的加工时间，求一个调度方案，使所有任务的最大完工时间最小。

生产过程中不确定事件的发生是不可避免的，在作业车间中常见扰动类型有加工时间变动、工序优先关系改变、机器可用性变更等。由于生产过程中不确定事件类型繁多，重调度时须强调3个方面［13－16］：①对各种不同类型的扰动都具有自适应的能力；②重调度的计算时间要短，反应速度要快；③重调度后调度方案的性能损失要小。

图1所示的作业车间重调度示意图中，包含3台机器、3个任务，每个任务有2道工序，其中1（1）表示1号工件的第1道工序。假设［0，t）时间段内生产正常，t时刻出现扰动。预计产生新的调度方案需耗费计算时间为Δt，作如下规定：①只要所在机器未发生故障，在［0，t＋Δt］时刻内开始的任何工序都不作调整，避免扰乱现有生产秩序。例如1号工件的第1道工序1（1），2号工件的第1及第2道工序即2（1）和2（2），在t时刻之前它们已经开始加工，在加工它们的机器不存在故障前提下，允许它们继续完成任务，不受新调度方案影响。②从t＋Δt时刻，其他工序遵照新调度方案中加工顺序和机器分配的安排。例如1号工件的第2道工序和3号工件的第1及第2道工序须遵照重调度方案执行。

图1 重调度示意图

1.2 扰动及参数异动分析

根据上述规定，启用重调度的首要判定内容是：在所在机器未发生故障的前提下，t＋Δt时刻有哪些工序尚未开始；已经开始加工，但因所在机器发生故障而无法继续运行的工序；针对上述工序集合的变更，重调度系统中需要更新哪些参数，以保证该系统对各种扰动类型都具有适应能力。

据此将常见扰动类型分成订单异动、操作延时和机器故障三大类。在出现紧急插单或订单取消时，在受影响工序集中增加或减少新的任务、补充或取消上述任务的可用机器约束；针对操作延时的情况下，采用固定时间间隔检查的方法，根据测定结果修正操作时间；针对机器出现故障的情况，在各工件工序的可用机器集合中删除出现故障的机器，形成新的可用机器约束，同时在操作时间表中作同步更新，详细内容如表1所示。

表1 受影响工序及参数更新

在执行调度前通过更新操作时间、机器约束，可确保算法适用于不同订单变动、操作延时及机器故障等不确定扰动发生的情形。

需要注意的是，机器约束的确定是操作时间更改的前提条件，因此，在两种或两种以上扰动同时发生时，按“先机器约束后操作时间”的原则进行系统参数更新。例如在订单异动和操作延时两种扰动同时发生时，因订单异动有可能涉及机器约束的改变，所以先按订单异动规则更新机器约束和操作时间，再按操作延时规则进一步更新操作时间。

1.3 作业车间自适应重调度框架

建立在表1基础上的面向作业车间的重调度算法需要具有以下几种能力：

（1）扰动不可避免，但在指定时段内扰动可能发生，也可能不会发生，故要求算法在无扰动、有扰动两种情况下都得能到近优解，以减少生产损失；

（2）扰动类型的多样化需要算法具有一种自适应能力，可处理各种类型的扰动影响。结合表1内容，需要算法中存在确定受影响工序、系统参数更新两个模块，通过模块内参数的变动适应外在环境的改变。

为此，本文提出图2所示的作业车间自适应重调度流程，在遗传算法基础上通过利用参数、编码、算子等的重新设计，实现不同扰动类型条件下的作业车间重调度。该算法总流程如下：

图2 作业车间自适应重调度流程

（1）初始化系统参数，包括工件数、工序数、机器数、加工时间等，产生预调度方案。

（2）依照预调度方案进行生产，按照固定间隔时间检查结果及扰动类型提醒，决定是否重调度。①如果发生扰动，确定扰动类型，转步骤（3）；②如果没有扰动发生，按预调度方案继续生产。

（3）确定受扰动影响的工序集合，更新系统参数。

（4）利用下述算法生成新的调度方案，更新预调度方案，转步骤（2）。

2 基于双层编码的重调度算法设计

从上述内容可知，通过调整受影响工序集、更新相应系统参数，所调度对象便可自动调整，调度对象的属性如操作时间等也已经自动变化，所提出算法既适用于静态调度，也适用于动态重调度。从机理来说，动态重调度已可顺利实现，算法核心就是促使解空间信息中既要包含各工序的顺序，还应包含该工序所分配的机器信息。

同时，由于重调度过程中反应时间Δt非常重要，如果Δt过大，则对整个加工过程影响很大，例如会推迟完工时间并增加闲置时间等，因此，计算新的调度方案应采取速度较快的算法。包括遗传算法在内的启发式算法能够在较短时间内求得调度问题的近似最优解，故本文考虑在重调度中使用遗传算法进行计算。

算法求解过程包括编码、生成初始解、对种群进行遗传操作、在迭代过程中不断改善种群结构和解的性能，最终得到最优解。具体实施方法叙述如下。

为了简化问题的描述，对本文中出现的符号作如下约定：i＝1，2，…，I，为工件序号，I为工件总数；j＝1，2，…，Ji，为工艺序号，Ji为第i个工件的工序数为总工序个数；m＝1，2，…，M，为机器编号，M为机器总数；Kij为第i个工件的第j道工序的可用机器总数为第i个工件的第j道工序的可用机器集合；1，2，…，Kij为机器可用集合中的序号为机器的实际编号为第i个工件的第j道工序在可选机器集Φij中的机器上的加工时间集合为第i个工件的第j道工序的结束时间；Mt（s）m为第m台机器上进行的第s项操作的结束时间。

2.1 双层遗传编码和初始化

为同时描述工件的加工顺序与分配机器两种信息，采用图3所示的双层编码结构：第一层为基于工件工序的编码，称为工序码；第二层为基于可用机器选择的编码，称为机器码，总编码长度为2N。在给定的可用机器集和对应加工时间表的基础上，每一个双层编码对应一个调度方案，描述各工件每道工序所选择的机器，以及各机器上进行工件加工的先后顺序。设其中一个染色体为

其中，工序码xn（xn∈ ｛1，2，…，I｝）对应于被加工的工件号，某工件号xn在工序码中第i次出现表示该工件的第i道工序，而某一工件号在工序码中出现的累计次数即为该工件的工序数。机器码yn（yn∈ ｛1，2，…，Kij｝）是各工序可用机器集内各元素的重新编号（图3），旨在减少计算过程对系统运行空间的需求，加快运行速度。注意，每一个xn对应一个集合｛y1，…yn…，yN｝，根据集合｛x1，…xn…，xN｝与｛y1，…yn…，yN｝的对应关系，即可确定每个工件各道工序的执行机器。

图3 双层染色体编码示意图

在图3所示案例中，某作业车间有3台机器，需加工2个工件，且各工件均含有2道工序。各工件每道工序的可用机器表及加工时间如图3所示。

假设某个染色体编码为（1，2，1，2，1，2，2，1），其中前四位（1，2，1，2）为工位码，直接确定了2个工件共4道工序的执行顺序：工件1工序1、工件2工序1、工件1工序2、工件2工序2。编码后四位（1，2，2，1）为机器码，联立可用机器集共同确定执行各工序的机器为：工件1的第1、2道工序分别由机器1和3加工，工件2的第1、2道工序分别由机器3和2加工。该染色体编码对应的加工过程甘特图见如图4。

图4 遗传编码与加工过程的对应

2.2 解码方法和适应度函数设计

假设根据调度方案的排序，第i个工件第j道工序恰好被安排为第m台机器上的第s个任务，则有如下公式：

即在上述的假设中，第i个工件的第j道工序的完成时间等于第i个工件第j－1道工序的完成时间加上第m台机器上第s－1个任务的完成时间的最大值，或第i个工件第j道工序在所分配机器上的加工时间。 为了表达形式的方便，记分别表示第i个工件与第m台机器的可开始时间。

2.3 选择和交叉操作设计

选择操作采用轮盘赌的方法依概率选择适应度较强的染色体参与遗传操作。概率的计算由适度函数值决定，表达式如下：

交叉操作首先从种群中随机选出两个染色体，对染色体的第一层随机选择交叉点进行交叉。交叉操作分为两步：参与交叉的两个染色体的第一层在交叉点前后互换基因；对交叉后的染色体进行局部调整，调整的原则为使其所表达的工件数及工序数与问题条件相符。如图5中的染色体中第一层基因位置里1、2、3各出现了3次，表示对应的问题是有3个工件，每个工件有3道工序的Job Shop问题。但交叉后，出现了有的工件工序变多，有的工件工序变少的问题，这时调整的方法是从工序较多的工件号中随机抽取一个使之变成工序变少的工件号，并从该工件可选机器中选择一个。图5演示了一个具体的交叉操作过程。图6为调整步骤示意。

图5 工序码交叉

2.4 变异算子设计

变异操作分为工序码变异和机器码变异两步。工序码变异首先随机选择两个变异位置，然后将第一层工序码和第二层机器码的对应位置上的基因进行互换。图7演示了一个具体的工序码变异操作过程。

图6 工序码调整

图7 工序码的变异设计

机器码变异是在第二层机器码中随机选择一个变异位置，将该位置对应的可选机器序号集中随机选择一个序号，替换原序号值，如图8所示。

图8 机器码的变异设计

2.5 种群的精英保留策略

在本算法中采取精英保留策略，即用当前代中适应度值最好的个体替换适应度值最差的个体，在进行遗传步骤的时候最好个体不仅以更大的概率参与遗传操作，并且直接进入下一代种群。

3 算例分析

给定具有6个工件、每个工件有6道工序、可用机器数为10的某作业车间调度问题。已知各工件每道工序的可选机器集合（如表2中中括号所示），及其在对应机器上的加工时间（对应于表3中中括号内容）。

表2 各工序可选机器表

表3 各工序加工时间表

采用MATLAB编码编制完成上述遗传算法。根据本问题的规模和计算复杂度，通过多次实验对比，在综合考虑计算效率和求解时间的前提下，设置遗传代数为50、选择率为0.8、交叉率为0.8、工序码变异率和机器码变异率均为0.1，运行该算法得到遗传算法迭代图和预调度方案分别如图9、图10所示。

图9 遗传算法迭代图

图10 预调度方案甘特图

从图9中可以看出，算法的收敛性较好，从第30代开始种群的最优解就稳定在47s。在最优预调度方案的甘特图中，表示工序的矩形中的数字i0j表示该矩形对应于第i个工件的第j道工序。从图中可见所求最大完工时间的较优值为47s，在10台机器中设备运用率最高的为机器5，最后完工的工件是6号，由于201和303占用了机器4号和7号，完工时间不可能更为提前。算法的运行时间为3s，低于预先估计的1min，显示该算法效率较高。

当不确定发生时，以机器故障为例考虑如下情形的扰动：假设在生产进行到第14min时编号为9的机器突然发生意外，以至于在后续的生产过程中无法继续工作，求新的调度方案，新调度方案的计算时间预设为1min。根据本文中前述的原则可以确定受影响的任务工序集合与更新后的参数。发生扰动后，需要在新的初始条件下重新计算后续工件工序的调度方案。根据本例中9号机器发生故障的情况，更新工序可选机器表和工序加工时间表的原则为：未完成工序中涉及第9台机器的加工时间改为无穷大。发生扰动后的工件可选机器和在各机器上的加工时间如表4和表5所示。其中，“※”表示在重调度中不需要考虑的工件工序的机器可用情况及加工时间；“inf”表示加工时间为无穷大。

表4 9号机发生故障后的可选机器更新表

表5 9号机发生故障后工序加工时间更新表

在此基础上，计算出后续工件工序的最佳调度方案，新调度方案中的完工时间为55s，此案例中新调度方案的实际计算时间为3s，低于预先估计的反应时间，计算得到的新调度方案如图11所示。

图11 9号机故障发生后的重调度方案

在本例中，通过适应性的双层编码遗传算法解决了机器故障情形下的重调度问题，得到了Job Shop问题在扰动情况下的最优解，对于其他类型的扰动，可以使用同样方法进行重调度方案

本文在对400个不同规模的Job Shop重调度问题进行仿真运算的基础上试验和分析所应用的适应性算法的效率，仿真问题中的工件个数和工序数在6至25之间自由组合，每道工序可选择的机器数设为2，即问题的规模介于72至1250之间。运算的结果如图12及图13所示，从图12中可以看出所有问题的重调度运算时间均小于80s，其中绝大部分的时间小于60s。图13为运算时间的等值分布图，从图中可以看出不同规模问题的运算时间分布，时间大于60s的问题占问题总数的2%以下。因此，本文中所设置的1min反应时间对于大部分Job Shop问题的重调度来说可行。的求解。

Job Shop问题的规模可由两个因素确定：总工序的个数和每道工序可选择的机器数。在不失一般性的情况下，可按照如下公式来定义Job Shop问题的规模：

图12 运算时间分布图

图13 运算时间等高线图（s）

4 结论

重调度通过重新编制调度方案来应对不确定扰动，具有同时保障全局较优和生产稳定的能力。本文以柔性作业车间为研究对象，提出了具有自适应能力的重调度框架及算法。

仿真实验证明，以各工件每道工序的可用机器集及相应加工时间为系统参数，可有效表征柔性作业车间调度中常见扰动类型；动态调整上述系统参数，即可适应生产过程中订单异动、操作延时和机器故障等3种类型扰动；基于双层编码的遗传算法具有简单和高效的特点，可在有限的反应时间内求到问题的近优解；结合自适应重调度和双层编码遗传算法，对不同规模问题都能得到满意的结果。

后续工作将针对柔性作业和混合流水车间，进一步研究基于其他高效算法的适应性重调度方法。

［1］陈国权.企业实施敏捷制造的过程框架［J］.清华大学学报，1999，14（2）：56－59.Chen Guoquan.Framework of Agile Manufacturing in Enterprise［J］.Journal of Tsinghua University，1999，14（2）：56－59.

［2］吴秀丽，李苏剑，杜彦华.柔性作业车间多品种小批量调度算法研究［J］.中国机械工程，21（4）：424－429.Wu Xiuli，Li Shujian，Du Yanhua.Research on Batch Scheduling Problem in a Flexible Job Shop［J］.China Mechanical Engineering，21（4）：424－429.

［3］Sugimura N，Tanimizu Y，Iwamura K.A Study on Real－time Scheduling for Holonic Manufacturing System ［J］.Journal of Manufacturing Systems，2004，33（5）：467－475.

［4］Li Z，Ierapetritou M.Process Scheduling under Uncertainty：Review and Challenges［J］.Computers and Chemical Engineering，2008，32（4／5）：715－727.

［5］Leon V J，wu S D，Storer R H.Robustness Measures and Robust Scheduling for Job－shop［J］.IEEE Transactions，1994，26（5）：32－43.

［6］张沙清，陈新度，陈庆新，等.基于改进多目标微粒群算法的模具多项目反应调度［J］.中国机械工程，2011，22（10）：1173－1179.Zhang Shaqing，Chen Xindu，Chen Qingxin，et al.Reactive Scheduling for Multiple Mould and Die Projects Based on Improved Multi－objective Particle Swarm Optimization［J］.China Mechanical Engineering，2011，22（10）：1173－1179.

［7］Abumaizar R J，Svestka J A.Rescheduling Job Shops under Random Disruptions［J］.International Journal of Production Research，1997，35（7）：2065－2082.

［8］Wu S D，Storer R H，Chang P C.One－machine Rescheduling Heuristics with Efficiency and Stability as Criteria［J］.Computers and Operations Research，1993，20（1）：1－14.

［9］李莉，乔非，吴启迪.半导体制造重调度研究［J］.中国机械工程，2006，17（6）：612－616.Li Li，Qiao Fei，Wu Qidi.Research on Rescheduling for Semiconductor Wafer Fabs［J］.China Mechanical Engineering，2006，17（6）：612－616.

［10］Parviz F，Fariborz J，Jamal A.Flexible Job Shop Scheduling with Overlapping in Operations［J］.Applied Mathematical Modeling，2009，33（7）：3076－3087.

［11］Sabuncuoglu I，Karabuk S.Rescheduling Frequency in an FMS with Uncertain Processing Times and Unreliable Machines［J］.Journal of Manufacturing Systems，1999，18（4）：268－283.

［12］李铁克，肖拥军，王柏琳.基于局部性修复的HFS机器 故 障 重 调 度 ［J］.管 理 工 程 学 报，2010，4（3）：45－49.Li Tieke，Xiao Yongjun，Wang Bailin.HFS Rescheduling under Machine Failures Based on Local Repair［J］.Journal of Industrial Engineering／Engineering Management，2010，4（3）：45－49.

［13］任海英，邹艳蕊.基于多Agent的柔性作业车间预先／重调度系统［J］.武汉理工大学学报（信息与管理工程版），2012，34（1）：69－74.Ren Haiying，Zou Yanrui.A Flexible Job Shop Pre／re－scheduling System Based on Agent［J］.Journal of WUT（Information ＆ Management Engineering），2012，34（1）：69－74.

［14］Wh H H，Li R K.A New Rescheduling Method for Computer Based Scheduling Systems［J］.International Journal of Production Research，1995，33（8）：2097－2110.

［15］Leon V J，Wu S D，Storer R H.Games Theoretic Control Approach for Job Shops in the Presence of Disruptions［J］.International Journal of Production Research，1994，32（6）：1451－1476.

［16］Abumaizar R J，Svestka J A.Rescheduling Job Shops under Disruptions［J］.International Journal of Production Research，1997，35（7）：2065－2082.