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

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

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

2、大完成时间到达时间Agent中图分类号：TP301；TPl8文献标识码：AAgent-basedIntelligentAlgorithmforUniformParallelMachineSchedulingProblemLiKaiZuoChunrongRenMinglun(SchoolofManagement。HefeiUniversityofTechnology，脚230009，China)AbstractAuniformparallelmachineschedulingproblemwithreleasedatestominimizemakespa

3、nwasconsidered．ThisproblemisatleastNP—hard．AlgorithmABH，whichwasanintelligentschedulingalgorithmbasedonAgenttechnologyinordertorealizethemanufacturingschedulingprocessrobotizedbymeansoftheintelligenceofmachine，hasbeendevelopedfortheproblem．SemanticdescriptionoftwokindstotheAgent

4、wasgiven．Theresultsandanalysisofquiteextensivecomputationalexperimentswerereportedanddiscussed，andABHalgorithmissuperiortotheexistingalgorithms，anditsaveragerelativeerrorislessthan0．084％．KeywordsUniformparallelmachines，Intelligentscheduling，Makespan，Releasedates，Agent引言很多研究人员致力于

5、将Agent技术应用于企业整合、企业合作、制造过程中的计划与调度、车间级控制以及子整体制造业(holonicmanufacturing)等相关方面的研究⋯t。就传统的调度问题而言，不少文献将Agent用于解决车间作业(jobshop)调度问题[2--4]或流水作业(flowshop)调度问题[5

6、。这两类调度问题均是串行调度问题，而将Agent技术应用到平行机调度的研究成果还很少，尤其是机器速度不同的同类机情形。同类机调度是一类重要的平行机调度问题，其中机器的处理能力具有恒定的差异。针对一类作业不同时到达的同类机调度问题，调度目标是最小化最大完成时间，

7、此问题通常描述为Q。IriC。，。本文为Q。frj『C。，问题构造高性能的调度算法，同时引入Agent技术使得问题中的各机器互相协作以实现调度的智能性，从而实现生产调度过程的自动化。1问题描述在Q。IrjCrux问题中通常作如下假设。给定一组作业Jl'．”，J。，每个作业均可被调度到一组机器M1’．一，M。上，每个机器Mi(i=1，⋯，m)给定一个处理速度si。不失一般性，假定s。≥s2≥⋯≥收稿日期：2008—03—3l修回日期：2008—05—25*国家自然科学基金资助项目(70631003、70871032)、国家“863”高技术研究发展计划资助

8、项目(2008AA042901)和合肥工业大学科学研究发展基金资助项目(071102F)。作者简介：李凯，助理研究员，博士生，主要从事生产调度、企业能源管理、优化算．法、人工智能等方面的研究．E—mail：hfutlk@163．tom万方数据第2期李凯等：基于Agent的同类机智能调度算法185s。。一个作业在每一时刻只能被一个机器加工，并且一个机器在同一时刻只能加工一个作业。作业不允许中断。当作业J，被机器M；加工，此作业将会对应一个加工时间P玎’Pif=pj／sf，其中户，是作业J，的加工时间(又称为作业J，的长度)，Po是作业，i被机器Mi加工所

9、需要的加工时间。作业可能不是在同一时刻到达，即每个作业J，有一个到达时间(releasedat