运筹与管理2011，Vol.20Issue(4)：104-107,112,5.
并行机问题的模拟退火调度算法研究
Research on Simulated Annealing Scheduling Algorithm for Parallel Machine Problem
摘要
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 operation, the insertion operation is presented to change the number of the sub-schedules. A large set of randomly generated instances are made to test the solution quality and the efficiency of the algorithm. Computational results show that the simulated annealing algorithm proposed in this paper can solve the problems with large size in a reasonable time.关键词
调度/并行机/最大完工时间/模拟退火Key words
scheduling/ parallel machine/ makespan/ simulated annealing'分类
信息技术与安全科学引用本文复制引用
史烨,李凯..并行机问题的模拟退火调度算法研究[J].运筹与管理,2011,20(4):104-107,112,5.基金项目
国家高技术研究发展计划(863)重点项目(2008 AA042901) （863）
国家自然科学基金项目(70631003,70871032,70971035) （70631003,70871032,70971035）
安徽省自然科学基金资助项目(11040606Q27) （11040606Q27）
合肥工业大学博士专项科研资助基金项目(GDBJ2010-025). （GDBJ2010-025）
