基于顺序相关调整时间的FJSP与设备维护计划集成优化*

查　靓，金　花，潘志成，袁庆松

(三峡大学 机械与动力学院，湖北 宜昌　443002)



基于顺序相关调整时间的FJSP与设备维护计划集成优化*

查靓，金花，潘志成，袁庆松

(三峡大学 机械与动力学院，湖北 宜昌443002)

摘要：为了能根据设备的实际工作时间制定维护计划，以及利用设备空闲时间进行预防维护，研究了考虑顺序相关调整时间(SDST)的柔性作业车间调度(FJSP)和设备维护计划的集成优化问题。以完工时间最小为目标，建立FJSP-SDST与不等周期设备维护的集成优化模型。提出了基于遗传优化的两阶段算法，先得到基础FJSP-SDST的调度方案，然后在设备的可靠度低于阈值时安排不等周期实时维护计划，以一定的概率在基础调度方案中的空闲时间段插入维护时间，从而得到集成方案。针对某实例的计算结果表明，考虑顺序相关调整时间的调度方案的总完成时间优于原调度方案的总完成时间，集成优化方案的总完成时间优于定期维护方案的总完成时间。

关键词：柔性作业车间；车间调度；设备维护；顺序相关调整时间

0引言

在实际生产系统运行过程中，调度计划的实施取决于设备的稳定性，设备故障会对计划执行所产生的不良影响；简单依据历史经验安排的设备维护计划容易导致过度维护，浪费宝贵的人力和相关资源。因此，为实现生产调度与设备维护之间的有效平衡，最大化企业的整体利益，必须将两者进行集成优化。

在最近少数几篇关于生产调度和设备维护的集成研究中，Khamseh, A[1]等研究了流水车间的成组调度问题与预防维护的集成优化，文章仅对相似的并行机系统进行了研究。喻明让[2]等的研究针对的是一般作业车间的调度问题与预防维护的集成优化，没有考虑修复非新的不等周期设备维护情况。宋文家[3]等的研究针对柔性作业车间，利用改进加权TOPSIS方法和混合殖民竞争算法求解集成优化方案，但该研究没有考虑调整时间，使得设备可靠度比实际偏低，从而造成提前安排设备维护计划，降低了设备利用率。因此在FJSP和设备维护计划的集成优化研究中，有必要单独考虑顺序相关调整时间。

基于上述分析，本文以完工时间最小为目标，基于威尔分布的故障密度函数和不等周期实时维护策略，建立了考虑顺序相关调整时间的FJSP与设备维护计划集成优化模型，设计了基于遗传优化的两阶段算法进行求解。针对某实例的计算结果表明该模型及算法的有效性，得到的集成优化方案不仅能够保证生产的连续进行，而且具有更好的生产效率。

1问题描述

1.1设备维护问题描述

设备的预防维护计划需确定间隔多久进行一次预防维护(即预防维护周期)和进行一次预防维护所需的时间。

设备的可靠度是指设备在寿命周期内完成规定功能的能力。随着设备的运转，当可靠度低于一定的阈值时进行维护以避免出现故障造成停机。设备可靠度的计算与其故障概率密度函数有关，故障概率密度是指机器在单位时间发生故障的概率，由于在机械加工车间使用的大多是机电类设备，故障概率概率更接近威尔分布[4]，依据文献[5]，设备在运行时刻t的故障概率密度函数f(t)如式(1)所示：

(1)

其中，t代表设备运转的第t时刻，β为形状参数，不同的β决定不同的分布曲线形状，η为尺度参数，二者都与设备使用时间t无关。

根据式(1)设备在t时刻的可靠度R(t)如下式(2)计算[5]：

(2)

本文假设设备每次进行预防维护所需时间相同，在实际应用中可依据各设备历史运行数据进行确定。

1.2FJSP-SDST问题描述

