考虑状态维护策略与工时恶化作用下的单机调度研究

裴霞 吴晓 郭鹏 王昕 温昆

摘 要：为了解决单机调度问题，提高设备的可靠性和稳定性，根据连续故障检测和离散故障检测的特点，以最小化拖期成本和维护成本为目标，建立了考虑分段线性恶化和维护不可用时间的单机调度模型，基于系统可靠性理论研究考虑机器可靠性的单机调度问题，采用决策条件统一化处理方法对维护策略进行对比，通过单因素和双因素调参分析确定相关参数变化对生产调度优化的影响。结果表明：模型求解时间与单位时间拖期成本的减少呈近似指数级增长，单位拖期成本越大，求解速度越快;单位时间拖期成本的变化不会引起维护成本的大幅度改变，成本函数不存在柔性周期维护中的跳跃节点，不能“自适应”调节;预防性维护时间与故障小修比值对离散检测下的维护决策有较大影响。采用决策条件统一化处理方法，可减少计算时间和检测成本，较好地解决了离散故障检测中易出现的过度维护或维护不足等问题，有助于降低运营成本，提高经济效益。

关键词：生产管理;连续故障检测;离散故障检测;工时恶化;单机调度;整数规划

中图分类号：TH186   文献标识码：A   doi：10.7535/hbkd.2020yx05001

Abstract：In order to solve the single machine scheduling problem， and improve the reliability and stability of the equipment， a single machine scheduling model considering piecewise linear deterioration and maintenance unavailability time was established according to the characteristics of continuous fault detection and discrete fault detection. Based on the system reliability theory， the single machine scheduling problem considering machine reliability was studied， and the advantages and disadvantages of maintenance strategy were compared by unified processing of decision conditions. The influence of related parameter changes on production scheduling optimization was determined by single factor and two factor adjustment analysis. The results show that the solution time of the model increases exponentially with the decreasing direction of unit delay cost， and the greater the unit delay cost， the faster the solution speed. The change of delay cost per unit time will not cause a significant change in maintenance cost， and the cost function does not have jumping nodes in flexible periodic maintenance， so it can not be adjusted adaptively. Ratio of preventive maintenance time to fault minor maintenance time has great influence on maintenance decision under discrete detection. The unified processing method of decision conditions can reduce the calculation time and detection cost， and better solve the problems of excessive maintenance or insufficient maintenance in discrete fault detection. These will help to reduce operating costs and improve economic benefits.

Keywords：production management;continuous fault detection; discrete fault detection; deteriorating jobs; single machine scheduling; integer programming

伴随着工业互联网的兴起[1]，产业数字化转型成为传统行业的发展趋势，一站式机械零部件制造云平台应运而生[2]，生产调度与设备维护相互影响且互为耦合[3]。如何在保证加工质量和效率的同时提高设备的可靠性和稳定性已成为制造行业的热点之一。生产调度研究最早可追溯到20世纪50年代，它是以一个或多个指标最优为目标，在一定约束条件下安排工件加工位置和时间的决策过程，有研究对此进行了探讨。郑先鹏等[4]通过对生产调度问题中的作业车间调度问题目标进行分解，设计改进了自适应遗传算法求解问题，并指出该问题是典型的NP-hard问题。单机调度模型也是生产调度模型中的一种，在实际加工过程中工件开工与加工时间不是固定的，由设备性能衰退或作业延迟处理帶来的加工惩罚加大了单机调度问题的难度。如何在考虑工时恶化的情况下，实现生产调度与设备维护策略的最佳适配，对于降低车间运作成本和按时交货至关重要。

工时恶化效应自GUPTA等[5]首次提出以来，受到了业界和学术界的广泛关注。其中，GAWIEJNOWICZ等[6]对近40年来在时间依赖调度领域的研究进行了全面回顾，阐述了不同任务的处理时间取决于任务的开始时间，重点讨论了时间依赖性调度问题的计算复杂度以及求解这些问题的算法。JAFARI等[7]研究了分段线性工时恶化单机调度问题，证明该问题为NP-hard问题。GUO等[8]研究了以最小化总延迟为目标的工时阶梯恶化单机调度问题。随后，CHENG等[9]研究了以完工时间最小为目标的工时阶梯恶化单机调度问题。近年来，LI等[10]提出了同时考虑加工时间可控和工时恶化效应的单机调度问题;LIANG等[11]研究了具有工时恶化效应和资源分配的单机调度问题，并设计了启发式算法与分支定界算法求解相关问题;陈海潮等[12]研究了具有线性恶化的并行机调度问题;GUO等[13]研究了具有工时阶梯恶化效应的并行机调度问题;在此基础上，GUO等[14]提出了同时考虑工时阶梯恶化和安装次数的并行机调度问题，并设计了混合离散布谷鸟搜索算法求解。

