| 并行机问题的模拟退火调度算法研究 |
| |
| 引用本文： | 史烨,李凯.并行机问题的模拟退火调度算法研究[J].运筹与管理,2011,20(4). |
| |
| 作者姓名： | 史烨 李凯 |
| |
| 作者单位： | 1. 合肥工业大学管理学院,安徽合肥 230009;中国科技大学管理学院,安徽合肥 230026
2. 合肥工业大学管理学院,安徽合肥,230009 |
| |
| 基金项目： | 国家高技术研究发展计划(863); 重点项目(2008AA042901); 国家自然科学基金项目(70631003,70871032,70971035); 安徽省自然科学基金资助项目(11040606Q27); 合肥工业大学博士专项科研资助基金项目(GDBJ2010-025) |
| |
| 摘 要： | 研究了一类调度目标是最小化最大完成时间的并行机调度问题.考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解.分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法.除了交换变换,还引入插入变换以改变各子调度中作业个数.大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解.
|
| 关 键 词： | 调度 并行机 最大完工时间 模拟退火 |
Research on Simulated Annealing Scheduling Algorithm for Parallel Machine Problem |
| |
| SHI Ye,LI Kai.Research on Simulated Annealing Scheduling Algorithm for Parallel Machine Problem[J].Operations Research and Management Science,2011,20(4). |
| |
| Authors: | SHI Ye LI Kai |
| |
| Institution: | SHI Ye1,2,LI Kai1(1.School of Management,Hefei University of Technology,Hefei 230009,China,2.School of Management,University of Science and Technology of China,Hefei 230026,China) |
| |
| Abstract: | This paper considers a kind of parallel machine scheduling problem with minimizing makespan.Considering the NP-hardness of this problem,the simulated annealing approach is introduced to obtain the near-optimal solutions with high quality.The limitation of the existing simulated annealing algorithm for this problem is analyzed.Two kinds of machines,crucial machine and non-crucial machine,are identified.A simulated annealing algorithm including a process of local optimization is designed.Apart from the swap o... |
| |
| Keywords: | scheduling parallel machine makespan simulated annealing |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