FJSP的一般描述为：n个工件在m台设备上加工，每个工件的加工有k道工序，工序顺序是确定的[7]。FJSP具有加工路径柔性的特点，每道工序可以在多台不同的设备上加工，但使用的设备不同加工时间也不同。因此，FJSP包含两个子问题：确定工序的设备选择和确定各设备上工序的加工顺序[8-10]。

当某台设备上的加工产品改变时，一般需要卸下已加工完成的工件、除屑、更换工具、夹具或模具、装载待加工工件等，所耗费的时间为调整时间[11]。此时设备处于停机状态，在维修计划中调整时间不应计入设备的工作时间，此外，该调整时间与相邻工序之间的相似性有关，加工顺序会影响调整时间的长短，进而影响整个加工完成时间。维修计划的插入会影响工件在设备上开始加工的时间和完工时间，因此需要对FJSP-SDST与设备维护计划进行集成优化。

2数学模型的建立

建立FJSP-SDST与设备维护计划的集成优化模型如下：

(3)

s.t.stij+x(ij)l×p(ij)l≤etij

(4)

etij≤sti(j+1)

(5)

etij≤Cmax

(6)

(7)

etij×x(ij) l+tl×q(ij)(hd)l×g(ij)(hd)l+tz(ij)(hd)l×g(ij)(hd)l≤

sthd×xhdl+L(1-g(ij)(hd)l)

(8)

Rl(t)≤Rl,min

(9)

其中，i和h代表工件序号，i,h=(1,2,…,n)；Kj表示工件j加工的总工序数；j和d表示工序序号；l表示设备序号，l=(1,2,…,m)；p(ij)l表示工件i的第j道工序在设备l上的加工时间；stij表示工件i的第j道工序加工开始时间(不包括调整时间)；etij表示工件i的第j道工序加工结束时间；tz(ij)(hd)l表示设备l先加工工件i的第j道工序接着加工工件h的第d道工序的调整时间；tl为机器l的维护时间；Ci表示工件i的完工时间；Cmax表示加工的最大完工时间；L为一个极大的正数；变量xijl=1表示工件i的第j道工序在设备l上加工，否则xijl=0；g(ij)(hd)l=1表示在设备l连续加工工件i的第j道工序和工件h的第d道工序，否则g(ij)(hd)l=0；q(ij)(hd)l=1表示在设备l加工工件i的第j道工序和工件h的第d道工序之间需要维护，否则q(ij)(hd)l=0。

目标函数(3)表示追求总完工时间最短，约束条件(4)和(5)表示同一工件加工顺序符合工序的先后顺序约束；式(6)表示每个工件的完工时间不得超过总完工时间；式(7)表示同一时刻同一工序只能在一台设备上加工；式(8)表示同一台设备的上道工序完工时间加上维护时间和调整时间小于下道工序的加工开始时间；式(9)表示设备的可靠度应小于其可靠度阈值。

3两阶段算法的设计

由于该集成优化问题为NP-难问题，直接求解非常困难，因此设计了一种基于遗传优化的两阶段算法。算法流程如图1所示。

初始化种群后，第一阶段不考虑维护计划利用遗传算法的交叉、变异算子得到多个基础FJSP-SDST调度方案。第二阶段，基于基础调度方案，根据机器可靠度模型和不等周期维护规则生成维护计划，以一定的概率将维护时间插入机器加工的空闲时间，得出对应的多个调度维护集成方案，计算适应度值，保留精英解，然后根据轮盘赌规则选择若干个个体截取FJSP-SDST部分复制到下一代种群，算法反复搜索直到满足停止条件，此时输出保留在外部的精英解即为集成优化方案。

图1　算法流程图

3.1第一阶段：基础FJSP-SDST调度方案的生成

(1)编码

