考虑设备故障的Job Shop调度问题研究

吴正佳 望 芸 付先旺 何海洋 华 露

(1. 三峡大学 机械与动力学院， 湖北 宜昌 443002； 2. 中国电建集团 贵阳勘测设计研究院有限公司， 贵阳 550081)



考虑设备故障的Job Shop调度问题研究

吴正佳1望 芸1付先旺1何海洋2华 露1

(1. 三峡大学 机械与动力学院， 湖北 宜昌 443002； 2. 中国电建集团 贵阳勘测设计研究院有限公司， 贵阳 550081)

在实际的企业生产加工过程中存在许多扰动因素，设备故障就是其中的典型．对于Job Shop中的设备故障问题，传统的调度方法主要是完全重调度和直接右移，但是对系统的稳定性影响较大且效率不高．基于此，文章提出了一种新的调度策略—解码右移策略．根据故障出现时间早晚、故障修复时间长短以及问题规模大小设计了8组仿真实验，并构建了偏离度和延迟度两个评价指标对该策略的有效性进行验证．实验结果表明解码右移调度策略的偏离度相比于整体右移策略降低了41.45%，相比于完全重调度策略降低了69.01%；其延迟度相比于其它两种策略有一定优势．

Job Shop； 设备故障； 解码右移策略； 仿真

近10年来，考虑设备故障的Job Shop调度问题研究已经取得了一些进展[1-4]．王超[5]认为可以将设备故障按大小分为两种情况，当出现大故障时，将故障设备直接退出调度；当出现小故障时，等待设备修复后再投入生产．刘琳[6]提出了空闲时间插入法，首先生成一个初始调度顺序，然后根据工件和故障的特征插入相应的空闲时间，以吸收故障对原调度的影响．Alpay[7]则认为，在扰动发生时，如果只是重新调度直接或间接受扰动影响的工件，能够有效地减少生产周期，同时也能减少重调度与预调度的偏差．张利平[8]设计出带空闲时间的预-反应策略，该策略对小规模的新工件车间有较好的效率和稳定性．对于Job Shop调度过程中出现的设备故障问题，现有的解决方法主要分为直接右移[9]和完全重调度两种[10]，但是这两种策略的调度效果并不令人满意．完全重调度由于要重新对所有工件进行调度，导致系统的稳定性很低；直接右移由于要等待设备修复完成，造成了时间的浪费，效率不高．

基于上述分析，本文提出了一种解码右移调度策略，该策略的主要思路为：从故障发生时刻开始对预调度方案重新解码，保证工件的加工顺序不变，只是将工件向右移动一定距离，以获得最优调度方案．设计实验仿真将解码右移策略、直接右移和完全调度策略进行对比，验证解码右移调度策略的有效性，为实际的生产调度提供一定的指导意见．

1 Job Shop调度问题模型

Job Shop调度一般描述为n个工件{J1，J2，…，Jn}在m台设备{M1，M2，…，Mm}上加工，每一个工件有p道工序，用Oij表示第i个工件的第j道工序，各工序之间的加工路线相互独立．表1是3个工件在3台设备上加工的Job Shop调度问题的实例．

表1 某Job Shop调度问题的加工时间表

Job Shop的调度目标是确定各个设备上每个工件的加工顺序，并确定每道工序开始加工的时间，使得系统的调度目标达到最优．本文结合生产实际，从最大完工时间f1和拖期惩罚f2两个方面来构建目标函数：

(1)

(2)

(3)

其中，Ck是第k台设备上所有工件完成加工的时间，Ci是第i个工件所有工序完成加工的时间，Di是工件Ji的交货期．如果工件Ji完成加工的时间大于交货期，则需要受到拖期惩罚，用δi表示拖期惩罚系数．式(3)表示总目标f为两个目标函数值求和．

