考虑设备周期性维护的单机调度问题研究.pdf 10页

'中国科技论文在线http://www.paper.edu.cn考虑设备周期性维护的单机调度问题研究**吴玉洁，谢勇（华中科技大学自动化学院，武汉430074）5摘要：针对单机调度问题，在考虑周期预防性维护的基础上，以最小化最大拖期为优化目标，建立了整数规划模型来决策工件的最优加工顺序。针对模型的特点，本文提出了一种两阶段启发式算法(TwoStageHeuristicAlgorithm,TSHA)，依据批次的最优排序规则，获得一个初始调度序列，再通过对批次松弛时间的充分利用，在不增大最大拖期的前提下，使最大10拖期工件前移或者使最大拖期工件的开工时间提前，进而获得更优的调度安排。通过计算实验，与CPLEX最优解以及已有启发式算法的解作对比，结果表明，本文所提出的启发式算法性能更加优异，能有效解决工件不可中断情况下的以周期性维护为资源约束的单机调度问题。关键词：单机调度；周期性维护；最大拖期；松弛时间；启发式算法15中图分类号：TP202+.7Single-machineschedulingwithperiodicmaintenanceWUYujie,XIEYong(SchoolofAutomation,HuazhongUniversityofScience&Technology,Wuhan430074)20Abstract:Thispaperconsidersasingle-machineproblemwithperiodicmaintenancewhichtheobjectiveistominimizethemaximumtardiness.Aintegerprogrammingmodelisdevelopedtofindaoptimalschedule.Weproposeatwostageheuristicalgorithminwhichaninitialsolutionisobtainedfirstwiththebatchorderingruleandthenthesolutionisimprovedbyleft-shiftingthemosttardyjoboradvancingit’sstartingtime.Throughcomputationalexperiments,theperformanceoftheproposed25heuristicisevaluatedbycomparingthesolutionwiththoseobtainedfromCPLEXandanexistingheuristicalgorithm,andtheresultshowsthatthepresentedheuristiccansolvethesingle-machineschedulingproblemsubjecttoperiodicmaintenanceandnonresumablejobseffectively.Keywords:single-machine;periodicmaintenance;maximumtardiness;slacktime;heuristicalgorithm30354045作者简介：吴玉洁(1993-)，女，硕士研究生，主要研究方向为供应链管理、物流管理通信联系人：谢勇(1974-)，男，副教授、硕导，主要研究方向为供应链管理、物流管理.E-mail:76280788@qq.com-1- 中国科技论文在线http://www.paper.edu.cn0引言长期以来，设备维护和生产调度是独立研究的。然而，这与实际状况并不符合，生产调度和维护计划是紧密相关的，生产调度作业会使设备负荷变化，并抢夺设备维护的时间；维50护会改变设备的故障率，带来机器的一个不可用时间段分布。因此，更为贴近实际的生产调度模型应该将维护活动考虑在内。本文将探讨以最小化最大拖期为目标函数，以周期性维护[1][2]为资源约束的单机调度问题，该问题是一个NP难题。按照Pinedo提出的问题表示法，该问题可被表示为1npmptpmTmax，pm和npmpt分别表示周期性维护和工件不可中断。目前，国内外学者将维护活动和生产调度结合考虑时，依据生产过程中机器进行维护的[3]55次数大致分为两类：一类是单次维护，另一类是多次维护。在第1类研究中，Mane和Ghadle针对每个工件对机器役龄影响因子相同的情况，以最小化提前、拖期、截止期总费用为目标，[4]提出了一种多项式时间算法，来确定维护位置、公共交货期以及加工序列。而Wan根据炼钢工业的问题特性，解决了各工件加工时间相同的情况下的生产调度问题。在第2类研究中，可以再根据维护活动方式的不同，分为周期性维护和柔性维护。周期性维护的时间节点在调[5]60度之前就确定已知。Liao和Chen以单机系统为研究对象，以最小化最大拖期为目标函数，[6]分析了周期维护下调度序列的最优解性质，基于该性质提出了一种启发式算法。Sbihi研究[7]了相同的问题，并提出一种结合分支定界法的启发式算法。Chen探讨了以最小化拖期工件数量为优化目标的集成调度问题，提出了一种基于Moore算法的启发式算法来获得最优的[8]调度序列。张思源将问题延伸至流水线车间，并提出了结合增量式进化策略、局域搜索机65制、种群密度管理的混合遗传算法，对问题进行优化求解。柔性维护活动具有柔性时间窗口，[9]维护活动的时间节点可调整。Yang首次考虑了柔性维护和单机调度的联合优化问题，证明[10]了该问题是一个NP难题。Chen以最小化平均流动时间为优化目标，从不同的视角建立了[11]四种二元混合整数规划模型，并通过实验比较了它们的模型复杂性。蒋志高首次提出虚拟维护的概念，针对多阶段维护且加工时间可变的单机和并行机生产系统，利用维护次数的70上界来建模，并提出了改进的变领域搜索算法和混合粒子群算法。1周期性维护下的单机调度问题建模1.1问题描述本文研究的周期性维护下的单机调度问题。假设有n个工件J1,J2,,Jn等待在同一台机器上加工，每个工件都有各自的处理时间pj和交货日期dj。加工过程中，机器并不是一75直持续可用的，需要定期进行维护，连续两次维护活动之间的时间间隔是固定的，维护活动的开始时间也是确定的，如图1所示。TtTtR1R2J[1]...J[i-1]M1J[i]...J[k]M2...B1B2图1考虑周期性维护的单机调度-2- 中国科技论文在线http://www.paper.edu.cn本文作出如下假设：801)工件之间的加工顺序无约束2)所有工件在零时刻均已就绪3)工件的加工不需要准备时间4)工件加工过程中不允许中断5)设备同一时刻最多只能加工一个工件851.2周期性维护下的单机调度问题的数学模型数学规划方法是求解机器调度问题的常用方法之一。近年来，随着计算机技术的发展，出现了诸如CPLEX、GLPK等高性能的数学规划问题求解器，可以快速求解线性规划、混合整数规划、二次规划等一系列规划问题。针对问题1npmptpmTmax，本节将建立问题的整数规划模型。90决策变量表示如下：1工件j在第i个位置加工xij(1)0其他1加工第i个位置的工件后进行维护y[i](2)0其他辅助决策变量表示如下：Bi为第i个加工批次；[i]为第i个加工位置；i[j]为批次Bi中的第j个加工位置；J[i]为95第i个位置加工的工件；p[i]为J[i]的加工时间；d[i]为工件i的交货时间，c[i]为J[i]的完工时间；L[i]为J[i]的延迟时间；T[i]为J[i]的拖期时间；e[i]为J[i]的完工时间与上一次维护完成时间的时间差；g[i]为工件J[i]所在批次的松弛时间；b[i]为工件J[i]所在批次的总加工时间。它们存在以下关系：np[i]pjxij(3)j1n100d[i]djxij(4)j1e[1]p[1](5)e[i]My[i1]e[i1]p[i](6)e[i]M1-y[i1]p[i](7)e[i]T(8)105b[i]e[i]M1y[i](9)g[i]Tb[i]M1y[i](10)i1i1i1c[i]b[k]g[k]ty[k]e[i](11)k1k1k1L[i]c[i]d[i](12)T[i]max0，L[i](13)110T[i]c[i]d[i](14)-3- 中国科技论文在线http://www.paper.edu.cnTmaxT[i](15)e[i],b[i],g[i],T[i]0(16)式(6)~式(16)中，i,j1,2,,n。其中，M为一个足够大的正数，T为连续两次维护活动之间的时间间隔，t为完成一次维护活动所需要的时间。115模型具体描述如下：MinimizeTmax(17)ns.t.xij1,i1,2,,n(18)j1nxij1,j1,2,,n(19)i11,xiji,j1,2,,n(20)0,1,120y[i]i,j1,2,,n(21)0,式(17)指出目标函数为最小化最大拖期。式(18)和式(19)表示工件和加工位置的一一对应关系。2基于最小批次松弛时间的两阶段启发式算法对于小规模的问题，可以通过商业整数规划求解器来求解。但是，对于大规模问题，求125解器难以在有限时间内获得最优解。启发式算法常常用来解决大规模问题，它是面向具体问题的经验、规则启发出来的方法，在可接受的时间和空间内给出一个可行解，但这个解可能不是最优的。文献[5,6]等也研究了以最小化最大拖期为优化目标的集成调度问题，并提出了相应的启发式算法。但是由于维护周期的固定，它们求得的最优解往往还存在较多的机器空闲时间。130这不仅会造成大量维护资源的浪费，也可能使得到的解不够完美。针对这个问题，本文提出了一个两阶段的启发式算法，通过对松弛时间的充分利用，获得近似最优解。2.1构建批次的调度序列记一个完整的调度序列为S，调度子序列为Si，第i次维护为Mi，Bi的子集为Wi，则SB1,M1,B2,M2,,Bl。令Ri为批次Bi的松弛时间，CMi为第i次维护活动Mi的完成时135间，PWi为工件集Wi的总加工时间，PBi为工件集Bi的总加工时间。性质1：最优调度序列中，批次Bi的松弛时间必须小于其后加工的任一工件的加工时间。即Ripj，对于任一工件JjBk,ki1,i2,。证明：令调度序列SS1,Mi1,Bi,Mi,S2,Mk1,Wk1,Jj,Wk2,Mk,S3，且Ripj。将工件Jj移140至批次Bi最后一个加工工件之后的位置，获得的新的调度序列可表示为"SS1,Mi1,B1,Jj,Mi,S2,Mk1,Wk1,Wk2,Mk,S3。对于任一工件JpWk2，S和S"中Jp的延迟分别为：-4- 中国科技论文在线http://www.paper.edu.cnLpCMk1PWk1pjppdp(22)"LpCMk1PWk1ppdp(23)"145因为pj0，所以LpLpTmax。可知，S"的最大拖期相较S更小。证毕。定理1：最优调度序列中，每一批次Bi中的工件按交货期最早优先规则（EarliestDueDate,EDD）排序。150证明：令调度序列SS1,Ml1,Wl1,Ji,Ji1,Wl2,M,S2，工件Ji的交货期晚于工件Ji1，即didi1。交换工件Ji和Ji1的加工顺序后新的调度序列"SS1,Ml1,Wl1,Ji1,Ji,Wl2,M,S2。在S中，Ji和Ji1的延迟分别为：155LiCMl1PWl1pidi(24)Li1CMl1PWl1pipi1di1(25)在S"中，Ji和Ji1的延迟分别为："LiCMl1PWl1pi1pidi(26)"Li1CMl1PWl1pi1di1(27)160因为00"LL"。pi1，pi，didi1，所以TmaxLi1LiLi，i1i1因此，调度序列S"的最大拖期相较S更小。也就是说，同批次的相邻工件，交货期早的工件应该优先被加工。不断调整相邻工件的位置，直至不存在逆序，这便是最优的批次工件顺序。证毕。165根据性质1和定理1，设计了第一阶段的算法，构建批次的调度序列，具体步骤如下：步骤1：工件排序。将工件按照EDD规则排序，如果工件的交货期相同，再按照SPT规则排序。步骤2：构建批次，生成调度序列。具体步骤如下：1)初始化。令i1，j1，RiT。1702)如果Rip[j]0，则将工件J[j]加入批次Bi，RiRip[j]，转至5）；否则，转至3）。3)在未处理工件中，选择处理时间最长且小于等于Ri的工件Jp，将其加入批次Bi，RiRipp。重复该步骤，直至不存在满足条件的工件。4)安排一次维护活动，开始一个新批次。令ii1，RiT，转至2)。1755)如果jn1，终止。否则，令jj1，转至2）。2.2改善批次的调度序列在上一小节获得的初始批次调度序列的基础上，改善批次的调度序列的基本思想是：在不增大最大拖期的前提下，基于最小批次松弛时间思想，调整工件的加工顺序，使得最大拖期工件前一批次有足够大的空闲时间，再将最大拖期工件左移，或者将与最大拖期工件位于-5- 中国科技论文在线http://www.paper.edu.cn180同一批次且先于其加工的工件左移，从而获得更小的最大拖期。性质2：令调度序列的最大拖期为T[m]，J[p]Bk，J[q]Bl，kl，当：1)当工件J[q]为最大拖期工件时，若p[p]d[p]p[q]d[q]，交换工件J[p]和J[q]的位置可得更小的最大拖期；2)当J[m]Bl，mq，且p[p]p[q]时，即最大拖期工件之前批次存在工件J[p]，它的处185理时间小于最大拖期工件同批次且先于其加工的工件的加工时间，交换工件J[p]和J[q]的位置可得更小的最大拖期。证明：令调度序列SS1,Mk1,Wk1,J[p],Wk2,Mk,S2,Ml1,Wl1,J[q],Wl2,Ml,S3，JiWk2，JjWl2。因为维护周期是固定的，所以若J[m]S1,S2,S3,Wk1,Wl1时，交换工件J[p]和J[q]190的位置对最大拖期没有影响。仅当JmWk2,Wl2,J[p],J[q]时，有可能通过交换获得更小的最大拖期。交换工件J[p]和J[q]位置后的调度序列表示为S"。在S中，工件J[p],Ji,J[q],Jj的延迟时间可以表示为：L[p]CMk1PWk1p[p]d[p](28)LiCMk1PWk1p[p]pidi(29)195L[q]CMl1PWl1p[q]d[q](30)LjCMl1PWl1p[q]pjdj(31)在S"中，工件J[p],Ji,J[q],Jj的延迟时间可以表示为："""L[p]CMk1PWk1p[p]d[p](32)""LiCMk1PWk1p[p]pidi(33)"""200L[q]CMl1PWl1p[q]d[q](34)""LjCMl1PWl1p[q]pjdj(35)""""显然，p[q]p[p]，p[p]p[q]，d[q]d[p]，d[p]d[q]。"当工件J[q]为最大拖期工件时，因为p[p]d[p]p[q]d[q]，所以可得L[q]L[q]Tmax。即S"有更小的最大拖期。"205当工件Jj为最大拖期工件时，因为p[p]p[q]，所以LjLjTmax。即S"有更小的最大拖期。证毕。根据定理1和性质2，设计了第二阶段的算法，改善第一阶段构建的批次调度序列，具体步骤如下：210步骤1：最大化最大拖期工件前一批次的空闲时间。在不增大Tmax的前提下，前移加工时间较长的工件，直至最大拖期工件的前一批次。具体步骤如下：1)令i1，j1。-6- 中国科技论文在线http://www.paper.edu.cn2)找到使批次Bj和Bi的工件交换后，Bi的松弛时间最小的两个工件。3)将两工件交换，并对批次Bj和Bi按照EDD规则重新排序，计算批次Bj和Bi215中工件的最大拖期，记最大值为Tmax。4)若TmaxTmax，将调度序列恢复为交换前的状态。5)如果jm-1，停止。否则，令ii1，jj1，转至2）。步骤2：在不增大Tmax的前提下，前移最大拖期工件。具体步骤与步骤1类似，产生新的最大拖期为T。max1220步骤3：在不增大Tmax的前提下，提前最大拖期工件的开始加工时间。具体步骤与步骤1类似，将与最大拖期工件同批次且先与其加工的工件前移，产生新的最大拖期为T。max2步骤4：如果Tmax1Tmax2，则新的最大拖期为Tmax2，否则，新的最大拖期为Tmax1。根据2.1节和2.2节的内容，绘制了两阶段启发式算法（TSHA）的流程图，如图2所225示。应用本文提出的两阶段启发式算法（TSHA）对文献[5]的数值示例进行求解，获得的调度序列为J2,J4,J7,M1,J1,J9,J8,M2,J6,J10,J5,M3,J3,J11，最大拖期为17，最大拖期之前批次的松弛时间为{0,0,0}，而文献[5]求得的最大拖期为19，最大拖期之前批次的松弛时间为{0,1,4}。显然，本文提出的TSHA算法获得的解更优。工件按EDD和SPT规则排序构建批次，生成调度序列前移工件，最大化最大拖期工件前一批次的空闲时间230前移最大拖期工件提前最大拖期工件的开始加工时间求得新的最大拖期Tmax1求得新的最大拖期Tmax2Tmax=min(Tmax1,Tmax2)图2两阶段启发式算法流程图3计算实验为了证明两阶段启发式算法(TSHA)的有效性，利用不同的工件规模和参数设置设计实[6]验，将算法TSHA和Sbihi的启发式算法进行对比分析，再将算法TSHA求得的解与规划235求解器CPLEX求得的最优解做比较。-7- 中国科技论文在线http://www.paper.edu.cn[6]实验参数的生成方式与Sbihi相同，设置如下：工件的处理时间为区间[1,10]上的离散nn平均随机变量，交货期为区间[1CQ2i1pi,1CQ2i1pi]上的离散平均随机变量，其中，C为拖期因子，Q为交货期幅度。为了避免算法涉及到的主要参数的不同取值对算法的优劣性判断有影响，拖期因子C、交货期幅度Q、维护周期T、维护时间t取多组240值。交货期幅度Q0.2,0.6，拖期因子C0.2,0.6，它们共有四种组合，分别为C0.2,Q0.2、C0.2,Q0.6、C0.6,Q0.2、C0.6,Q0.6。维护周期和维护时间考虑两种情况，T10,t2和T18,t4。对于每一种问题参数C,Q,n,T,t的组合，随机产生50个问题实例。实验中，算法均使用MATLABR2016a编写，在配置为2.71GHZ处理器、4GBRAM的245DELL-Vostro上运行。为简便起见，下文将Sbihi[6]的启发式算法简记为算法H1。3.1与H1的比较实验问题规模有{10,20,30,40,50,80,110,150,170,200}十种，将算法TSHA和H1进行实验对比分析，实验结果如表1和表2所示。表中TSHA列下的“No”表示算法TSHA的解比H1的解更优的实例数目，“Max”和“Mean”分别表示算法TSHA比H1更优的解中两解的最250大差值和平均差值。同样的，表中H1列下的“No”、“Max”和“Mean”分别表示算法H1的解比TSHA的解更优的实例数目、两解的最大差值及平均差值。表1TSHA与H1的性能比较（c=0.2,Q=0.2）TtnTSHAH1NoMaxMeanNoMaxMean1021025165.006133.332039239.48353.0030443612.654126.2540424619.95122.0050495226.38144.0080507246.020001105012065.800001505013392.4000017050156108.0000020050201134.960001841025205.0410147.502036309.97384.0030444415.38263.5040483919.682138.0050464723.23144.0080508042.200001105010964.620001505013586.400001705015298.5200020050163126.74000注：实验发现，解的优劣性与拖期因子C及交货期幅度Q的取值关系不大，为了展示的简洁性，仅列255出（C,Q）=(0.2,0.2)的实验结果。-8- 中国科技论文在线http://www.paper.edu.cn260表2TSHA与H1的计算时间（单位：秒）比较nTSHAH1100.02810.0159200.03200.0197300.04500.0202400.05350.0207500.05560.0215800.05590.02201100.06570.02311500.07130.02351700.07890.02412000.07990.0258从表1可以看出，比较两个算法获得的优解数目、解的最大差值和平均差值三个方面，算法TSHA较算法H1都更优，而且这种优异性随着问题规模的增大更加突显。当工件数n超过50时，算法TSHA获得更优解的比例接近100%。这是因为算法TSHA充分利用了每个批次的松弛时间，使工件的加工更为紧凑，接近于无维护活动干扰情况下的单机调度。265从表2可以看出，虽然算法TSHA比算法H1的计算时间稍长一些，但两者的差距最多不超过0.06s，而且在问题规模为n=200的情况下，TSHA花费的时间仅为0.0799s。所以说，H1算法的求解速度虽然比算法TSHA更快，但差距并不明显。[6]总的来说，从实验结果可以看出，相较Sbihi提出的启发式算法H1，本文提出的启发式算法TSHA性能更优。2703.2与CPLEX的比较实验分别在工件数为10,15,20的情况下，将算法TSHA和CPLEX得到的最优解进行比较，实验结果如表3所示。表3中“No”表示TSHA求得最优解的实例数目，“Max”和“Mean”分别表示TSHA和CPLEX得到的最优解的最大偏差和平均偏差。(36)Tmax(H1)opt_TmaxTheRelativeError275表3TSHA与CPLEX的性能比较opt_Tmax(C,Q)(T,t)n=10n=15n=20RelativeErrorRelativeErrorRelativeErrorNoMaxMeanNoMaxMeanNoMaxMean(0.2,0.2)(10,3)430.63640.2350430.35290.2367460.11480.0659(10,6)420.56520.2335430.25810.1213440.15460.0642(15,3)410.85710.3413420.60000.4058440.36000.1690(15,6)410.80000.2672420.48840.2101440.30000.1056(20,3)420.68750.2033450.52380.1891460.16130.0847(20,6)420.88890.3797440.34830.1883460.10710.0682(0.6,0.6)(10,3)430.46150.1993450.26530.2253470.16670.1006(10,6)450.29550.1465460.20510.1428460.11850.0488(15,3)420.47370.2542420.27270.1754440.26670.1439(15,6)420.53570.1714430.33330.1638440.20000.1066(20,3)420.34620.1541430.20830.0996460.12280.0511(20,6)420.36360.1417430.27540.1305450.14750.0564Time(s)TSHA<0.1<0.1<0.1CPLEX0.3848.54239.80从表3中可以看出，随着工件数目的增大，CPLEX所需要的时间呈指数级的增长，算法TSHA的计算时间始终小于0.1s。在解的优劣性方面，平均情况下，算法TSHA获得最-9- 中国科技论文在线http://www.paper.edu.cn优解的数目为44个（总共有50个），与最优解的平均偏差不超过20%。并且，随着问题规模的增大，算法TSHA的解愈加趋向于最优解，当工件数为20时，与最优解的平均偏差280低至5%。此外，由表3比较可知，随着维护周期T的增大和维护时间t的减小，平均偏差逐渐减少，这是因为此种情况下维护活动次数的减少。4结论本文提出了考虑周期性维护的生产调度集成优化模型，并设计了一种基于最小化松弛时间的两阶段启发式算法对模型进行优化求解。数据实验结果表明，TSHA算法较以往的算法285获得的解更加优异，可在有限时间内获得近似最优解。本文仅研究了单机系统下的集成优化模型，对于多台设备或者混联系统下的集成优化问题等，还需进一步的研究。[参考文献](References)[1]LeeCY.Machineschedulingwithanavailabilityconstraint[J].JournalofGlobalOptimization,1996,9(3):395-416.290[2]PinedoML.Scheduling:Theory,Algorithms,andSystems[J].PottsC.n.vanWassenhoveL.n,2012,1991:35-42.[3]ManeJK,GhadleKP.MaintenanceActivitySingle-MachinesSchedulingandDue-DateAssignmentSimultaneously[J].IjmesCom,2014.[4]WanL.SchedulingJobsandaVariableMaintenanceonaSingleMachinewithCommonDue-Date295Assignment[J].Thescientificworldjournal,2014,2014(2):748905.[5]LiaoCJ,ChenWJ.Single-machineschedulingwithperiodicmaintenanceandnonresumablejobs[J].Computers&OperationsResearch,2003,30(9):1335-1347.[6]SbihiM,VarnierC.Single-machineschedulingwithperiodicandflexibleperiodicmaintenancetominimizemaximumtardiness[J].Computers&IndustrialEngineering,2008,55(4):830-840.300[7]ChenWJ.Minimizingnumberoftardyjobsonasinglemachinesubjecttoperiodicmaintenance☆[J].Omega,2009,37(3):591-599.[8]张思源,陆志强,崔维伟.考虑设备周期性维护的流水车间生产调度优化算法[J].计算机集成制造系统,2014,20(6):1379-1387.[9]DarLiYang,ChingLienHung,ChouJungHsu,etal.MINIMIZINGTHEMAKESPANINASINGLE305MACHINESCHEDULINGPROBLEMWITHAFLEXIBLEMAINTENANCE[J].JournaloftheChineseInstituteofIndustrialEngineers,2002,19(1):63-66.[10]ChenJS.Single-MachineSchedulingwithFlexibleandPeriodicMaintenance[J].JournaloftheOperationalResearchSociety,2006,57(6):703-710.[11]蒋志高.考虑多阶段维护且加工时间可变的车间作业调度问题研究[D].上海交通大学,2011.310-10-'