预测调度的算法研究和性能分析

《预测调度的算法研究和性能分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、预测调度的算法研究和性能分析摘要现代制造企业在经济全球化的环境下面临着前所未有的竞争压力，对生产管理提出了更高的要求。调度是对稀缺资源进行优化分配。一个好的调度可以使生产企业提高生产效率、节约生产成本，从而为企业带来巨大的经济效益。大部分调度问题都是NP-hard的，求解这类问题，一种常用的方式就是找到有效的启发式算法，以合理的计算代价求出较好的结果。过去大量的研究成果集中在离线算法和在线算法方面，对可以预测到部分未来信息的情况考虑较少。本文将预测控制的思想应用到调度问题中，提出了预测调度算法，并研究了其在三类典型的调度问题中对改善性能的作用。归纳起来，本论文主要做了以下三个方

2、面的工作：ò针对单机加工、有到达时间约束、最小化总加权完工时间的调度问题，提出了一种预测调度算法，证明了预测调度算法在该问题上的竞争比下界为2，和在线算法的竞争比相同。这表明，在性能保证方面预测调度算法和在线算法是相同的。但对一般情况的实例进行了大量的仿真，从统计的意义上说明预测调度算法优于在线算法的。ò针对同速机，有到达时间约束，最小化最大完工时间的问题上，提出I了一种预测调度算法。通过仿真，发现该算法在极差情况下的性能比小于原来最优的在线算法，这说明该算法的性能保证可能优于在线算法。对一般情况下的实例也做了大量的仿真，结果说明，预测调度算法的性能优于在线算法。ò针对一类信息

3、不准确的Jobshop问题，提出了一种预测调度算法。在预测窗口内，使用移动瓶颈算法求解子问题；在窗口外，用较简单规则进行虚拟调度。通过仿真，与静态算法比较，发现预测滚动机制的引入，在一定程度上可以改善调度性能。关键词：预测调度，竞争比，总加权完工时间，最大完工时间IITHERESEARCHANDPERFORMANCEANALYSISOFPREDICTIVESCHEDULINGALGORITHMSABSTRACTWiththeeconomyglobalization,todaymanufacturersarefacingmorepressurethanever.Theyhaveh

4、igherrequirementonproductionscheduling,whichmeansanoptimizedassignmentofrareresources.Awell-plannedschedulecanraiseefficiency,savecostandthushelptoincreasetheprofitofthecompany.MostschedulingproblemsareNP-hard.Ageneralwaytosolvetheseproblemsistodesignaheuristicalgorithmthatcangivegoodresulta

5、tacceptablecomputationcost.Inthepastmostresearchesfocusedonoff-linealgorithmsandon-linealgorithms,withlittleconsiderationofsuchconditionthatfutureinformationcanbepartlypredicted.Inthisdissertation,weintroducetheessenceofpredictivecontrolintoschedulingproblems.Weproposepredictiveschedulingalg

6、orithmsforthreetypicalproblemsandstudytheimprovementofperformance.Insummary,themainresearchworkofthisdissertationliesinthreeaspectsasfollows:òForminimizingtotalweightedcompletiontimeforsinglemachineproblemwithreleasetime,wedesignapredictiveschedulingalgorithm.Wealsoprovethatthelowerboundofpr

7、edictiveschedulingalgorithmsisIII2,whichisthesameasthecompetitiveratioofon-linealgorithms.Thissuggestspredictiveschedulingalgorithmsworksthesameason-linealgorithmsinperformanceguarantee.Formoregeneralinstances,wesimulatealotandshowthatthepredictive