维修时点预测的动态车间调度问题

匡鹏　吴尽昭

摘要：针对制造业中生产计划的不确定问题，提出一种维修时点预测与自适应的遗传模拟退火算法相结合的优化调度方法。该方法首先利用差分自回归移动平均模型预测设备未来的故障率，然后借助电气设备的威布尔（Weibull）分布模型逆向求出设备未来故障发生时刻，最后将此作为约束条件，利用自适应的遗传模拟退火算法解决传统的生产调度问题。结合工厂实际情况，主要分析了设备有无维修的随机调度问题，以最小化最大完工时间为目标，获取每一个任务的调度计划以及每一台设备的维修时点，确定出最佳调度方案。实验表明自适应的遗传模拟退火算法的性能较好。在河北某工厂的生产车间中，设备在运行调度方法后三个月的平均故障率比运行前相对降低了3.46%。

关键词：自回归移动平均模型；设备故障率；遗传算法；模拟退火算法；生产调度

中图分类号：TP277.3

文献标志码：A

0引言

随着工业4.0时代的到来，互联网与工业的融合将完全颠覆现有模式，包括供应链体系、生产体系以及售后体系。这就意味着在生产环节将实现更大的柔性和可变性、模块化与自主性以及自主产品与自主生产系统等。因此要实现工厂的智能生产、提高智能工厂的运行效率，智能调度系统就必须提供优化决策。生产调度[1]是目前生产管理中最为薄弱的环节，也是最困难的一环，已成为目前计算机集成制造系统研究中的一个瓶颈。

其次，制造业中设备的故障率和维修率[2]越来越受关注，特别是在生产过程中导致订单无法正常交付、工厂受到损失，因此工厂对于设备维修时点[3]的确定非常需要。以往的研究大多假设为理想的调度环境，但在实际的制造系统中，常常存在许多不确定的因素，如工件的加工时间不确定[4]、机器故障、紧急插单或者更改交货期等。流水型企业中生产车间的优化调度问题[5]已经成为提高企业生产效率的核心问题。

虽然目前智能调度的研究与实践不断取得新的进展，但是数据的完整性缺乏，导致了很多研究只是关注系统研究以及算法优化，鲜有关注设备层面的优化，没有考虑设备的负载率，没有将机器预防性维修与生产调度相结合。设备运行制定合理的动态维修方案才是生产车间所需要的。基于以上分析本文重点讨论将设备的维修时点作为一个因素考虑到生产调度中，结合实际的车间安排确定出最佳的设备维修时点以及生产任务。

1问题描述

1.1原问题描述

在传统的生产车间内，成品必须经过每一道工序，每一道工序在同一类型的设备上加工。只有设备正常运转，成品才能按时按量交付给客户。传统工厂中通过设备的月度维修或季度维修来维持设备的正常运转，一般都是车间管理人员基于实践经验或有限的计算分析来确定每个月或每个季度的维修时点，实际效果很难保证设备的正常运转。目前对不确定问题主要采用随机变量、拟合、时间序列分析以及统计学等进行描述。用随机变量描述不确定因素，需知道其概率分布函数，由设备历史加工数据分析出设备的加工时间服从指数分布。时间序列分析是根据系统观测得到的时间序列数据，通过曲线拟合和参数估计来建立数学模型的理论和方法。对设备的历史故障率数据采用时间序列分析模拟出差分自回归移动平均模型（AutoRegressive Integrated Moving Average model， ARIMA）[6]。对设备历史维修时点分析满足威布尔（Weibull）分布模型，通过对参数进行有效估计，确定维修时点函数。因此本文采用随机变量、时间序列分析以及统计学的方法对设备维修时点进行预测，从而达到降低设备故障率的目标，促进生产。

本文在充分考虑制造型企业车间中的不确定因素的前提下，建立不确定车间调度问题模型。目前对于不确定调度问题，主要采用遗传算法[7]、蚁群算法[8]、模拟退火算法[9]以及混合算法[10]等进行优化。本文针对车间调度问题模型，采取两种不同的交叉和变异策略设计出了基于自适应模拟退火遗传算法。假定情境为m台机器n个不同的任务，每个任务有m道工序，以相同的顺序在m台机器上加工。对于生产调度问题约束条件为：工件在同一类型的设备上只能被加工一次；任何时刻某一台机器只能加工一个工件；每一个产品的加工过程不允许插队加工。在实际生产中，本文通过此算法优化随机流水车间调度问题。仿真结果显示，改进算法具有更好的优化性能，其效果可行有效，能对实际生产起到一定的指导作用。

1.2条件假设

1）假设工件的首道工序的实际开始时间为0；