由于FJSP同时需要确定工序的设备选择和确定各设备上工序的加工顺序，因此采用基于工序和机器的编码方法。个体由两部分组成，前半部分为工序编码，用来确定工序的加工先后顺序，每道工序用对应工件号表示；后半部分为机器编码，用来选择每道工序的加工机器，用机器号表示。每个编码序列即为FJSP的一个可行解。假设某柔性作业车间有3台设备，待加工4个工件，每个工件包含2道工序。如图2所示，工序序列为(O11O41O21O12O31O42O22O32)，机器上的加工序列为：机器1(O41O42)，机器2(O12O31O22)，机器3(O11O21O32)。Oij表示工件i的第j道工序。

图2编码示例

(2)FJSP-SDST解码

基于FJSP-SDST的问题模型，需要在安排工件加工开始之前确定顺序相关调整时间。当工序为设备上第1道工序或者工序与该设备上的紧前工序属同一工件时，工序在机器上的顺序相关调整时间为0。具体解码规则：首先判断当前工序号分别为工件和设备上的第几道工序；然后计算当前工序所属工件的紧前工序和设备上的紧前工序完工时间的差值Δt，若Δt=0，则调整开始时间任取两者之一，若0<Δt≤tz(ij)(hd)l,则调整开始时间为设备上紧前工序的完工时间，若Δt>tz(ij)(hd)l，则调整开始时间为工件紧前工序的完工时间减去调整时间。工件或机器加工开始时间为调整开始时间加上调整时间，工件或设备加工结束时间为加工开始时间加上工序在设备上的加工时间。依次类推，直到工序序列的工件号安排完成，解码过程结束，得到基础FJSP-SDST的总完工时间。

(3)交叉

为了保证交叉后得到的子代仍是可行解，采用基于工序编码的交叉方法，即交叉操作只改变父代中的工序序列，保留工序对应的机器到子代。交叉过程如图3所示为：首先，将所有工件随机分成两个集合A1和A2(图3中A1包含工件1和3，A2包含工件2和4)；然后，复制父代1包含在A1中(工件1和3)的工序序列到子代1，复制父代2包含在A2中(工件2和4)的工序序列到子代2，保留它们的位置和顺序，复制父代1包含在A1中(工件1和3)的工序序列到子代2，复制父代2包含在A2中(工件2和4)的工序序列到子代1，保留它们的顺序。

图3　交叉示例

(4)变异

采用基于工序编码的两点变异方式，随机选取工序序列两个位置的工序号交换位置，保持所有工件工序分配的机器不变，如图4所示，把工序序列中位置3的工序4与位置5的工序3交换，同时交换两个工序对应的机器，得到子代。

图4　变异示例

3.2第二阶段：维护计划的概率插入

经过第一阶段，得到了若干个基础FJSP-SDST调度方案，明确了每台设备上工件加工的顺序和工时，可计算出设备的可靠度，当可靠度到达阈值时，需要安排维护任务，如果此时设备正好是空闲的，且空闲时间大于维护时间，可直接插入维护计划，但如果此时设备上正在执行加工任务，有两种选择：①提前进行维护保养，再执行当前加工任务，称为前移式；②等到当前加工结束后再进行维护保养，称为后移式，但如果加工时间较长导致维护周期太长，任务结束时设备损耗非常严重，甚至出现故障。如图5所示，虚线处是设备可靠度达到阈值的时刻，设备1的维护计划采用的是后移式，设备2的维护计划是前移式，很好的利用设备的空闲时间来进行维修保养，缩短总的完成时间。

图5　前移式和后移式维护计划示例

STEP1：取一个基本的FJSP-SDST方案。初始化，设置当前工序Oij为工序序列中的第一个工序，维护次数el=0，(l=1,2,...m)，以及初始可靠度阈值。

STEP4：判断当前工序是否是工序序列中的最后一道工序，如果是此子程序结束，计算总完工时间；否则，更新当前工序为工序序列中的下一个工序，转STEP2。

4实例验证