设备在生命周期内会经历不同的性能衰退状态。维护作为一种支持功能，在保证产品质量和交货期、提高满意度等方面起着重要作用，维护不当会产生“过维护”（指过度维护）或“欠维护”（指维护不足）的状况。“过维度”将加大设备剩余价值浪费，增加维护成本;“欠维护”将影响产品质量和实际交付时间，降低顾客的满意度。因此，如何根据实际生产情况选择合适的维护决策方案引起了业界和学界的广泛关注。KRIM等[15]研究了以完工时间最小为目标的定期预防性维修单机调度问题，并证明该问题是Np-hard问题;LEE等[16]研究了考虑一次维护的单机调度问题，设计了动态规划算法求解相关问题;JOO等[17-18]引入遗传算法求解维护次数受限的生产调度问题，随后去掉了维护次数约束进行拓展研究;王昕等[19]研究了考虑周期性维护与工时恶化的单机调度问题;ZHANG等[20]研究了考虑恶化效应和维护活动的单机调度问题。基于状态的维护决策研究主要从设备可靠性约束方面展开讨论，崔维伟等[21]在单机系统里引入了故障小修，为保证决策模型有效，设计了遗传算法和枚举算法进行优化对比;为说明可靠度随维护次数增加而下降的情况，李有堂等[22]在多设备混联系统中引入了役龄递减因子与故障率递增因子;杨宏兵等[3]通过建立Markov决策模型获得模型最优方程，设计了强化学习算法求解预防性维护单机调度问题。

综上可知，考虑设备维护和恶化效应的生产调度研究已较为丰富，但部分研究理论作出的假设使其成果不能得到很好的应用。例如设备维护策略多样，而多数研究集中于单次维护策略下的生产调度优化，忽略了改变维护策略、优化建模方向等方式。此外，工时恶化函数多样，但多数研究采用一般线性函数，使用分段线性恶化描述的还较少，且多数研究从生产时间角度进行优化，忽略了生产与维护之间的矛盾关系。

本文根据连续故障检测（通常根据设备状况设置故障率阈值Zcm，根据故障率阈值比对决策预防性维护位置）和离散故障检测（通常根据最优设备利用率下的维护周期T来设置维护决策）的特点，以最小化拖期成本和维护成本为目标，建立考虑分段线性恶化和维护不可用时间的单机调度模型，基于系统可靠性理论，研究了考虑机器可靠性的单机调度问题，采用决策條件的统一化处理实现维护策略的优劣对比，通过单因素和双因素调参分析确定相关参数变化对生产调度优化的影响。

1 问题描述

假设生产车间中有n个工件集合为Jj={J1，J2，…，Jn}在机器M上加工，工件基本加工时间aj={a1，a2，…，an}，恶化率bj={b1，b2，…，bn}，交货期dj={d1，d2，…，dn}，机器在同一时刻只能加工一个工件且在加工过程中不允许中断。考虑机械加工设备性能衰退造成的工时恶化效应，将加工设备分为正常作业、恶化作业、失效3个作业状态。pj为实际加工时间，sj为连续加工时间，h为设备恶化期，σ为设备恶化系数，α为单位时间拖期惩罚成本，Δ为极大常数。一旦该设备连续加工时间超过设备恶化期，将面临加工性能恶化。采用分段线性函数表述工时恶化情况，表达式如下：pj=aj， sj≤h，

aj+bj×（sj-h）， s>h。

故障率能较好地表征设备状态条件。基于故障率的维护策略，可通过采用连续故障检测或离散故障检测获取故障率数据，从而对设备故障率作出准确评估。维护成本主要分为维护动作成本和维护时间成本，维护动作成本MM包含故障小修、预防性维护及维护检测的操作成本，维护时间成本MT用停机时间表示，故障小修和预防性维护会导致停机。