此外，在加工的过程中需要满足以下约束：1)各个工件的加工路线是固定的，不能做任何改变；2)在任意时刻，一台设备只能进行一道工序的加工；3)在任意时刻，一个工件只能占用一台设备加工；4)同一工件不同工序间应该有先后顺序的约束．

2 考虑设备故障的解码右移策略

解码右移策略的关键是确定故障发生时设备的工件是否完成了解码．如果工件已完成解码，则保持其加工信息(工件开始加工的时间等)不变；如果工件未完成解码，则按照原调度方案继续解码，只是故障发生后第一个加工的工件的开始加工时间有所改变．本文对上述两种情况分别进行讨论，流程图如图1所示．

图1 解码右移调度策略流程图

假设故障发生时刻为T，修复时间r．如果故障设备M正在加工，设加工工件Xij，其预调度方案中的开始加工时间SMxij，完工时间CMxij；如果发生在空闲时间，假设设备M发生故障后第一个加工的工件是Yij，其预调度方案中的开始加工时间是SMyij．

1) 故障发生时设备M正在加工

假设所有工序的加工是可间断的，则以故障点为分界点，工件Xij后续部分的开始加工时间Ts为：

(4)

此工件在故障设备上剩余部分的加工时间tsx：

(5)

(6)

该状态下故障设备的下一个工件最早开始加工时间Tsij为：

(7)

由上式可知，若下一个加工的工件是其第一道工序，则最早开始加工时间相当于在前一个工件的完工时间上延长设备修复时间长度；若下一个加工的工件不是其第一道工序，则需将前一个工件的实际完工时间与下一个工件的前道工序完成时间Tei(j-1)作比较．

2)故障发生时设备M为空闲

故障发生时刻到下一个工件开始加工之间的时间间隔tsy为：

(8)

(9)

由上式可知，在此状态下，下一个工件的最早开始时间相当于在故障时刻延长了修复时间的长度．

为了验证此调度策略的可行性，本文从企业最为关注的调度稳定性和调度效率两个角度出发，构建偏离度和延迟度两个评价指标对调度结果进行评价．

①偏离度，用来表示调度策略的稳定性：

(10)

②延迟度，表征调度策略的效率：

(11)

3 遗传算法在Job Shop调度问题中的应用

遗传算法(genetic algorithm , GA)在1975年被美国的Holland教授首次提出，他借鉴了生物界适者生存、优胜劣汰的遗传机制，通过模拟自然进化过程来搜索最优解．遗传算法由于其全局优化搜索能力强、搜索效率高等优势被广泛应用于Job Shop调度问题的求解中．针对Job Shop调度问题的特点，本文采用基于工序的编码方式，随机生成初始解，经过轮盘赌选择、单点交叉与插入变异，通过判断是否满足优化规则来终止计算，得到最终调度方案．算法流程如图2所示．

图2 遗传算法流程图

Step 1：设计编码与解码

编码和解码是使用遗传算法的首要问题，它是指染色体与调度解之间的转换．由于不同的工序对应不同的加工时间，所以在设计编码方式时要基于工序，染色体上的每一个基因代表每一道工序．在编码染色体中，用工序所在的工件号来表示，工件号第k次出现即表示该工件的第k道工序．以表1中的加工实例，若设计的染色体为1-2-2-3-1-2-3-1-3，则对应工序的加工顺序为O11-O21-O22-O31-O12-O23-O32-O13-O33．

解码即根据染色体得到工序的加工顺序．对于Job Shop调度问题，当对某一道工序进行加工时，需要满足两个条件：一是该工序的前道工序已经加工完成；二是该加工机器已完成上一个工件的加工．

Step 2：初始化

遗传算法的第一步是产生初始染色体，即初始化．选择应用广泛、操作简单的随机初始化方式．随机生成初始加工顺序，即为初始染色体．

Step 3：选择操作

