设备故障驱动的作业车间生产任务重调度方法研究

刘 轩，尚 鋆，白 翱

（1.中国工程物理研究院 机械制造工艺研究所，绵阳 621900；2.中国核电工程有限公司，北京 100840）

设备故障驱动的作业车间生产任务重调度方法研究

刘 轩1,2，尚 鋆1，白 翱1

（1.中国工程物理研究院 机械制造工艺研究所，绵阳 621900；2.中国核电工程有限公司，北京 100840）

现代作业车间中，因设备故障导致原生产计划无法执行的情况时有发生，影响了车间生产任务的正常执行。针对此问题，首先分析了设备故障情况下的动态约束条件，并进行了业务建模和数据建模，其次采用混合集合规划理论及其支持工具，结合滚动窗口重调度模式，建立了作业车间重调度模型，包括其主要约束、优化目标、求解算法等。最后，通过某机械加工车间的生产实例进行了应用验证，求解结果表明了本方法的可行性和有效性。

作业车间；设备故障；重调度；混合集合规划；自然约束语言；智能制造

0 引言

作业车间中经常出现各种动态的扰动或异常事件，这些扰动或异常事件会对原生产计划的正常执行产生不利影响，严重时甚至造成生产任务不能按期完工和交付，给企业带来订单超期交付而被惩罚的损失。因此，当扰动或异常事件发生时，根据当前车间任务的实时执行状态和扰动影响程度，对原有的生产计划进行重新调度，以生成新的生产计划是保证车间生产任务正常执行的关键所在。设备故障是现代作业车间中最常见的扰动之一，由设备故障引起的停机问题将导致原来安排到该设备上生产的工序无法顺利执行，因此，研究设备故障条件下的调度对于提高整个制造系统的稳定性具有重要意义。

目前，国内外学者对于设备故障重调度问题已经有了一些研究[1～3]，其中采用的求解方法多以遗传算法、粒子群算法等智能优化算法为主。混合集合规划（Mixed Set Programming，MSP）[4]理论结合了运筹学、启发式规则以及智能推理等诸多方法的优势，且已独立发展了对应的支持语言系统——自然约束语言（Natural Constraint Language，NCL）[5]，可更加有效、方便地求解工程中复杂的组合优化问题。目前MSP已在车间生产调度领域有了一些研究与应用[6～8]，初步展现其在大规模工程优化问题方面的诸多优势。

针对作业车间设备故障引起的重调度问题，本文将采用混合集合规划的理论进行建模和求解，通过增加动态约束条件和引入动态任务集的方法，在基本静态调度模型基础上设计了一种设备故障重调度方法，以便发生设备故障时能够快速生成新的生产计划，指导不同工序生产任务的落实和执行，从而保证车间生产过程的平稳、高效。

1 设备故障重调度动态约束分析

在设备故障重调度问题中，存在一些除静态调度常见约束以外的重调度特有的动态约束条件。

图1是设备故障重调度的示意图，为设备-工序甘特图。图中共列出了三台设备——设备1、设备2、设备3，三个作业——作业A、作业B、作业C，其中作业A有三道工序，作业B有三道工序，作业C有两道工序。图中箭头所指位置为设备2发生故障时刻，此时刻就作为重调度的节点时刻。

首先参照图1定义三种任务的状态：

1）重调度任务

在重调度节点时刻未完工且需要进行重调度的任务。受到设备2故障影响需要重调度的任务有作业B的工序1未完工部分（如图1中右阴影所示）及其所有后续工序（作业B的工序2、3）、作业A的工序2及其后继工序（作业A的工序3）、作业C的工序2。

图1 设备故障重调度示意图

2）正加工任务

在重调度节点时刻未受到设备故障影响的已经开始加工但仍未完工的任务。这一类任务不需要进行重调度，但是会对当次重调度产生影响。如图1中作业A的工序1（左阴影部分为未完工部分）。

3）已调度任务

在重调度节点时刻未受到设备故障影响且未完工的任务。这一类任务也不需要进行重调度，但是会对当次重调度产生影响。如图1中作业C的工序1。

定义完任务的状态，就开始对重调度的动态约束条件进行分析，总结出以下五种动态约束条件：

1）正加工任务次序约束

图1中作业A的工序1为“正加工任务”，需要重调度的作业A的工序2是其后继工序，所以其开工时间必须在该“正加工任务”完工之后。本文中将这种约束称为“正加工任务次序约束”。

2）正加工资源占用约束

图1中作业A的工序1为“正加工任务”，该工序占用了重调度后设备1上的一部分可用时间（即图1中左阴影部分），因此设备1上的这部分时间就不能再安排其他任务（如作业B的工序2）。本文中将这种约束称为“正加工资源占用约束”。

3）已调度任务次序约束

图1中作业C的工序1为“已调度任务”，需要重调度的作业C的工序2是其后继工序，所以其开工时间必须在该“已调度任务”完工之后。本文中将这种约束称为“已调度任务次序约束”。

4）已调度资源占用约束

图1中作业C的工序1为“已调度任务”，该工序占用了重调度后设备3上的部分可用时间，因此设备3上的这部分时间就不能再安排其他任务（如作业B的工序3）。本文中将这种约束称为“已调度资源占用约束”。

5）资源可用约束

每一次重调度时，较之上一次调度都过去了一段时间，这时就需要将已经过去的这段时间从资源的可用时间中删除掉。更新之后的资源可用信息构成准确的“资源可用约束”。

2 业务建模

2.1 约束条件

首先根据作业车间生产调度问题的三要素（资源、作业、工序）梳理基本的静态调度约束条件如下：

