资源描述：
《基于目标增量的无等待流水调度快速迭代贪婪算法_》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、基于目标增量的无等待流水调度快速迭代贪婪算法本课题得到国家自然科学基金（No.60504029和No.60672092）和国家863项目（No.2008AA04Z103）资助。朱夏，女，1982生，博士研究生，主要研究领域为调度优化、服务计算，email：zhuxia@seu.edu.cn；李小平，男，1970生，博士生导师，博士，副教授，主要研究领域为调度优化、服务计算、企业互操作，email：xpli@seu.edu.cn；王茜，女，1946生，博士生导师，教授，主要研究领域为信息集成技术、数据库技术以及计算机协同工作。朱夏,李小平,王茜(东南大学计算机科学与工程学院,南京210096)(
2、计算机网络和信息集成教育部重点实验室，南京210096)摘要:最小化总完工时间无等待流水调度是典型的NP-完全问题，广泛存在于实际生产系统。改变传统求解调度序列目标函数的模式，提出目标增量法，通过目标函数变化量判断新解的优劣，大大降低算法所需计算时间；通过证明启发式算法基本操作的目标增量性质，设计两种基本目标增量法以快速评估新产生解的质量。提出快速迭代贪婪算法FIG（FastIterativeGreedyalgorithm）求解该问题，构造初始解生成算法，提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量。基于110个经典Benchmark实例，将提出的FIG算法与目前求解该
3、问题较好的启发式算法PH1p和元启发式算法SRTS、DPSOvnd进行比较，实验结果表明FIG在性能上优于SRTS和PH1p，略逊于DPSOvnd；在效率上优于SRTS和DPSOvnd，略逊于PH1p。关键字:无等待流水调度，目标增量，启发式算法，总完工时间最小ObjectiveIncrementbasedIterativeGreedyHeuristicforNo-waitFlowshopswithTotalFlowtimeMinimizationXiaZhu,XiaopingLi,QianWang(SchoolofComputerScienceandEngineering,Southeast
4、University,Nanjing,210096)(KeyLaboratoryofComputerNetworkandInformationIntegration(SoutheastUniversity),MinistryofEducation,Nanjing,210096)Abstract: No-waitflowshopswithtotalflowtimeminimizationaretypicalNP-Completecombinatorialoptimizationproblems,widelyexistinginpracticalmanufacturingsystems.Diffe
5、rentfromtraditionalmethodsinwhichobjectivesarecompletelycomputedforanewgeneratedschedule,objectiveincrementmethodsarepresentedinthispaper.Whetheranewscheduleisbetterorworsethantheoriginaloneisjudgedjustbytheobjectiveincrement,whichcanreducecomputationaltimeconsiderably.Objectiveincrementpropertiesar
6、eanalyzedforfundamentaloperationsofheuristics.Basedontheproperties,twofundamentalmethodsareintroducedforfastevaluatingschedules.FIG(FastIterativeGreedyalgorithm)isproposedfortheconsideredproblem,whichincludesinitialsolutiongeneratingandsolutionimprovementphases.Besidesaninitialsolutiongeneratingmeth
7、odbeingconstructed,asegmentbasedreconstructiveheuristicandaniterativeimprovementprocedurearedevelopedforlocalandglobalsearchrespectivelytoimprovethecurrentsolution.FIGiscomparedwithPH1p,SRTSandDPSOvnd
