考虑调整时间的作业车间调度与预防性维修集成方法

喻明让,张英杰,陈琨,高瑞,张定

(西安交通大学机械工程学院,710049,西安)



考虑调整时间的作业车间调度与预防性维修集成方法

喻明让,张英杰,陈琨,高瑞,张定

(西安交通大学机械工程学院,710049,西安)

为了解决作业车间调度理论研究中两种常见但却不符合生产实际的理想假设所带来的问题,提出了一种考虑调整时间的作业车间调度与预防性维修集成方法。首先利用遗传算法得到单独考虑调整时间时的最优初始调度方案,然后依据初始调度方案中各机器的任务分配情况以及该机器的故障概率分布自适应确定其预防性维修方案,同时依据插入的预防性维修时间间隔采用右移策略对初始调度方案进行调整,最终得到优化的作业车间调度与预防性维修集成方案。通过对经典调度基准实例进行扩展来构造测试实例,进而验证所提方法的有效性。实验结果表明:单独考虑调整时间不仅能够提高车间调度性能,还能够使得依据机器的运行时间和故障概率分布得到的预防性维修方案更加合理,从而达到提高生产效率并降低预防性维修成本的目的,对于实际生产具有一定的指导意义。

作业车间调度;调整时间;预防性维修;故障概率分布

车间调度问题是组合优化问题理论研究与生产实际相结合的典范,对车间调度问题的研究不仅能够在理论上推进优化理论的发展,而且能够提高实际生产的效率,其中作业车间调度问题(JSP)由于具有典型性而受到研究者们的广泛关注。JSP定义如下[1]:n个工件在m台机器上加工,每个工件包含多个具有先后顺序的工序,各工件的工艺路线不尽相同,各工序采用的机器及其在该机器上的加工时间已知。要求在满足各工件工序顺序约束的前提下,确定各工件在每台机器上的加工顺序及加工开始时间,以使某些性能指标最优。

JSP问题早已被证明是非确定性多项式难题[2],为了便于求解,研究者在建立JSP模型时往往通过一些理想假设来对问题进行简化,其中最常见的两种理想假设[3-4]:①机器在任何时刻都是可用的;②工序的调整时间是可以忽略的,或者将调整时间合并为工序的加工时间。

毫无疑问,以上假设使JSP求解过程得到简化,并因此产生了丰富的理论研究成果[5-7]。然而,这些假设往往并不符合车间生产实际。例如,生产过程中的机器故障使得机器在调度区间内会出现不可用时段,从而导致已有调度方案不在最优甚至是不可行的;另一方面,在许多实际生产中,调整时间相对于加工时间来说是不可以忽略的,而将调整时间合并为工序的加工时间则会导致调度性能恶化。因此,车间调度理论研究中这两种常见但不符合生产实际的理想假设,使得车间调度的理论研究成果难以很好地应用于实际生产[8]。

机器故障是导致调度资源环境发生变化的主要原因之一,并且机器故障可能造成重大的生产损失。为了减少可能发生的机器故障,需要定期对机器进行停机检修,即预防性维修(PM)。对机器进行预防性维修时会造成生产的停滞,占用一定的生产时间。在进行生产调度时若不考虑机器的预防性维修,则有可能因为机器发生故障造成不必要的损失。因此,车间生产调度与预防性维修之间存在密切的联系,有必要对二者进行集成研究。另外,由于机器运行过程中,只有加工时间才会造成机器的退化,进而引起机器故障[9]。在大多数车间调度的研究中经常假设调整时间是可以忽略的或者将调整时间合并为工序的加工时间,因此导致依据机器故障概率分布确定的预防性维修计划不够合理。