假设所有工作均在零时刻准备就绪，设备完成维护活动后，性能可恢复至初始状态。采用GRAHAM等[23]提出的三参数表示法描述状态维护策略下考虑工时恶化的单机生产调度问题：1|nr，pj=aj+max{0，bj×（sj-h）}，dpm|ω1Dmax+ω2Mmax。（1）  式中：1表示单机;nr表示工件加工和设备维护均不可中断;dpm表示基于条件的动态维护;ω1 和ω2分别是生产部门和维护部门的权重系数;ω1Dmax+ω2Mmax表示将从成本角度出发，以最小化工件延误成本和设备维护成本为目标。

2 数学模型

2.1 连续故障检测维护模型的建立

n个工件调度后有n个位置，位置下标为l，其他模型符号与定义如表1所示。

3.1 连续/离散检测策略比较

两种策略决策条件不同，通过决策条件“统一化”（连续故障检测根据设备状况设置故障率阈值Zcm，通过对故障率与故障率阈值进行比较来决策预防性维护位置;离散故障检测是根据最优设备利用率下的维护周期T来决策维护位置。为了对两种检测方法进行对比，通过系统故障率分布函数，将离散故障检测的维护周期T转化为故障率，该转化过程定义为决策条件“统一化”）实现T与故障率的转化。

将离散检测策略最优维护周期代入T=100×tc/tr，得T=200，令t=200，代入λ（t）=t/5 000中得故障率为0.04。因此，在算例对比分析中，连续故障率检测策略设置故障率阈值Zcm=0.04，离散故障率检测策略设置最优维护周期T=200。基本加工时间aj服从[1，100]的均匀分布，交货期dj服从aj+U（0，3aj]，n∈{5，10}，保持加工环境不变，各生成5组算例。计算结果如表4所示，其中，CD表示连续检测，DD表示离散检测。

对表4分析可知：同一算例连续检测和离散检测所得的最优调度方案相同，拖期成本也相同，而离散检测的成本总是少于连续检测的成本。模型运算时间上，离散检测模型计算时间比连续检测模型的计算时间长，特别是算例规模变大时，区别更为明显。为了同时优化计算时间和成本，可采取决策条件“统一化”方法。通过数值仿真计算得出连续检测策略下的调度序列，再用离散检测的最优维护周期进行检测并决策维护操作点，实现计算时间和检测成本的减少。

3.2 单位时间拖期成本的影响

针对同一算例，采用单因素控制法调整单位时间拖期成本参数。大量数据实验结果显示，在调整α参数时，两种方案所表示的趋势相同，故选取一种进行分析。当α足够小时，Gurobi求解器不能在限定时间内获得规模为10的小规模算例的最优解。图1和图2分别显示了2个算例单位时间拖期成本对总成本目标和运算时间的影响情况。

对图1分析可知：总成本和拖期成本与单位时间拖期成本α呈线性相关，线性函数斜率与算例中的作业数据有关。维护成本基本无变化，不存在周期性维护[19]中的多个跳跃点节点（跳跃点节点是指在某一个参数比值对应的节点，目标函数值会往靠近固定周期维护目标值的方向突变）。图2显示了模型求解时间与α的关系，可以发现：单位时间拖期成本α越大，求解速度越快。

3.3 维护与小修时间比值的影响

离散故障率检测的决策条件T对tc/tr比值依赖性强，为探究该参数比值对两种方案的影响，需进行调参分析。保持tr=5，Zcm=0.04不变，令tc={1，5，10，15，20，25，30，35，40}，改变维护时间参数进行实验，得到如表5所示的调度方案成本。将总成本进行分解，得到tc/tr比值变化下的各项成本情况，如图3所示。

由表5可知：维护时间tc的增加不影响连续检测CD维护决策下的调度方案，但对离散检测DD维护决策有较大影响。CD维护决策由故障率阈值决定，因此维护位置不发生改变。若以CD调度方案为标准，DD调度方案则存在过维护或欠维护的情况。例如表5中tc=1为过维护，tc=35和tc=40为欠维护。

图3为tc/tr比值变化下的各项成本情况。通过分析可知，tc主要影响DD的维护成本，对拖期成本影响不大。当tc=1时，使用离散检测策略导致了过维护，但各项成本值均低于使用连续检测策略下的情况，这说明基于故障率阈值条件决策维护得到的结果并不总是最优的。