1）资源类约束：包括工作日历约束和资源占用约束。

2）作业类约束：包括最早开工时间约束、最晚完工时间约束、作业优先级约束、作业装配等级约束。

3）工序类约束：包括加工次序约束、单次加工约束、可用资源约束、工时约束。

在动态调度问题中，还要考虑上文中的五种动态约束条件：正加工任务次序约束、正加工资源占用约束、已调度任务次序约束、已调度资源占用约束、资源可用约束。

动态约束条件是随着时间和生产系统状态的不断变化而相应发生改变的，这是其不同于静态调度约束条件的根本所在。

2.2 动态任务集

根据生产任务的几种不同状态，分别定义不同的动态任务集如下：

1）待调度任务集：存储当次参与调度的任务；

2）任务总集：存储所有未开工的任务；

3）正加工任务集：存储重调度时刻的正加工任务。

2.3 优化目标

在面向订单的生产环境中，按照承诺给客户的时间节点交付产品是车间生产最重要的目标，因此本文选择最小化作业延迟时间总量作为生产计划重调度的优化目标。

3 数据建模

3.1 数据结构设计

需要建立资源、作业、工序、计划四类表，每一类包括的数据表分别如表1、表2、表3和表4所示。

表1 资源类表

表2 作业类表

表3 工序类表

表4 计划类表

每一类表的具体数据结构分别如表5、表6、表7、表8所示。

表5 资源类表数据结构

表6 作业类表数据结构

表7 工序类表数据结构

表8 计划类表数据结构

3.2 建立动态约束集和动态任务集

每个动态任务集分别由一个作业类表和一个工序类表组成：JOB表和TASK表组成“待调度任务集”，JOBALL表和TASKALL表组成“任务总集”，JOBFIXED表和TASKFIXED表组成“正加工任务集”。如表9所示。

表9 动态任务集的组成

不同的表存储着不同的约束信息，动态约束集由资源类表或计划类表组成：PLANFIXED表储存“正加工任务次序约束”信息，RESOURCEFIXED表储存“正加工资源占用约束”信息，PLAN表储存 “已调度任务次序约束”信息，RESOURCEPLAN表储存“已调度资源占用约束”信息，RESOURCE表储存“资源可用约束”信息。如表10所示。

4 NCL建模与求解

4.1 约束条件建模

下面依次对业务建模中梳理的静态和动态约束条件进行数理逻辑的建模。

表10 动态约束集的组成

4.2 优化目标建模

本文中选取最小化作业延迟时间总量作为优化目标。

4.3 求解算法设计

选择完优化目标，就开始进行相应的求解算法的设计。本文选取最常用的最小化松弛度准则和顺序搜寻准则作为查询准则，枚举方式选择下界优先边界枚举。将算法求解过程分为两个阶段，即先将工序安排到资源上，再确定每个工序的开工时间。

经过求解算法的两个阶段，即可得到每道工序在相应资源上的开工时间和完工时间。

5 设备故障重调度的实现

设备故障重调度的流程图如图2所示。

图2 设备故障重调度

在更新“正加工任务次序约束”、“正加工资源占用约束”和“资源可用约束”信息之后，设备故障重调度的具体实现步骤如下：

Step1：依据计划结果表（PLAN表）中的信息，从“任务总集”中选出要重调度的任务，复制到“待调度任务集”中，然后将这些选出的需要重调度的任务对应的工序从PLAN表中删除，但不删除这些任务在“任务总集”中的信息。

此时PLAN表中存储了准确的“已调度任务次序约束”信息。

Step2：根据PLAN表更新已调度资源占用表（RESOURCEPLAN表）的信息，从而更新了“已调度资源占用约束”。

Step3：在约束的条件下进行调度，并输出计划结果到PLAN表中。

6 实例验证

以某机加车间2015年1月份的生产任务作为实例进行验证。

运行环境：处理器为AMD Opteron™ Processor 6168 1.90GHz（双核处理器），安装内存（RAM）为32GB，Windows操作系统版本为Windows Server 2008 R2 Enterprise，POEM优化计算平台版本为Academic Version 3.0。

假设2015年1月22日（周四）9:00设备B08发生故障，预计到2015年1月27日17:30可排除故障。

以故障发生时刻为重调度节点（2015年1月22日9:00），故障期间涉及到的需要重调度的作业有4个，共21道工序。并且资源故障发生时刚好有工序在该设备上进行加工，为作业93238_457148_859472的第二道工序id=2400185，需要用剩余工时（177分钟）修正原有工时（600分钟）。

B08设备故障重调度计划的结果具体指标如表11所示。

表11 设备故障重调度计划结果

从表中结果可以看出，所有受到设备故障影响进行重调度的任务都能够按时完工，作业按期完工率为100%，证明了设备故障重调度方法良好的重调度效果；运算时间为2.6秒，完全满足生产实际的要求。

图3和图4分别截取了设备B08发生故障进行重调度之后一周范围内的故障前和故障后的调度计划的资源-

【】【】工序甘特图。通过与图3进行对比，可以从图4中看出，受到B08设备故障影响进行重调度的任务（着色）都被很好地重新安排到了原计划（未着色）的空闲时段，重调度效果良好。

Production task rescheduling method for job shop based on equipment failure

LIU Xuan1,2, SHANG Jun1, BAI Ao1

TH166

A

1009-0134(2016)12-0026-06

2016-08-13

中国工程物理研究院机械制造工艺研究所“十二五”预研课题（K814-13-Y）；中国工程物理研究院科技专项（9120601）

刘轩（1990 -），男，河北唐山人，硕士研究生，研究方向为生产计划与调度理论及应用。