基于故障处理算法的动态多目标FJSP研究*

潘 颖，高天一，薛冬娟，谢忠东

(大连海洋大学 机械与动力工程学院，辽宁 大连 116023)

基于故障处理算法的动态多目标FJSP研究*

潘 颖，高天一，薛冬娟，谢忠东

(大连海洋大学 机械与动力工程学院，辽宁 大连 116023)

针对柔性作业车间调度(FJSP)过程的多目标、动态和信息不确定等特征，文章提出了一种实时调整的FJSP动态调度方法。首先，建立了FJSP动态仿真求解模型，该模型受自适应控制启发，并结合鲁棒调度和预见调度，求解效果稳定而高效；同时，该模型中设置了基于自适应遗传算法的仿真求解器，并通过故障处理算法实现预见功能。最后，通过一企业实例验证了文中所提算法的有效性和实用性。

多目标柔性作业车间调度；动态调度；仿真求解模型；故障处理算法

0 引言

生产调度是一系列生产活动的计划，用于指导生产过程。但是，实际制造系统比如存在一些不可预期的现象或随机扰动，会有各种实时动态事件发生，如到达紧急订单、工件交货期突化和加工设备突发故障等，可见实际生产系统具有本质上的不确定性与动态特征。而这些实时动态事件会使之前通过静态调度已经制定好的生产加工计划无法执行，需要车间调度人员根据这些新情况重新进行任务分配或工件调度。

柔性制造系统由于采用高度柔性的加工设备，零件的加工路线约束松弛使生产更灵活、高效，但相应的柔性调度更加复杂，调度算法所要搜索的解空间也急剧增大[1]。研究动态调度的主要方法有：最优化方法、系统仿真方法、启发式方法、人工智能方法及计算智能方法等[2-8]。

本文针对柔性作业车间调度过程中多目标、信息不确定和动态的特征，提出了一种基于故障处理算法的FJSP动态调度方法。建立了FJSP动态仿真求解模型，提出了动态仿真求解模型框架，该框架受自适应控制启发，结合了鲁棒调度和预见调度，兼具两者的优点，即稳定而高效；进而研究了基于预见动态调度的初步方案生成方法，采用动态仿真求解器的方法实现了预见功能，在随机事件发生时减少系统的调整与优化指标波动；获得了真正的优化效果。

1 问题描述

某生产车间，要在m台设备上加工n个零件，每个零件有p个工序，所有工序都可以在任一设备上经指定的时间和花费指定的成本加工完成。

本模型基于以下假设：

(1)每台设备每一时刻只能加工一个零件的一个工序；

(2)全部工序都必须加工也只需加工一次；

(3)每道工序必须一次加工完成，不能中断；

(4)同一零件的工序必须按顺序加工，即某道工序必须在其前道工序完成后开始；

(5)各零件的各工序在不违背要求(4)的条件下具有相同的优先级；

(6)设备在维护期间不能进行加工；

(7)设备在故障维修期间不能加工；

(8)随机故障遵循期望为MTBF(Mean Time Between Failure，平均故障间隔时间)的指数分布；

(9)维修时间遵循期望为MTTR(Mean Time To Restoration，平均维修时间)的指数分布；

(10)所有机器的MTTR，MTBF均事先已知；

(11)假设某工序加工过程中出现故障，该工序可以重新开始，而且不会因此产生废品。

多目标FJSP即满足上述假设下将工序分配到各机床，确定加工次序，使得总工期、机器总负载、总成本和工序滞后度等指标最优。

2 动态柔性作业车间调度建模

受现代控制理论观测器概念的启发，本文设计了如图1的动态仿真求解模型。其中仿真求解器共享实际生产系统的基础信息，包括设备、人员、物料、订单等方面信息，以及各工序在不同设备上加工的工时与成本等，还包括了设备新旧程度、维修周期等方面的信息。同时仿真求解器还接受实际生产系统运行过程中产生的信息更新，如设备无故障工作时间，已完成工序内容等。以上信息也作为考虑实时事件发生时生成初始动态决策的基础。当发生设备故障或订单变动等实时事件时仿真求解器的调度更新功能将作出快速反应，重新生成新的调度决策，或对原调度决策进行调整以适应情况的变化，并保证系统指标的优化。

图1 动态仿真求解模型

为保证求解的精度和系统运行的稳定性，该仿真求解器能根据实际指标输出与仿真指标输出的差异来修正系统的参数与算法的选择。

AGA(Adaptive Genetic Algorithm，自适应遗传算法)求解器是保证动态调度优化能力的核心，该求解器是作者前续研究AGA算法基础上修改得到的[9-10]。修改后的AGA求解器在模型中能动态更新其求解参数，具备了动态调度的能力。