调整时间主要指的是更换夹具、模具以及清理工作台、切屑、废液等消耗的时间。文献[10]对考虑调整时间的车间调度问题进行了综述,认为调整时间可以分为与顺序无关的调整时间和与顺序相关的调整时间。前者指的是工序的调整时间只与该工序所属的工件以及所选择的机器有关;后者指的是工序的调整时间与该工序所属的工件以及该机器上一个加工任务所属的工件有关。文献[11]进一步将调整时间划分为可提前发生的调整时间和不可提前发生的调整时间,若调整工作可以在工件到达该机器前进行则称该调整是可提前发生的,否则为不可提前发生的。本文主要考虑可提前发生且顺序无关的调整时间对作业车间调度与预防性维修集成研究的影响。

考虑机器预防性维修的车间调度即在调度方案中插入一定的空闲时间间隔(PM时间)以进行机器的预防性维修。尽管已有的研究中对考虑预防性维修的车间调度进行了较多的研究,但是大多数此类研究中都忽略调整时间或将调整时间作为加工时间的一部分来进行考虑[12-14]。如前所述,这将导致依据机器故障概率分布确定的预防性维修周期与实际不相符,因此本文对考虑调整时间的作业车间调度与预防性维修集成问题进行研究,从而使车间调度的理论研究更加符合实际生产,同时达到提高生产效率并降低预防性维修成本的目的。

1 必要性分析

图1 作业车间调度与预防性维修集成中考虑调整时间与否的对比结果

在预防性维修的研究中,依据机器的故障概率分布确定预防性周期是最常采用的方法。假设图1a与图1b分别是将调整时间合并为加工时间以及将调整时间单独考虑的调度甘特图(仅以机器M1上的任务为例)。假设依据机器M1的故障概率分布计算得到每隔20个单位时间M1的故障概率就会大于所设定的阈值,即需要进行预防性维修(一般假设故障概率大于设定的阈值时机器很可能发生故障,需要进行预防性维修[14]),且一次预防性维修需要持续5个单位时间,则将调整时间合并为工序加工时间以及单独考虑调整时间的预防性维修与调度集成方案,如图1c和图1d所示。由图1对比结果可知,当单独考虑调整时间时,插入预防性维修时间间隔的数量和位置更加精确,能够有效地提高生产效率(最大完工时间),同时降低了预防性维修成本(预防性维修次数)。因此,有必要在进行作业车间调度与预防性维修集成研究时单独考虑调整时间。

2 机器故障描述

对机器故障的研究一般将机器故障分为故障信息完全未知、故障信息完全已知以及故障信息部分已知3类。对于故障信息完全未知的机器故障主要采用经验估计的方法进行固定的周期性预防性维修;对于故障信息完全已知的机器故障则可直接在已知的故障发生时刻前进行预防性维修。实际上大多数生产中所面临的机器故障属于故障信息部分已知的情况,即可以依据机器的历史数据得到机器故障的概率分布。本文研究是针对已知机器故障概率分布的情况来进行的,选择以指数分布为例来描述机器故障的概率分布。假设各机器故障概率独立且同分布,各机器进行一次预防性维修所需要的时间相同(在实际应用中需要依据各机器历史运行数据进行确定)。同时,假设进行预防性维修后机器故障概率重置为0,则机器故障的指数分布描述如下

(1)

3 作业车间调度与预防性维修集成方法

本文将作业车间调度与预防性维修集成分为两个阶段。首先单独考虑调整时间生成优化的初始调度方案,然后依据初始调度方案中各机器的任务安排情况以及机器的故障概率分布自适应确定各机器的预防性维修计划。同时,由于插入预防性维修时间间隔,初始调度方案也需要进行适当的调整。本文采用右移策略对受影响的工序进行调整以保证调度方案总是可行的。

3.1 初始调度方案生成方法

如前所述,JSP属于典型的NP-hard问题,因此采用近似算法在可接受的时间内寻求问题的近似最优解成为主要的研究方法[2]。如遗传算法、粒子群优化、蚁群算法、模拟退化算法以及禁忌搜索算法等都在一定程度上解决了某一类型的车间调度问题,其中GA算法由于良好的搜索能力而受到广泛关注。本文选择遗传算法来求解JSP,从而得到优化的初始调度方案。遗传算法求解JSP的研究较为成熟,不同的是本文在进行作业车间调度时对调整时间进行单独考虑,因此其解码方法需要进行调整。图2给出了采用遗传算法求解JSP的流程,接下来对其关键步骤进行简要介绍。