某柔性作业车间包含6台设备，加工6个工件，每个工件包含6道工序，车间原来采用的维护方案是每隔35个时间单位进行一次维护，调度维护方案的甘特图如图6所示，黄色部分为加工时间，红色部分为设备维护时间，该方案的总完工时间为128个时间单位，维护次数14次。

图6　未优化的原始调度维护方案甘特图

通过对加工过程的进一步分析，可分离出每道工序的实际加工时间和顺序相关调整时间，如表1和表2所示。

表1　每道工序的可选设备及加工时间

基于MATLAB R2012b平台开发实现本算法，并进行多次仿真实验。

首先仅运行第一阶段程序求解考虑顺序相关调整时间后的柔性作业调度问题(FJSP-SDST)，算法相关参数设置如下：种群规模N=100,迭代次数为50，交叉概率Pc=0.8，变异概率Pm=0.05，维护方案仍是每隔35个时间单位进行一次维护，得到优化后的调度维护方案的甘特图如图7所示，蓝色为调整时间，此时总完工时间为117，比不考虑顺序调整时间的原始方案的总完工时间减少11个时间单位，表明将每道工序的实际加工时间和顺序调整时间分离，进行基于顺序相关调整时间的调度优化有助于得到完工时间更短的方案。

图7　考虑顺序相关调整时间的调度维护优化方案甘特图

表3　设备预防维护的相关参数

采用本文设计的两阶段算法计算得到集成优化方案，甘特图如图8所示。例如设备6在第26个时间单位时，可靠度降到阈值，需要进行维护，此时该设备上正在进行工件1的第3道工序的加工，将此维护任务提前到该工序之前，可利用生产空闲时间进行维护。又如设备4在28个单位时间时，需要进行维护，此时该设备上正在进行工件3的第3道工序的加工，该工序完工后可靠度为0.843，仍在安全范围内，将该维护任务推后在该工序完成后的空闲时间再进行。

图8　FJSP-SDST与设备维护计划集成优化方案甘特图

集成优化方案的最大完工时间为112个时间单位，维护次数8次。如表4所示，该集成优化方案与未优化的原始方案相比，总完工时间减少16个时间单位，维护次数减少6次；与仅考虑了顺序相关调整时间的调度维护优化方案(FJSP-SDST)相比，总完工时间减少5个时间单位，维护次数减少6次。

表4　计算结果对比

本文所提的调度和设备维护集成优化方法由于充分利用了调度方案中的空闲时间进行预防维护，因此有助于提高了生产效率和机器使用率。

5结论

本文针对FJSP-SDST与集成优化研究问题，建立了以最大完工时间最小为目标的调度与维护集成优化模型，设计了基于遗传优化的两阶段算法，在FJSP-SDST调度基础上，依据设备可靠度模型和不等周期维护规则，利用前移式和后移式在设备空闲时间段插入维护计划。实例计算表明，考虑顺序相关调整时间有助于找到完工时间更短的调度方案，生产调度与设备维护计划集成优化有助于利用调度方案中的空闲时间进行预防维护，将加工时间和调整时间分离有助于更准确的计算设备累积运行时间及其可靠度，进一步减少预防维护的次数。考虑顺序相关调整时间的FJSP与设备维护集成优化方案既保证了连续生产，也减少了因不科学的设备维护计划造成的生产资源浪费，大大提高了机器利用率和生产效率。

[参考文献]

[1] Khamseh A , Jolai F, Babaei M. Integrating sequence-dependent group scheduling problem and preventive maintenance in flexible flow shops[J]. International Journal of Advanced Manufacturing Technology. 2014, 77(4): 173-185.

[2] 喻明让, 张英杰, 陈琨,等. 考虑调整时间的作业车间调度与预防性维修集成方法[J]. 西安交通大学学报,2015, 49(6): 16-20.

[3] 宋文家, 张超勇, 尹勇, 等. 基于多目标混合殖民竟争算法的设备维护与车间调度集成优化[J]. 中国机械工程,2015,25(11): 1478-1487.

