新工件到达干扰下单机最大延迟时间重调度

《新工件到达干扰下单机最大延迟时间重调度》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第29卷第4期系统工程学报Vol.29No.42014年8月JOURNALOFSYSTEMSENGINEERINGAug.2014新工件到达干扰下单机最大延迟时间重调度刘乐,周泓(北京航空航天大学经济管理学院,北京100191)摘要:在一批新工件突然到达的干扰条件下,研究了总序位干扰量受上限的单机最大延迟时间重调度问题.在建立起若干结构化占优性质和针对部分排序的两种下界计算式的基础上,开发了含两阶段的启发式算法以及精确求解问题的分支定界算法.通过数值实验对比考察了分支定界算法在较小规模算例上的计算效率,并分析了两阶

2、段启发式算法在较大规模算例(总工件数n不小于100)上的解质量与适用条件.实验结果表明,所提分支定界算法在n不超过16算例上的计算耗时显著优于CPLEX优化软件;对于干扰容许率不小于0.6,或者新工件比例不小于0.95而干扰容许率在0.1以内的较大规模算例,宜采用所提出的两阶段启发式算法进行求解.关键词:重调度;单机;最大延迟时间;序位干扰量;启发式;分支定界中图分类号:N945;TP301文献标识码:A文章编号:10005781(2014)04049413Single-machinerescheduling

3、ofminimizingthemaximumlatenesswiththedisruptivearrivalofnewjobsLiuLe,ZhouHong(SchoolofEconomicsandManagement,BeihangUniversity,Beijing100191,China)Abstract:Underanunexpectedarrivalofnewjobs,thispaperconsidersthesingle-machinemaximumlate-nessreschedulingproblem

4、subjecttoanupperlimitonthetotalsequencedisruption.Severalproblem-specificstructuralpropertiesandtwolowerboundsrelatedtopartialsequencesarefirstestablished.Subsequently,atwo-stageheuristicalgorithmandanexactbranch-and-boundalgorithmaredevelopedtosolveofthisproble

5、m.Inournumericalexperiments,theefficiencyofthebranch-and-boundalgorithmwascomparativelyexaminedforsmall-sizedinstances,andsolutionqualityandapplicabilityofthetwo-stageheuristicalgorithmwereana-lyzedforinstanceswithnotlessthan100jobs.Experimentalresultsrevealtha

6、tthebranch-and-boundalgorithmsignificantlyoutperformstheCPLEXoptimizerinexecutiontimeforinstanceswithupto16jobs,andincaseoftoleranceratesnotlessthan0.6,orratiosofnewjobsnotlessthan0.95correspondingtotolerancerateslessthan0.1,thetwo-stageheuristicalgorithmisreco

7、mmendedforrelativelylarge-sizedinstances.Keywords:rescheduling;singlemachine;maximumlateness;sequencedisruption;heuristic;branchandbound1引引引言言言实际的生产过程中各种干扰事件会随时出现,如新工件到达、机器故障、订单撤销、交货期变更、误操作等.突发的干扰往往导致原调度方案执行起来不再顺畅,甚至不再可行,继而亟需对原调度进行修复或调度收稿日期:20121213;修订日期:201

8、30418.基金项目：国家自然科学基金资助项目(71071008);教育部人文社科研究青年基金资助项目(14YJCZH098);济南大学科研基金资助项目(XKY1322).第4期刘乐等:新工件到达干扰下单机最大延迟时间重调度495再生成,于是便引出了生产运作中的重调度问题[1−3].生产重调度旨在能动、快速地修复废弃的原调度或编制出可行的新调度;在尽量小