图2 遗传算法求解JSP流程

(1)编码。本文采用基于工序的编码,基于工序的编码具有任意交换编码位置仍然能够得到可行调度的特点。表1给出了一个3×3的JSP实例(时间为无量纲单位时间),则其一个可能的染色体编码为[2 1 2 3 3 1 3 2 1],其中基因位的数字表示其对应的工件编号,该数字在染色体中第几次出现表示该工件的第几个工序,如第1个3表示J3的第1道工序,第2个1表示J1的第2道工序等。

(2)解码。间隙挤压法能够保证解码得到活动调度,此处对其进行改进使其能够应用于考虑调整时间的JSP优化求解。由于本文考虑的调整时间与顺序无关,直接将工序的开始时间加上其相应的调整时间以及加工时间即可得到该工序的完工时间。

表1 一个3×3的JSP实例

间隙挤压解码算法的其他操作可参考文献[15]。

针对JSP的适应度函数为最大完成时间,则适应度值越小的个体越适合生存,采用轮盘赌的方式进行选择操作,交叉方法采用文献[15]提出的基于工序编码的交叉算子,变异采用互换变异。采用遗传算法求解JSP问题的研究较为成熟,此处不做过多描述,详细操作可以参考文献[15]。

3.2 作业车间调度与预防性维修集成

在得到作业车间调度的初始方案之后,进行车间调度集成与预防性维修的流程如下。

Step 2: 由式(1)以及机器Mk的故障概率阈值Ptk得到机器的累积加工时间阈值

(2)

Step 3: 依据初始调度方案S中机器Mk上的任务分配情况及其累积加工时间阈值tak结合预防性维修策略,自适应确定机器Mk的预防性维修计划,即在机器Mk的调度区间内自适应插入一定数量的预防性维修时间间隔。同时,由于预防性维修间隔时间的插入,调度方案S也需要及时地进行调整。即将机器Mk上直接受影响的工序以及其他机器上间接受影响的工序都采用右移策略进行调整,并以调整后的调度方案S′代替初始调度方案S,同时令k=k+1。

Step 4: 判断k≤m是否成立,其中m表示调度系统中机器的数量,若成立,转到Step 2;否则,退出循环,输出最终的调度方案(集成了预防性维修方案的调度方案)。

在上述流程Step 3里提到采用预防性维修策略自适应确定机器Mk的预防性维修计划,就是当预防性维修与车间调度集成时,进行预防性维修必须考虑车间调度任务的执行情况,同时车间调度方案也需要根据预防性维修计划进行相应的调整。为了尽可能降低预防性维修活动对调度执行的干扰,预防性维修活动应尽可能被安排在该机器某一工序完成之后或者另一工序开始之前进行。

假设在调度开始时各机器的累积加工时间及故障概率均为0,令Oki和Ok(i+1)分别表示机器Mk上相邻的两个工序,且工序Ok(i+1)在Oki之后进行加工。令taki和tak(i+1)分别表示工序Oki和Ok(i+1)加工完成时机器Mk的累积加工时间,tak表示机器Mk的累积加工时间阈值,则当taki≤tak且tak(i+1)>tak时,在工序Oki后插入一次预防性维修活动。此时,若工序Oki和Ok(i+1)之间不存在足够的空闲时间来进行预防性维修,则需要将机器Mk上的工序Ok(i+1)及其以后的工序进行右移,同时将其他机器上受影响的工序也进行相应的右移。