[4] 李苗群.基于可靠性的设备预防性维护策略研究[D].西安: 西安电子科技大学, 2011.

[5] 魏永合,刘雪丽,牛保国. 基于故障预测的预防性维修策略优化模型[J]. 组合机床与自动化加工技术,2015(7):91-94.

[6] 刘繁茂.面向故障过程的多设备可靠性分析与维修决策 [D]. 武汉:华中科技大学, 2010.

[7] 李传鹏,王桂从,崔焕勇. 柔性作业车间调度问题研究现状及发展趋势[J]. 组合机床与自动化加工技术,2012(11): 109-112.

[8] Wang Ling, Zhou Gang, Xu Ye, et al. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology. 2012, 50(4): 303-315.

[9] 吴秀丽, 张志强, 杜彦华, 等. 改进细菌觅食算法求解柔性作业车间调度问题[J]. 计算机集成制造系统,2015, 21(5): 1262-1270.

[10] 赵诗奎. 求解柔性作业车间调度问题的两级领域搜索混合算法[J]. 机械工程学报, 2015, 51(14): 175-184.

[11] Allahverdi A, Ng C T, Cheng T C E, et al. A survey of scheduling problems with setup times or costs [J]. European Journal of Operational Research, 2008, 187(3):985-1032.

[12] Ruiz R, Maroto C，Alcaraz J. Solving the flow-shop scheduling problem with sequence dependent setup times using advanced metaheuristics[J]. European Journal of Operational Research. 2005,165(1): 34-54.

[13] 徐建有, 董乃群, 顾树生. 带有顺序相关调整时间的多目标流水车间调度问题[J]. 计算机集成制造系统,2013, 19(12): 3170-3176.

[14] 周亚勤, 李蓓智, 杨建国. 调整时间与工序顺序相关的Job shop调度优化方法研究[J]. 中国机械工程,2005,16(10): 914-918.

[15] 高亮, 张国辉, 王晓娟. 柔性作业车间调度智能算法及其应用[M]. 武汉:华中科技大学出版社, 2012.

(编辑赵蓉)

Integrated Optimization of Flexible Job Shop Scheduling Problem and Equipment Maintenance Plan with Sequence-dependent Setup Times

ZHA Jing,JIN Hua,PAN Zhi-cheng,YUAN Qing-song

(College of Mechanical & Power Engineering, Three Gorges University, Yichang Hubei 443002, China)

Abstract：In order to draw up an equipment maintenance plan based on actual working time and free time, the paper studied the integrated optimization of flexible job shop scheduling problem (FJSP) and equipment maintenance plan with sequence-dependent setup times (SDST). The object of the integrated optimization model is to pursue the minimum of makespan. The paper proposed a two-stage algorithm based on the genetic algorithm to solve the problem. Firstly generated basic FJSP-SDST schedules. Secondly probabilistically arranged the unequal periodic equipment maintenance at the equipment’s free time if the reliability of the equipment is below the threshold value. Then obtained an integrated plan. The optimization result of a practical example showed that the makespan of FJSP-SDST was less than the original one and the makespan of the integrated optimization was less than the makespan of equipment maintenance at regular intervals.

Key words：flexible job shop; shop scheduling; equipment maintenance; sequence-dependent setup time

文章编号：1001-2265(2016)05-0155-06

DOI:10.13462/j.cnki.mmtamt.2016.05.042

收稿日期：2016-12-11；修回日期：2016-01-12

*基金项目：湖北省教育厅科学技术研究项目(Q20151206)

作者简介：查靓(1978—)，女，湖北松滋人，三峡大学讲师，博士，研究方向为生产调度及智能算法应用，制造系统建模仿真优化等，(E-mail)maria_zhajing@hotmail.com。

中图分类号：TH166;TG659

文献标识码：A