2）假设每道工序在指定的机器类型上加工；

3）假设每一台设备同一时刻只能加工一件工件；

4）假设每一工件的工艺路线是已知的；

5）假设任何工件各道工序加工的前提是该工件前一道工序必须加工完成；

6）假设每台设备每个月必须维修一次，且维修时长确定。

2.3设备维修时点动态调整

2.3.1设备故障率预测

借助可编程逻辑控制器（Programmable Logic Controller， PLC）数据库获取的设备历史故障率数据，分析设备故障的预测，从而为设备维修策略提供初始数据，最终提高设备利用率。本文研究的故障率数据取自中间数据库，中间库是对不同设备的PLC数据库进行抽取来得到有效的数据。针对复杂的数据，本文主要利用时间序列的方法建立预测模型，把设备历史故障率数据看成时间序列的一组动态数据，这些动态数据是非平稳的，需要考虑对序列进行平稳化处理。本文利用差分的方法对数据进行平稳化处理，建立ARIMA模型进行预测分析。利用随机序列的自相关和偏相关函数图判断ARIMA模型的阶次p和q的取值范围。

图2中表明数据的平稳性较好。对此数据进行自相关函数和偏相关函数分析，由图3中的自相关图可以看到，在第8步滞后的自相关系数显著不为零，而第8步之后都接受“系统为零“的假设，故有在图2中，在显著性水平α=0.05时，接受原假设系统为零的95%的置信区间。由图3知在第8步之后都接受系数为零的假设，得出

0≤q≤8。同理，由偏相关函数图可知0≤p≤11。利用赤池信息量准则（Akaike Information Criterion， AIC）判定较为理想的模型。通过比较得模型ARIMA（7，6）的AIC值是最小的，即ARIMA（7，6）模型是更为理想的预测模型。

通过理想模型计算第81个故障率数据的预测值，为7.637%，利用递推的方法可以实现对后19个数据进行预测。预测出的后20个数据与实际的20个数据的对比如图4所示。计算出预测值与实际值的拟合优度R2=0.6003，实验结果显示效果是可观的。

2.3.3设备加工时间不固定

由历史数据分析知，设备的加工时间在区间内小范围地波动，数据趋势服从指数分布。

2.4情况分析

通过对设备维修时点的三种情况分析可以发现，没有维修时点是理想的状况。工件最小完工时间是否无限接近理想状况是本研究评判的一个标准。因为实际情况只要涉及设备维修一定会占用设备运转的时间，也会对当天的产量有影响，以致于订单的交货期不得不向后延期。因此本文将设备的维修时点设定为动态可变，以此保证设备的运转更符合实际情况。实验不断地对模型的参数进行调节，使得维修时点被合理地安排，既可以保证订单的按时完成，同时也能提高设备的运行效率。

3混合算法设计

以最大完工时间Cmax为目标，采用遗传算法和模拟退火算法相结合的方式，提出了一种

自适应的遗传模拟退火算法

（Adaptive algorithm of Genetic Algorithm and Simulated Annealing algorithm， AGASA），该算法将模拟退火算法嵌入到自适应遗传算法的循环体中，以利用模拟退火算法具有较强的局部搜索能力、并且能够使搜索过程避免陷入局部最优解的特点。

3.1优化库的建立

优化库建立的目的主要是存储优秀种群，本文设计了三种不同类型的库：第一种是初始种群库，用来存储各种状态下最后一次迭代所产生的种群；第二种是分类索引库，用来将每次迭代后产生的种群划分为若干类，并以此时的状态、温度作为索引；第三种是优化结果库，用来存储每次优化计算后所得到的温度调节参数和最优解。

3.2遗传算法设计

1）初始值。采用自然数编码，用一段顺序码表示工件处理的优先级顺序，数字表示工件号。初始种群一部分采用随机方法产生，另一部分利用机器学习[12]方法产生，以提高初始种群的适应性。

2）计算适应值。直接把目标值Cmax作为适应值，即：f=Cmax。

3）遗传操作。交叉操作有以下两类：

第一类在第二个任务列中随机选择一个交叉区域，将第二个任务列中的交叉区域加到第一个任务列对应的位置，删除第一个任务列中已存在第二个任务列的交叉区域中出现过的工件序号。

第二类对父代以适应度函数值进行排序，适应度小的与适应度小的配对，适应度大的与适应度大的配对；然后利用混沌序列确定交叉点的位置，最后对确定的交叉项进行交叉。

4实验结果分析

