基于Agent的同类机智能调度算法1

《基于Agent的同类机智能调度算法1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、农业机械学报第40卷第2期基于Agent的同类机智能调度算法*李凯左春荣任明仑(合肥工业大学管理学院，合肥230009)【摘要】研究了目标函数是最小化最大完成时间的同类机调度问题，且作业到达时间可能不同。此问题被证明是NP．hard问题。为此问题构建了一个基于Agent的智能调度算法ABH，使得机器具有一定的智能性，从而实现工厂调度的自动化。给出了用于调度的两类Agent的语义描述，进而给出ABH算法描述。大量随机数据实验结果表明，ABH算法性能明显优越于现有算法，其相对于最优解的平均误差收敛达

2、0．084％。关键词：同类机智能调度最大完成时间到达时间Agent中图分类号：TP301；TP18文献标识码：AAgent—basedIntelligentAlgorithmforUniformParallelMachineSchedulingProblemLiKaiZuoChunrongRenMinglun(SchoolofManagement，HefeiUniversityofTechnology，Hefei230009，China)AbstractAuniformparallelmachi

3、neschedulingproblemwithreleasedatestominimizemakespanwasconsidered．ThisproblemisatleastNP～hard．AlgorithmABH，whichwasanintelligentschedulingalgorithmbasedonAgenttechnologyinordertOrealizethemanufacturingschedulingprocessrobotizedbymeansoftheintelligen

4、ceofmachine，hasbeendevelopedfortheproblem．SemanticdescriptionoftwokindstOtheAgentwasgiven．Theresultsandanalysisofquiteextensivecomputationalexperimentswerereportedanddiscussed，andABHalgorithmissuperiortOtheexistingalgorithms，anditsaveragerelativeerro

5、rislessthan0．084％．KeywordsUniformparallelmachines，Intelligentscheduling，Makespan，Releasedates，Agent中机器的处理能力具有恒定的差异。针对一类作业引言不同时到达的同类机调度问题，调度目标是最小化很多研究人员致力于将Agent技术应用于企业最大完成时间，此问题通常描述为QlrJIC本整合、企业合作、制造过程中的计划与调度、车间级文为QIr，lC。问题构造高性能的调度算法，同时控制以及子整体制造业(hol

6、onicmanufacturing)等引入Agent技术使得问题中的各机器互相协作以实相关方面的研究⋯。就传统的调度问题而言，不少现调度的智能性，从而实现生产调度过程的自动化。文献将Agent用于解决车间作业(iobshop)调度问1问题描述题[2-4]或流水作业(flowshop)调度问题【5l。这两类调度问题均是串行调度问题，而将Agent技术应用在Q1rJjC问题中通常作如下假设。给定到平行机调度的研究成果还很少，尤其是机器速度一组作业一，J，每个作业均可被调度到一组机不同的同类机情形。器

7、M一，M上，每个机器M(i=1，⋯，m)给定同类机调度是一类重要的平行机调度问题，其一个处理速度S。不失一般性，假定S1≥s2≥⋯≥收稿日期：2008—03—31修回日期：2008—05—25*国家自然科学基金资助项目(70631003、70871032)、国家“863”高技术研究发展计划资助项目(2008AA042901)和合肥工业大学科学研究发展基金资助项目(071102F)作者简介：李凯，助理研究员，博士生，主要从事生产调度、企业能源管理、优化算法、人工智能等方面的研究，E—mail：hf

8、utlk@163corn第2期李凯等：基于Agent的同类机智能调度算法185s。一个作业在每一时刻只能被一个机器加工，并器上的当前最优排序序列或近似最优排序序列，且一个机器在同一时刻只能加工一个作业。作业不Ci是机器M寸应的最优值或近似最优值。显允许中断。当作业J被机器M加工，此作业将会然，各机器Agent的Goal的初始值是(O，(2>)，即调对应一个加工时间P¨P，=，／s，其中，是作业度队列为空集，对应的最大完成时间为零。的加工时间(又称为作业J，的长度)，P，是作业J，被Ru是Agen