基于模拟退火的多处理机调度优化算法研究

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (12): 2963-2967.

基于模拟退火的多处理机调度优化算法研究

李凯1,2，左春荣1,2

1. 合肥工业大学管理学院, 安徽合肥 230009; 2. 过程优化与智能决策教育部重点实验室, 安徽合肥 230009

出版日期:2009-12-24 发布日期:2010-01-03

Research on optimization algorithm for multiprocessor scheduling problem based on simulated annealing

LI Kai1,2, ZUO Chun-rong1,2

1. School of Management, Hefei Univ. of Technology, Hefei 230009, China; 2. Key Lab. of Process Optimization and Intelligent Decisionmaking, Ministry of Education, Hefei 230009, China

Online:2009-12-24 Published:2010-01-03

摘要/Abstract

摘要：

研究了目标函数是最小化最大完工时间的多处理机调度问题，此问题被证明是NPhard问题。分析了此问题现有模拟退火算法的缺陷，在此基础上构造了一个模拟退火算法SALZ。大量的随机数据实验用于验证算法的性能和计算效率，实验结果表明SALZ算法优于现有算法。

Abstract:

This paper considers the multiprocessor scheduling problem to minimize makespan. This problem is proved to be an NPhard problem. The limitation of the existing simulated annealing algorithm is analyzed, and then a simulated annealing algorithm, named SALZ, is proposed to obtain nearoptimal solutions with high quality. A large set of randomly generated instances are made to test the performance and efficiency of SALZ. Computational results demonstrate that the proposed algorithm is very accurate and outperforms the existing methods.

李凯1,2，左春荣1,2. 基于模拟退火的多处理机调度优化算法研究[J]. Journal of Systems Engineering and Electronics, 2009, 31(12): 2963-2967.

LI Kai1,2, ZUO Chun-rong1,2. Research on optimization algorithm for multiprocessor scheduling problem based on simulated annealing[J]. Journal of Systems Engineering and Electronics, 2009, 31(12): 2963-2967.