在本文的实验中，实验数据采集河北某工厂的历史数据。根据历史数据设定设备的加工时间在区间[5，10]（单位：min）内随机波动，每一个工件都需要经过5道工序。在算法设计中取种群数为40，交叉概率为0.65，变异概率为0.15，t0=100℃，λ=0.95，Pr=0.93，N=1，终止温度为0.0001℃。

4.1设备加工时间固定且不考虑设备维修

目前工厂中生产一件产品需要经过5道工序，实验选取10个待加工工件，已知工件i在机器j上的加工的时间为T，初始化为：T={tij|1≤i≤n，1≤j≤m}={{8，6，9，5，8}，{11，5，6，6，9}，{8，7，5，8，6}，{12，5，5，7，5}，{9，6，7，6，8}，{10，10，8，8，7}，{9，8，6，9，5}，{11，5，7，8，8}，{10，9，5，6，5}，{8，7，5，10，9}}。

实验结果表明此问题的最优值结果为75，工件的加工次序依次为：1—5—2—10—8—6—3—4—7—9。即5台机器同时加工，将这10个工件全部加工完毕最快需要75min。为此本文将75定义为最优值，将76定义为次优值。表1是混合遗传模拟退火算法、遗传算法与模拟退火算法在解决此类问题时的测试结果。

4.2设备加工时间固定且维修时点固定

流程工厂一般都是选择一个固定的时间按照设备类型选择某一个时间段进行设备维修。实验中假设所有设备统一维修，且需要单位时间（假设为1）进行维修。需要对下一道工序的设备维修的时间与下一个工件的开始加工时间进行判断。通过混合算法算出此问题的最优值结果为75，次优值为76，然后通过反复的迭代，表2表明混合算法的效果较好。

对比表1和表2可以看出，当设备需要维修时，有可能不影响全部工件的加工，如果设计的搜索算法能找到此时刻，就达到了本文的目的。通过AGASA的搜索，最优值的比例降低了13.79%，效果还是比较可观的。

4.3设备加工时间与维修时点都不固定

将设备的加工时间设定为随机，维修时点按照本文预测的结果动态变化。维修时点是根据往常的设备故障率模拟出设备未来的维修时点，实际情况一般在预测维修时点的前后5个单位时间（本文采用单位为小时）内波动，即预测的时间前后相差5个单位时间左右为正常维修时点。任务数有6个时，根据智能调度方法得出最优排序：1—3—6—4—5—2；任务数为30时的最优排序：15—25—30—9—13—24—7—12—27—1—3—6—18—19—21—4—5—10—11—16—17—22—23—28—29—2—8—14—20—26。

通过表3分析得知，有无维修的方差在同种情况下的变化率分别为11.05%、10.06%、15.22%。从数据上分析是相对稳定的，说明在有维修情况下对整体任务的完成影响度是比较可靠的。

4.4故障率效果

在生产车间实际运行本文策略三个月之后，通过图6数据可以发现设备的故障率得到了一定程度的下降。将本文的策略在工厂中实践之后，6月故障率确实有明显上升，这主要是由于设备的工作量比之前要大，设备预测的效果也不是很好，但是实验参数经过调整之后，后面2个月的故障率有明显下降。

运行本文策略后三个月的运行结果与未运行该策略的前三个月相比，设备的平均故障率相对降低了3.46%。

5结语

本文首先通过PLC采集河北某胶管工厂设备的故障率数据，并设计了一种预测设备故障发生时刻的模型，并通过模拟实际的数据，契合效果较好。本文结合遗传算法和模拟退火这两种算法的优缺点，提出了一种自适应的智能调度算法，并分析了此算法在车间调度问题中的应用，结果表明该算法能更好地继承父代的优良特征产生的新解，而且该算法结合设故障率预测方法应用到实际工厂中也取得了较好的效果。

本文对设备的故障模拟效果还不是最佳，由于车间设备的故障影响因子非常复杂，维修时长也不确定，因此仍然有许多问题需要进一步研究和完善。车间调度理论模型是在一些假设情况下得到的，与实践之间也还有一些差距；而且生产车间的生产线增加，调度方案是否仍具有稳定的可扩展性也是下一步要研究的问题。

参考文献：

[1]JIN Y L， JIANG Z H， HOU W R. Multi-objective integrated optimization research on preventive maintenance planning and production scheduling for a single machine [J]. The International Journal of Advanced Manufacturing Tcchnology， 2008， 39（9）： 954-964.

[2]WEINSTEIN L， CHUNG C-H. Integrating maintenance and production decisions in a hierarchical production planning environment [J]. Computers and Operation Research，1999， 26（10/11）： 1059-1074.

[3]ALCAIDE D， RODRIGUEZ-GONZALEZ A， SICILIA J. An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns [J]. European Journal of Operation Research， 2002， 140（2）： 384-398.

