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

作     者：史烨 李凯 SHI Ye;LI Kai

作者机构：合肥工业大学管理学院安徽合肥230009 中国科技大学管理学院安徽合肥230026 

基　　金：国家高技术研究发展计划(863) 重点项目(2008AA042901) 国家自然科学基金项目(70631003 70871032 70971035) 安徽省自然科学基金资助项目(11040606Q27) 合肥工业大学博士专项科研资助基金项目(GDBJ2010-025) 

出 版 物：《运筹与管理》 (Operations Research and Management Science)

年 卷 期：2011年第20卷第4期

页      码：104-107,112页

摘      要：研究了一类调度目标是最小化最大完成时间的并行机调度问题。考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解。分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法。除了交换变换,还引入插入变换以改变各子调度中作业个数。大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解。

主 题 词：调度 并行机 最大完工时间 模拟退火 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 08[工学] 070105[070105] 0701[理学-数学类] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3969/j.issn.1007-3221.2011.04.016

馆 藏 号：203133956...