并行机问题的模拟退火调度算法研究

《并行机问题的模拟退火调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第20卷第4期2011年8月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．20。No．4Aug．2011并行机问题的模拟退火调度算法研究史烨1’2，李凯1(1．合肥工业大学管理学院。安徽合肥230009；2．中国科技大学管理学院．安徽合肥230026)摘要：研究了一类调度目标是最小化最大完成时间的并行机调度问题。考虑到此问题的NP．hard特性，引入模拟退火算法思想以获取高质量近优解。分析了现有此问题模拟退火算法的缺陷，定义了关键机器和非关键机器，设计了一个包含局部优化的模拟退火算法。除了交换变换，还引入插入变换

2、以改变各子调度中作业个数。大量的随机数据实验用于验证算法解的质量和计算效率，实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解。关键词：调度；并行机；最大完工时间；模拟退火中图分类号：TP30l；0223文章标识码：A文章编号：1007-3221(2011)04-0104．04ResearchonSimulatedAnnealingSchedulingAlgorithmforParalleIMachineProblemSHIYel．．。LIKail(1．SchoolofManagement，HefeiUniversityofTechnolo

3、gy，Hefei230009，China；2．SchoolofManagement，UniversityofScienceandTechnologyofChina，Hefei230026，China)Abstract：Thispaperconsidersakindofparallelmachineschedulingproblemwithminimizingmakespan．Consid—efingtheNP-hardnessofthisproblem，thesimulatedannealingapproachisintroducedtoobtainthene

4、ar—optimalsolutionswithhighquality．Thelimitationoftheexistingsimulatedannealingalgorithmforthisproblemisana—lyzed．Twokindsofmachines，crucialmachineandnon—crucialmachine，areidentified．Asimulatedannealingal—gorithmincludingaprocessoflocaloptimizationisdesigned．Apartfromtheswapoperatio

5、n，theinsertionoperationispresentedtochangethenumberofthesub—schedules．Alargesetofrandomlygeneratedinstancesaremadetotestthesolutionqualityandtheefficiencyofthealgorithm．Computationalresultsshowthatthesimulatedannealingalgorithmproposedinthispapercansolvetheproblemswithlargesizeinare

6、asonabletime．Keywords：scheduling；parallelmachine；makespan；simulatedannealing’0引言并行机问题是一类重要的调度问题并一直受到广泛的关注，相关的研究成果也较丰富。Leeeta1．It]、Cheng&Sin‘21、Mokotoff[31等对现有研究成果进行了总结。Li&Yang[41从建模方法、松弛技术和算法设计等方面对一类并行机调度问题进行了较为详细地综述。收稿日期：2009．12．02基金项目：国家高技术研究发展计划(863)重点项目(2008AA042901)；国家自然科学基金项目(

7、70631003。70871032，70971035)；安徽省自然科学基金资助项目(11040606Q27)；舍肥工业大学博士专项科研资助基金项目(GDBJ2010—025)．作者简介：史烨(1987)．男。江苏常州人．硕士研究生，研究方向为生产调度，优化算法；李钒(1977)。男。安擞蓉城人，讲师，博士，研充方向为生产调度。企业能源管理．优化算法，人工智能等。第4期史烨．等：并行机问题的模拟退火调度算法研究105本文将针对一类并行机调度问题进行研究。其中给定一组作业：-，。，厶，⋯，_，。，每个作业均可调度到一组机器肘。，肘：，⋯，肘。中的任意某一机器上加工

8、。一个作业在每一时刻只能被一个机器加工