[4]ALLAHVERDI A， MITTENTHAL J. Scheduling on a two-machine flow shop subject to random breakdowns with a makespan objective function [J]. European Journal of Operation Research， 1995， 81（2）： 376-387.

[5]李素粉，朱云龙，尹朝万.具有随机加工时间和机器故障的流水车间调度[J].计算机集成制造系统，2005，11（10）：1425-1429. （LI S F， ZHU Y L， YIN C W. Flow shop scheduling with stochastic processing times and machine breakdowns [J]. Computer Integrated Manufacturing Systems， 2005， 11（10）： 1425-1429.）

[6]卞晓灵.ARIMA模型在设备故障预测中的应用[J].科技信息（学术版），2008（8）：42-45. （BIAN X L.The application of equipment failure prediction ARIMA model[J].Science & Technology Information， 2008（8）： 42-45.）

[7]PERKGOZ C， AZARON A， KATAGIRI H， et al. A multi-objective lead time control problem in multi-stage assembly systems using genetic algorithms [J]. European Journal of Operational Research， 2007， 180（1）： 292-308.

[8]黄亚平，王万良，熊婧.基于改进蚁群算法的智能调度系统设计与开发[J].浙江工业大学学报，2010，38（3）：251-256. （HUANG Y P， WANG W L， XIONG J. Design and implementation of intelligent scheduling system based on improved ant colony algorithm [J]. Journal of Zhejiang University of Technology， 2010， 38（3）： 251-256.）

[9]石利平.模拟退火算法及改进研究[J].信息技术，2013（2）： 176-178. （SHI L P. Research on simulated annealing algorithm and improvement [J]. Information Technology， 2013（2）： 176-178.）

[10]张扬，杨松涛，张香芝.一种模拟退火遗传算法的传感器网络数据融合技术研究[J].计算机应用研究，2012，29（5）：1860-1866. （ZHANG Y， YANG S T， ZHANG X Z. Research on wireless sensor networks data aggregation on simulated annealing genetic algorithm [J]. Application Research of Computers， 2012， 29（5）： 1860-1866.）

[11]马存宝，李柯，包羽.故障时间观测的机电系统可靠性估计[J].机械与电子，2012（9）：3-6. （MA C B， LI K， BAO Y. Reliability estimation of mechanical and electrical system based on the observed failure time [J]. Machinery & Electronics， 2012（9）： 3-6.）

[12]YANG Z， QI C. Preventive maintenance of a multi-yield deteriorating machine： using reinforcement learning [J]. System Engineering — Theory & Practice， 2013， 33（7）： 1647-1653.

[13]NOURELFATH M， CHTELET E. Integrating production，inventory and maintenance planning for a parallel system with dependent components [J]. Reliability Engineering and System Safety， 2012， 101： 59-66.

[14]FITOUHI M-C， NOURELFATH M. Integrating noncyclical preventive maintenance scheduling and production planning for a single machine [J]. Reliability Engineering and System Safety， 2012， 136（2）： 344-351.

[15]MADUREIRA A， PEREIRA I. Intelligent bio-inspired system for manufacturing scheduling under uncertainties [C]// Proceedings of the 2010 10th International Conference on Hybrid Intelligent System. Piscataway， NJ： IEEE， 2010： 109-112.

[16]曾樑，周丹晨，周战强.基于改进遗传退火算法的生产智能调度系统[J].计算机工程与设计，2011，32（10）：3504-3506. （ZENG L， ZHOU D C， ZHOU Z Q. Intelligent production scheduling system based on improved genetic annealing algorithm [J]. Computer Engineering and Design， 2011， 32（10）： 3504-3506.）

[17]邓辉，吴尽昭.线性半代数变迁系统的近似互模拟等价[J].吉林大学学报（工学版），2013，43（4）：1052-1058. （DENG H， WU J Z. Approximate bisimulation for linear semi-algebraic transition systems[J].Journal of Jilin University （Engineering and Technology Edition）， 2013， 43（4）： 1052-1058.）

[18]刘红军，赵帅.一种基于混合遗传算法的车间生产调度的研究[J].制造业自动化，2011（17）：33-35，59. （LIU H J， ZHAO S. Study on job-shop scheduling based on hybrid genetic algorithm [J]. Manufacturing Automation， 2011（17）： 33-35，59.）

[19]赵卫.模拟退火遗传算法在车间作业调度中的应用[J].计算机仿真，2011，28（7）：361-364. （ZHAO W. Job-shop scheduling based on genetic algorithm and simulated annealing algorithm [J]. Computer Simulation， 2011， 28（7）： 361-364.）