4 结 论

本文研究了状态维护策略与工时恶化作用下的单机调度问题，基于连续故障检测和离散故障检测两种维护策略的特点，分别以最小化最大拖期成本和维护成本为目标，建立了考虑分段线性恶化和维护不可用时间的单机调度模型。通过对计算结果进行分析，得到如下结论。

1）离散检测模型运算时间比连续检测长，但成本更少，采用决策条件“统一化”处理，可减少检测成本与模型运算时间。

2）维护成本基本不随单位时间拖期成本发生变化，不存在周期性维护中的多个跳跃节点，不能“自适应”调节，模型运算时间随单位时间拖期成本的减少呈指数级增长。

3）预防性维护时间与故障小修时间比值对离散检测维护决策有较大影响，存在过维护或欠维护状态，但基于故障率阈值条件的连续检测维护决策得到的调度方案不一定最优。

本文基于系统可靠性理论，探讨了考虑机器可靠性的单机调度问题，但研究中也存在着不足之处。在模型建立方面，仅考虑了分段线性恶化和维护不可用时间，有必要考虑负载、可变时长维护等因素带来的成本不确定性，在维护策略的选择上应设计算例与其他策略进行优劣对比;在数据来源方面，仅参考相关文献随机生成数据。未来应与机械加工企业合作，获取真实的生产数据，使研究结果更能直接反映实际情况，进一步探索将状态维护策略与两阶段线性工时恶化应用到更为复杂的生产系统中。

参考文献/References：

[1] 姚锡凡，景轩，张剑铭，等.走向新工业革命的智能制造[J/OL].计算机集成制造系统，2020：1-30[2020-03-12]. http：//kns.cnki.net/kcms/detail/11.5946.TP.20200312.1339.010.html.

YAO Xifan， JING Xuan，ZHANG Jianming，et al.Towards smart manufacturing for the new industrial revolution[J/OL].Computer Integrated Manufacturing Systems， 2020：1-30[2020-03-12]. http：//kns.cnki.net/kcms/detail/11.5946.TP.20200312.1339.010.html.

[2] 孫学珊，杨欣，李民.工业云平台的构建与服务新模式研究[J].中国市场， 2019（2）： 191-192.

SUN Xueshan， YANG Xin， LI Min.Research on the construction of industrial cloud platform and new service mode[J]. China Marketing，2019（2）： 191-192.

[3] 杨宏兵，沈露，成明，等. 带退化效应多态生产系统调度与维护集成优化[J]. 计算机集成制造系统， 2018， 24（1）： 80-88.

YANG Hongbing，SHEN Lu，CHENG Ming，et al.Integrated optimization of scheduling and maintenance in multi-state production systems with deterioration effects[J]. Computer Integrated Manufacturing Systems， 2018，24（1）： 80-88.

[4] 郑先鹏， 王雷.面向作业车间调度问题的遗传算法改进[J]. 河北科技大学学报， 2019， 40（6）： 496-502.

ZHENG Xianpeng，WANG Lei.Improved genetic algorithm for job shop scheduling[J]. Journal of Hebei University of Science and Technology， 2019， 40（6）： 496-502.

[5] GUPTA J N D， GUPTA S K. Single facility scheduling with nonlinear processing times[J].Computers & Industrial Engineering， 1988， 14（4）： 387-393.

[6] GAWIEJNOWICZ S. A review of four decades of time-dependent scheduling： Main results， new topics， and open problems[J].Journal of Scheduling， 2020. doi：10.1007/s10951-019-00630-w.

[7] JAFARI A A， LOTFI M M. Single machine scheduling to minimize the maximum tardiness under piecewise linear deteriorating jobs[J]. Scientia Iranica， 2017. doi：10.24200/sci.2017.4408.

[8] GUO P， CHENG W M， WANG Y. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs[J]. Journal of Industrial Management Optimization， 2017， 10（4）： 1071-1090.

[9] CHENG T C E， KRAVCHENKO S A， LIN B M T. Scheduling step-deteriorating jobs to minimize the total completion time[J].Computers Industrial Engineering， 2020. doi：10.1016/j.cie.2020.106329.

[10] LI L， WANG J J. Scheduling jobs with deterioration effect and controllable processing time[J].Neural Computing Applications， 2016， 29： 1163-1170.