3 多目标FJSP数学模型建立

取设计变量：

(1)

ORDij∈{1，2，...,pn}i∈N,j∈P

(2)

FJSP优化模型：

(3)

(4)

(5)

(6)

(7)

(3)-(6)式分别给出了最小总工期目标、单台设备最大负载最小化目标、全部设备总负载最小化目标和最小总成本目标；(7)式保证每工序只在一台设备上加工。

FJSP问题一定要保证某一时刻一台加工设备最多有一道工序在进行加工；并且要保证每个工件按工序的先后顺序依次进行。加工设备与工序的选择关系由0-1变量可确定；工件的工序加工顺序可由式(8)到(10)约束确定。

s.t.

STij+1≥ETiji∈N,j∈{1，2，...，p-1}

(8)

(9)

k∈M,i,i′∈N,j,j′∈P,且i≠i′,j≠j′

(10)

(8)式保证同一工件各工序的顺序；(9)式保证ORDij取得1-pn的组合；(10)式保证各工序的开始加工时刻，或者为0，或者要在同一设备前一工序完工之后。

4 故障处理算法设计

在给定的目标下，如期望的工期或最小的滞后，仿真器能在随机故障事件的情况下评价各方案的适应度。在仿真过程中，使用事件驱动策略决定何时进行重调度，当需要重调度时使用右移启发算法进行调度方案修正。在以上两个过程中都要使用到FEL变量与LIFE变量。将仿真器算法添加到AGA的解码算法中，对每一个原静态方案(染色体)施行以下步骤：

(1)初始化：

① 生成甘特图数据结构G，方便重调度时刻的判断与采用启发算法的调整；

② 根据各设备的MTBF，按指数分布生成随机变量FEL，对每台设备Mk生成随机数：FEL[Mk]= exp-rand(MTBF)，其中 exp-rand为指数分布随机数生成器Mk；k= 1， 2，...，m。

(2)建立动态调度，对工序部分自左至右读出其基因代码执行以下操作：

① 确定其对应工序Oij；

② 参考设备指定部分基因，确定其加工设备Mk，以及该工序在该设备上的工时Pijk；

③ 取t1为工序Oij的同一工件紧前工序Oij-1的结束时间，t2为同一设备前一工序的结束时间。如果Oij为某工件的首道工序(j=1)，则t1=0。如果Oij为所在设备的第一个工序，则t2=0；

④ 如果t2小于或等于t1，也就是指定设备Mk在t1时刻空闲，将工序在Mk上加工。起始时间为t1。否则将Oij插入Mk上正在加工工序之后，即开始时间为t2；

⑤ 执行故障处理算法。

(3)计算按照目标评价方案的适应度；

(4)若满足迭代终止准则，则输出方案；否则，转2。

仿真器通过故障处理算法实现对现实过程中随机故障的模拟，其步骤如下：

(1) 将Oij在设备Mk上加工的工时Pijk累加到Mk的使用时间中，即LIFE的相应变量中 LIFE[Mk]=LIFE[Mk]+Pijk；