设计适应度函数对染色体的适应度值计算之后，就要选择适应度较好的个体遗传．目前研究中最常见的有轮盘赌与锦标赛方法，由于轮盘赌方式运用了概率的思想，适应度大的个体被选择的几率较大，很好地印证了生物学中“适者生存”的思想，故使用轮盘赌方法进行选择．

Step 4：交叉操作

为了得到适应度更高的个体，在选择之后通常还要进行交叉操作．本文采用选择单点交叉方式，在父代染色体中随机产生一个点，以点为界将染色体分为J1和J2两部分，子代C1继承父代P1的J1部分和父代P2的J2部分，C1则继承P2的J1部分和P1的J2部分．

图3 单点交叉示意图

Step 5：变异操作

变异的目的是加快收敛速度，同时避免陷入局部最优．设计变异方法时应该考虑到越大的扰动对原有调度解的影响越大，越能帮助跳出局部区域，所以较好的变异方式是能较大地改变原有染色体的排列方式．本文采用插入变异方式，随机选择一段基因插入到染色体中的一个随机位置，染色体中其它基因位置保持不变．

图4 插入变异示意图

4 实验仿真

4.1 参数设定

1)问题规模：问题分为小规模和大规模两种，分别是6×6和10×10标准案例．

2)扰动时间：扰动时间分为早和晚，其中较早时间以总完工时间1/3时刻为例，较晚时间以总完工时间2/3时刻为例．

3)扰动程度：用故障修复时间来衡量扰动程度，分为高(修复时间为完工时间的30%)和低(修复时间为完工时间的3%)两种．

运用控制变量法分别固定以上3种变量，共设计了8组实验，实验内容见表2．

表2 仿真实验内容

4.2 仿真结果

以实验1为例，使用遗传算法对6×6规模问题进行求解，生成甘特图如图5所示．

图5 6×6初始调度甘特图

假定故障设备为2，故障时刻为2，修复时间为16，使用解码右移策略进行调度，遗传算法求解，得到的甘特图如图6所示．

图6 6×6解码右移策略甘特图

分别使用3种调度策略对8个实验进行调度仿真，得到的结果见表3和表4．

表3 不同调度策略仿真结果(偏离度)

表4 不同调度策略仿真结果(延迟度)

1)对比不同组实验的结果

不论是偏离度还是延迟度，可以发现都是第3组的实验值最小，第6组的实验值最大，这说明偏离度和延迟度都是随着问题规模的由小到大、扰动时间的由晚到早、扰动程度的由低到高而增大的．

为了进一步验证上述结论，分别比较两个表中的1和5，2和6，3和7，4和8组实验，发现在相同的扰动时间和干扰程度下，大规模问题的偏离度和延迟度均高于小规模问题，这是因为大规模问题所要调度的工件较多，所以会对其产生较大的影响；比较1和3，2和4，5和7，6和8组实验，发现在相同的调度规模和干扰程度下，扰动出现越晚，偏离度和延迟度越小，这是由于扰动出现晚意味着故障发生在靠后的阶段，前面已经加工完成了很多工件，需要移动的工件较少；比较1和2，3和4，5和6，7和8组实验，发现在相同调度规模和扰动时间下，干扰程度高的偏离度和延迟度要高于干扰程度低的，由于干扰程度低即设备出现故障后能够很快得到修复，所以对调度造成的影响较小．

2)对比不同调度策略的结果

不同调度策略之间的偏离度有很大的差别，解码右移策略的偏离度明显优于其它两种策略，其平均值相对于整体右移策略降低了41.45%，相对于完全重调度策略降低了69.01%；然而不同调度策略之间的延迟度差别不是很大，解码右移策略的延迟度和其它两种策略相比有一定的优势．

5 结 论

1)相比于静态调度，考虑设备故障的实时调度能够根据车间的实际加工情况迅速做出反应，从而达到较高的效率和稳定性．

