A simulated annealing approach to makespan minimization on identical parallel machines

被引：7
作者：
Wen-Chiung Lee
Chin-Chia Wu
Peter Chen
机构：
[1] Feng Chia University,Department of Statistics
来源：
The International Journal of Advanced Manufacturing Technology | 2006年 / 31卷
关键词：
Scheduling; Parallel machines; Makespan; Simulated annealing;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper addresses a makespan minimization scheduling problem on identical parallel machines. Several heuristic algorithms have been proposed to tackle the problem. In this paper, a very effective simulated annealing method is proposed to generate the near-optimal solution. Computational results demonstrate that the proposed heuristic is very accurate and that it outperforms the existing methods.
引用
收藏
页码：328 / 334
页数：6
相关论文
共 28 条
[1]  
Gupta JND(2001)A LISTFIT heuristic for minimizing makespan on identical parallel machines Prod Plan Control 12 28-36
[2]  
Ruiz-Torres AJ(1969)Bounds on multiprocessor timing anomalies SIAM J Appl Math 17 416-429
[3]  
Graham RL(1978)An application of bin-packing to multiprocessor scheduling SIAM J Comput 7 1-17
[4]  
Coffman EG(1984)Tighter bounds for the multifit processor scheduling algorithm SIAM J Comput 13 170-181
[5]  
Garey MR(1990)On the exact upper bound for the MULTIFIT processor scheduling algorithm Ann Oper Res 24 233-259
[6]  
Johnson DS(1988)Multiprocessor scheduling: combining LPT and MULTIFIT Discrete Appl Math 20 233-242
[7]  
Friesen DK(1996)Approximate algorithms for the PC Topology 4 345-359
[8]  
Yue M(1998) problem Prod Plan Control 9 685-689
[9]  
Lee CY(1983)A pairwise interchange algorithm for parallel machine scheduling Science 220 671-680
[10]  
Massey JD(1997)Optimization by simulated annealing Comput Ind Eng 33 257-260
123