(2) 如果(LIFE[[Mk] > FEL[[Mk]) 转步骤 3，否则，转步骤4；

(3) 设备出现故障，执行以下操作：

① 生成以该设备MTTR为期望的指数分布随机数，作为维修时间；

Repair time=exp-rand(MTTR)

② 将生成的维修时间添加到被中断工序所在零件的结束时间中；

Complete[i]= Complete[i]+ Repair time

③ 重置FEL中对应设备的变量，更新Mk的未来故障时间；

FEL[[Mk]= exp-rand(MTBF)

④ 将[Mk的使用时间归零。

LIFE[[Mk]= 0

(4) 返回修改后的AGA算法。

图2 初始动态调度生成流程图

5 算例仿真与企业实例验证

以下以表1“3×5”问题为例，展示动态调度的特点。以及当发生故障时，基于故障处理算法的动态调度优越性。其中M1被设置成易于发生故障的设备。

表1 完全柔性作业车间调度加工时间表

图3 “3×5”问题例静态调度结果

图3为静态调度结果，工期指标为8。

图4为采用本文提出的故障处理算法获取的动态调度结果，工期指标为9。由于设备故障的随机性以及该指标为多次动态解码的算术平均，此图只给出了一种解码结果，工期为9。但这不影响在统计意义下方案的较优性。而且，由图可见动态调度自动避开了倾向于故障的M1，使得初始调度方案具有更高的可靠性。

图4 “3×5”问题例动态调度结果的解码

图5 实时多目标调度参数设置界面

图6 多目标优化(成本+总负载)调度结果

该算法在某减速机分公司的生产管理软件得以应用，该企业主要生产重型汽车的减速器、齿轮齿座、联轴器和涡轮丝杆升降机等产品，属于典型的面向柔性制造的离散制造业。

图5为实时多目标调度参数设置界面，可选择调度任务，并列有调度类型选项：预调度、订单变动、设备故障及报废工件等。在优化参数一栏，可人工修改遗传算法参数，根据车间实际动态状况在一定程度上控制算法运算时间和精度。如不修改就沿用系统默认的参数值。优化目标部分，在各优化目标后面方框中的数字代表不同权重，数值大小可调。优化参数和优化目标权重值的调整会影响调度时间和结果，可根据工厂车间实际要求做出调整。全部参数选择设置好之后，可执行“开始”按钮，并查看调度结果甘特图。

图6显示的是由于车间出现设备故障，重新调度后以最小成本和最小全部设备负载为优化目标的甘特图。

6 结论

本文建立了动态仿真求解模型框架，该框架受自适应控制启发，结合了鲁棒调度和预见调度，兼具两者的优点，即稳定而高效；然后研究了故障处理算法，采用动态仿真求解器的方法实现了预见功能，使得生成的方案从统计的角度考虑了随机事件的可能发生，因而既获得了真正的优化效果，又能在随机事件发生时减少系统的调整与优化指标波动；综上所述，本文系统地给出了一种求解动态调度问题的模型与方法，并算例验证了其可行性与先进性。

[1] 王世进.基于自治与协商机制的柔性制造车间智能调度技术研究[D].上海:上海交通大学,2010.

[2] 高俊宇，张平，余海峰.车间动态调度方法综述[J].机电工程技术，2009,38(9)：13-16.

[3] Dong Liang-cai, XU Zi-qi, MI Wei-jian.The dynamic tugboat schedule based on particle swarm algorithm combined with genetic operators[J]. mathematics in practice and theory, 2012,42(6):122-133.

[4] W.J. Jiang, L.M. Zhang, P.Wang. Dynamic scheduling model of computing resource based on MAS cooperation mechanism[J]. Science in China Series F: Information Sciences, 2009 (l52):1302-1320.

[5] X.Wang, L. Gao, C. Zhang. A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2010 (51):757-767.

[6] Herroelen W. Discussion of “Probabilistic Estimation and Allocation of Project Time Contingency” by Gabriel A. Barraza[J]. Journal of Construction Engineering and Management 2013, 139(1):253-255.

[7] L. Nie, L. Gao, P. Li. A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates[J]. Journal of Intelligent Manufacturing , 2012:12-21.

[8] M?nch L, Fowler J W, Dauzère-Pérès S. A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations[J]. Journal of Scheduling, 2011 (14):583-599.

[9] 潘颖，孙伟，张文孝. 基于适应度分析的AGA求解柔性Job-shop调度问题[J].组合机床与自动化加工技术，2010(6)：101-104.

[10] Ying Pan, Wei Sun, Xiao-Hong Lu, Qin-Yi Ma.An Adaptive Genetic Algorithm for the Flexible Job-shop Scheduling Problem[C]. Proceedings 2011 IEEE International Conference on Computer Science and Automation Engineering,2011: 405-409.

(编辑 赵蓉)

Research on Dynamic Multi-objective FJSP Based on Fault-handling Algorithm

PAN Ying，GAO Tian-yi，XUE Dong-juan，XIE Zhong-dong

(School of Mechanical and Power Engineering, Dalian Ocean University. Dalian Liaoning 116023, China)

Aiming at multi-objective, uncertain information and dynamic characteristic during flexible job-shop scheduling process, some kind of dynamic scheduling method for FJSP is put forward based on real-time adjustment. Firstly, a dynamic simulation solution mode framework is presented for FJSP. This framework is inspired by adaptive control, combined with the robust scheduling and foreseeing scheduling. It has both advantages of such two schedulings, and it’s stable and highly efficient; at the same time, foreseeing function is realized by fault-handling algorithm and dynamic simulation solver on the basis of Adaptive Genetic Algorithm. Finally, the effectiveness and practicality of the presented algorithm is proved through the enterprise instance.

multi-objective flexible job-shop scheduling problem(FJSP); dynamic scheduling; simulation solution mode; fault-handling algorithm

1001-2265(2014)04-0150-04

10.13462/j.cnki.mmtamt.2014.04.042

2013-09-04

国家科技支持计划"大连市制造业信息化科技示范工程" (2013BAF02B03-2)；大连海洋大学博士启动基金(SYBS201205)

潘颖(1977—)，女，哈尔滨人，大连海洋大学讲师，博士，研究方向为车间调度，精益生产，(E-mail)panying@dlou.edu.cn。

TH166;TG65

A