[11] LIANG X X， LIU M， FENG Y B， et al. Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology[J]. Engineering Optimization， 2020， 52（7）： 1184-1197.

[12] 陳海潮， 程文明， 郭鹏， 等. 混和进化算法求解具有分段恶化效应的并行机调度问题[J]. 计算机系统应用， 2020， 29（4）： 10-17.

CHEN Haichao，CHENG Wenming，GUO Peng，et al.Hybrid evolutionary algorithm for solving parallel machine scheduling problems with step-piece deteriorating processing time[J].Computer System & Applications，2020， 29（4）： 10-17.

[13] GUO P， CHENG W M， ZENG M. Scheduling step-deteriorating jobs on parallel machines by mixed integer programming[J]. Journal of Donghua University（English Edition）， 2015， 32（5）： 709-714.

[14] GUO P， CHENG W M， WANG Y. Parallel machine scheduling with step-deteriorating jobs and setup times by a hybrid discrete cuckoo search algorithm[J]. Engineering Optimization， 2015， 47（11）： 1564-1585.

[15] KRIM H， RACHID B， DUVIVIER D， et al. Heuristics for the single machine weighted sum of completion times scheduling problem with periodic maintenance[J]. Computational Optimization and Applications， 2020，75（1）： 291-320.

[16] LEE C Y， LEON V J. Machine scheduling with a rate-modifying activity[J]. European Journal of Operational Research， 2001， 128（1）： 119-128.

[17] JOO C M， KIM B S. Genetic algorithms for single machine scheduling with time-dependent deterioration and rate-modifying activities[J]. Expert Systems with Applications， 2013， 40（8）： 3036-3043.

[18] JOO C M， KIM B S. Machine scheduling of time-dependent deteriorating jobs with determining the optimal number of rate modifying activities and the position of the activities[J]. Journal of Advanced Mechanical Design Systems & Manufacturing， 2015. doi：10.1299/jamdsm.2015jamdsm0007 .

[19] 王昕， 吳晓， 郭鹏， 等. 考虑周期性维护与工时恶化的单机调度研究 [J]. 河北科技大学学报， 2020， 41（3）： 201-209.

WANG Xin， WU Xiao， GUO Peng， et al. Single machine scheduling with time-based maintenance and step-deteriorating jobs[J].Journal of Hebei University of Science and Technology， 2020， 41（3）： 201-209.

[20] ZHANG X， YIN Y， WU C C. Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine[J]. Engineering Optimization， 2017，49（1）：84-97.

[21] 崔维伟， 陆志强. 单机系统的生产调度与预防性维护的集成优化[J]. 上海交通大学学报， 2012， 46（12）： 2009-2013.

CUI Weiwei，LU Zhiqiang. Integrating production scheduling and preventive maintenance planning for a single machine[J]. Journal of Shanghai Jiaotong University， 2012， 46（12）： 2009-2013.

[22] 李有堂， 程钥， 任泽海.基于可靠性的混联系统的动态预防性维护策略[J]. 兰州理工大学学报， 2018， 44（6）： 35-38.

LI Youtang，CHENG Yue，REN Zehai.Dynamic preventive maintenance strategy for hybrid system based on reliability[J].Journal of Lanzhou University of Technology，2018， 44（6）： 35-38.

[23] GRAHAM R L， LAWLER E L， LENSTRA J K， et al. Optimization and approximation in deterministic sequencing and scheduling： A survey[J]. Annals of Discrete Mathematics， 1979， 5（1）： 287-326.

[24] 金琳， 黄开敏， 周晓军.租赁设备的多阶段预防性维护策略及优化[J]. 计算机集成制造系统， 2013， 19（12）： 2947-2953.

JIN Lin， HUANG Kaimin，ZHOU Xiaojun.Multi-period preventive maintance policy and optimization for leased equipment[J].Computer Integrated Manufacturing Systems，2013， 19（12）： 2947-2953.

[25] 于捷， 申桂香， 贾亚洲.基于三参数威布尔分布的数控机床的可靠性评价[J]. 现代制造工程， 2007（5）： 26-28.

YU Jie， SHEN Guixiang，JIA Yazhou.Reliability evaluation on CNC lathes based on the three Weibull distributions[J].Modern Manufacturing Engineering， 2007（5）： 19-20.