针对表1所示调度实例,其最优调度方案如图3所示(其中时间为无量纲单位时间,下同)。假设各机器的tMTBF都为5个单位时间,且进行一次预防性维修需要1个单位时间。设定的机器故障概率阈值为0.7。由式(2)得到tak≤6.019 9,向下取整得到tak=6,即各机器累积加工时间达到6个单位时间时需要进行预防性维修。依据上述方法得到考虑预防性维修的作业车间调度甘特图如图4所示,其中M1和M2在累积加工时间为6个单位时间时进行了预防性维修,而M3在累积加工时间为5个单位时间时进行了预防性维修。由于预防性维修活动的插入,最大完工时间增加了1个单位时间。

图3 表1实例的最优调度甘特图

4 实验结果与分析

本节通过对经典调度基准实例进行扩展来构造测试实例,进而验证本文所提方法的有效性。选择Fisher等提出的FT06[16]作为基础实例,FT06加工数据如表2所示。首先构造各工序的调整时间,假设调整时间是顺序无关的,且取值范围为[1,3],随机生成一个6×6的二维矩阵,矩阵的元素为1到3之间的整数,得到的扩展FT06加工数据如表3所示。

表2 FT06初始加工数据

表3 扩展后的FT06加工数据

依据表3中的数据,首先采用前述遗传算法分别生成不考虑调整时间和考虑调整时间的调度方案,其中不考虑调整时间指的是将调整时间合并为工序的加工时间来进行调度优化。两种方法得到的最优调度甘特图分别如图5和图6所示,其中考虑调整时间比不考虑调整时间得到的最优调度方案的最大完工时间缩短了7个单位时间(约9.46%)。

图5 合并调整时间的调度甘特图

图6 考虑调整时间的调度甘特图

由于本文方法重点强调在预防性维修与车间调度集成研究中单独考虑调整时间的重要性,而机器故障的概率分布模型等不是本文研究的重点。此处假设各机器故障独立且服从相同的指数分布,各机器平均无故障时间间隔tMTBF都为33个单位时间。对各机器进行一次预防性维修的时间为2个单位时间,一次预防性维修的成本为200元,各机器故障概率阈值设定为0.6。那么,由式(2)计算得到各机器的累积加工时间阈值为30.24个单位时间,为安全起见,向下取整得到ta=30。采用第3节所述方法,分别以图5和图6的调度方案作为初始调度方案进行预防性维修计划的制定,同时对初始调度方案进行适当的调整。最终得到的车间调度与预防性维修集成方案分别如图7和图8所示,详细的对比结果如表4所示。

图7 不考虑调整时间的车间调度及预防性维修方案

图8 考虑调整时间的车间调度及预防性维修方案

从表4结果可以发现,当单独考虑调整时间时,车间调度方案的最大完工时间有一定程度的降低,意味着生产效率得到提高,同时预防性维修成本也得到大幅度的降低。证明了在作业车间调度与预防性维修集成研究中单独考虑调整时间的重要性,也说明本文所提方法是有效的,其对实际生产具有一定的指导意义。

表4 两种方案的预防性维修与车间调度集成对比结果

5 结 论

通过分析车间调度与预防性维修之间的内在联系,以及依据车间调度进行预防性维修时单独考虑调整时间的必要性,本文提出了一种考虑调整时间的作业车间调度与预防性维修集成方案。该方案重点强调了在预防性维修与车间调度集成研究中单独考虑调整时间的重要性。首先利用遗传算法得到优化的初始调度方案,然后依据初始调度方案中各机器的任务分配情况以及该机器的故障概率分布自适应地确定各机器的预防性维修方案。同时,由于预防性维修需要占用一定的调度时间,采用右移策略对初始调度方案进行调整以保证调度方案的可行性。最后通过对经典调度实例的扩展构造了本文的测试实例,证明了在预防性维修与车间调度集成研究中单独考虑调整时间能够提高生产效率,并大幅度降低预防性维修成本,从而验证了本文所提方法的有效性。

[1]PENG Yunfang.Job shop scheduling with sequence-dependent setup times based on constraint programming approach [C]∥Proceedings of 2012 3rd International Asia Conference on Industrial Engineering and Management Innovation.Berlin, Germany: Springer, 2013: 835-841.