2)在相同的扰动时间和干扰程度下，规模较大的调度出现设备故障时受到的影响更大；在相同的调度规模和干扰程度下，设备故障出现较早对调度系统会造成更严重的影响；在相同调度规模和扰动时间下，干扰程度高的设备故障造成的影响更大．

3)在效率一定的情况下，解码右移策略的稳定性相比于其它两种策略都有很大的优势；在稳定性一定的情况下，解码右移策略的效率相比于其它两种策略有一定优势．

[1] Rahmati Seyed Habib A, Zandieh M. A New Biogeography-Based Optimization (BBO) Algorithm for the Flexible Job Shop Scheduling Problem[J]． International Journal of Advanced Manufacturing Technology， 2012, 58(9-12)：1115-1129．

[2] Rajabinasab Amir, Mansour Saeed. Dynamic Flexible Job Shop Scheduling with Alternative Process Plans： an Agent-based Approach[J]．International Journal of Advanced Manufacturing Technology， 2011, 54(9-12)： 1091-1107．

[3] Moradi E, Ghomi S， Fatemi M T， et al． An Efficient Architecture for Scheduling Flexible Job-shop with Machine Availability Constraints[J]． International Journal of Advanced Manufacturing Technology， 2010, 51(1-4)：325-339．

[4] Al-Hinai Nasr, ElMekkawy T Y. A Efficient Hybridized Genetic Algorithm Architecture for the Flexible Job Shop Scheduling Problem[J]． Flexible Services and Manufacturing Journal 2011, 23(1)：64-85．

[5] 王 超. 基于Petri网的Job Shop调度问题研究[D]．北京：北京交通大学,2011．

[6] 刘 琳. 动态不确定环境下生产调度算法研究[D]．上海：上海交通大学,2007．

[7] Alpay S, Yuzugullu N. Dynamic Job Shop Scheduling for Missed Due Date Performance[J]． International Journal of Production Research, 2009, 47(15)： 4047-4062．

[8] 张利平. 作业车间预反应式动态调度理论与方法研究[D]．武汉：华中科技大学,2013．

[9] Kamoun H,Sriskandarajah C.The Complexity of Scheduling Jobs in Repetitive Manufacturing Systems[J]． European Journal of Operation Research.1993, 70(3)：350-364．

[10] Jain A K， Elmaraghy H A. Production Scheduling-Rescheduling in Flexible Manufacturing[J]． International Journal of Production Research, 1997, 35(1)：281-309．

[责任编辑 张 莉]

Research on Job Shop Scheduling Problem Considering Machine Faults

Wu Zhengjia1Wang Yun1Fu Xianwang1He Haiyang2Hua Lu1

(1. College of Mechanical & Power Engineering, China Three Gorges Univ., Yichang 443002, China； 2. Guiyang Survey & Design Institute Co., Ltd., China Electric Power Construction Group, Guiyang 550081, China)

There are many disturbing factors in the actual production process; the machine fault is one of the typical factors. To solve the machine failure of Job Shop problem, the traditional scheduling methods are completely rescheduling and direct right. However, they have greater impact of the system and low efficiency. In light of this, the paper proposes a new scheduling strategy, i.e. decoding right scheduling. 8 simulations are designed about downtime, trouble-shooting time and scale of the problem and two evaluation of deviation and delay are constructed in order to verify the effectiveness of the strategy. The results show that the deviation of decoding right scheduling decreases 41.45% compared with direct right strategy and decreases 69.01% compared with completely rescheduling strategy; and its delay has certain advantages compared with other two methods.

Job Shop; machine fault; decoding right strategy; simulation

10.13393/j.cnki.issn.1672-948X.2016.05.019

2016-05-20

湖北省自然科学基金资助项目(ZRY2014001091)

吴正佳(1964-)，男，教授，博士，研究方向为先进制造企业信息系统分析与集成、智能算法理论、设备综合管理与检测．E-mail：zjwu@ctgu.edu.cn

TH166

A

1672-948X(2016)05-0098-05