[2]GEN M, LIN L.Multiobjective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey [J].Journal of Intelligent Manufacturing, 2014, 25(5): 849-866.

[3]SHA D Y, HSU C Y.A hybrid particle swarm optimization for job shop scheduling problem [J].Computers & Industrial Engineering, 2006, 51(4): 791-808.

[4]LEI Deming, WU Zhiming.Crowding measure based multiobjective evolutionary algorithm for job shop scheduling [J].The International Journal of Advanced Manufacturing Technology, 2006, 30(1/2): 112-117.

[5]ZHANG Chaoyong, LI Peigen, RAO Yunqing, et al.A new hybrid GA/SA algorithm for the job shop scheduling problem [M]∥Evolutionary Computation in Combinatorial Optimization.Berlin, Germany: Springer, 2005: 246-259.

[6]NOWICKI E, SMUTNICKI C.An advanced tabu search algorithm for the job shop problem [J].Journal of Scheduling, 2005, 8(2): 145-159.

[7]VELA C, VARELA R, GONZALEZ M.Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times [J].Journal of Heuristics, 2010, 16(2): 139-165.

[8]SHEN Liji.A tabu search algorithm for the job shop problem with sequence dependent setup times [J].Computers & Industrial Engineering, 2014, 78: 95-106.

[9]ZHANG Yingjie, GE Liling.Reliability analysis of machining systems by considering system cost [EB/OL].[2014-10-24].http:∥www.tandfonline.com/doi/abs/10.1080 /0951192X.2014.914630.

[10]ALLAHVERDI A, GUPTA J N D, ALDOWAISAN T.A review of scheduling research involving setup considerations [J].Omega, 1999, 27(2): 219-239.

[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]LU C C, LIN S W, YING K C.Robust scheduling on a single machine to minimize total flow time [J].Computers & Operations Research, 2012, 39(7): 1682-1691.

[13]TANG Lixin, ZHANG Yanyan.Parallel machine scheduling under the disruption of machine breakdown [J].Industrial & Engineering Chemistry Research, 2009, 48(14): 6660-6667.

[14]HE Wei, SUN Dihua.Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies [J].The International Journal of Advanced Manufacturing Technology, 2013, 66(1/2/3/4): 501-514.

[15]张超勇.基于自然启发式算法的作业车间调度问题理论与应用研究 [D].武汉: 华中科技大学, 2007.

[16]FISHER H, THOMPSON G L.Probabilistic learning combinations of local job-shop scheduling rules [J].Industrial Scheduling, 1963, 3(2): 225-251.

(编辑 杜秀杰)

Job-Shop Scheduling and Preventive Maintenance Considering Setup Time

YU Mingrang, ZHANG Yingjie, CHEN Kun, GAO Rui, ZHANG Ding

(School of Mechanical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

To close the gap between scheduling theory and practice from unrealistic assumptions, a method for integrating job-shop scheduling (JSP) and preventive maintenance (PM) is proposed.The original scheduling plan is generated by genetic algorithm, where the setup time is taken into account.Then the preventive maintenance plan for each machine according to the assigned tasks of the machine and its failure probability distribution is adaptively determined.The original schedule meanwhile should be slightly modified by right-shifting strategy according to inserted time intervals for PM activities, thus the optimal integrated plan of JSP and PM is obtained.A classical benchmark instance is extended and used to verify the effectiveness of the proposed method.The comparative results show that the explicit consideration of the setup time improves the scheduling performances and makes the PM plan generated according to the machining time and failure probability distribution much more reasonable.

job-shop scheduling problem; setup time; preventive maintenance; distribution of failure probability

2014-11-24。 作者简介:喻明让(1986—),男,博士生; 张英杰(通信作者),男,教授,博士生导师。 基金项目:国家科技重大专项资助项目(2012ZX04010-071)。

时间:2015-03-18

http:∥www.cnki.net/kcms/detail/61.1069.T.20150318.0940.003.html

10.7652/xjtuxb201506003

TH166

A

0253-987X(2015)06-0016-06