Job Shop Scheduling by Simulated AnnealingAlgorithm Combined with Tabu Search
-
摘要: 针对成批车间的作业排序(Job Shop Scheduling )问题设计了一种模拟退火与Tabu Search相组合的算法.首先用模拟退火算法求得一个初始解,再利用Tabu Search进行进一步的寻优.通过大量的算例分析表明,该算法具有良好的寻优特性与运算效率.Abstract: This paper describes an approximation algorithm for the problem of finding the minimum makespan in a job shop.The algorithm is based on simulated annealing algorithm and tabu search,two generalizations of the well known iterative improvement approach to combinatorial optimization problems.First a start solution is found by the simulated annealing algorithm,then tabu search is used to seek the better solution in order to compensate the disadvantage of large running times by single simulated annealing algorithm.The algorithm in this paper is proved effective and efficient both in computation and convergence by analyzing the results of some experiments on it.
-
1. Simon French B A,Phil D.Sequence and scheduling: An introduction to the mathematics of the Job Shop.Chichester:Ellis Horwood Limited,1982 2. 刘 勇,康立山,陈毓屏.非数值并行算法——模拟退火算法.北京: 科学出版社,1995 3. Glover F.Future paths for integer programming and links to artificial intelligence.Computers Ops Res,1986,13(5): 533~549 4. Reeves C.Modern heuristic techniques for combinatorial problems.Oxford:Blackwell Scientific,1993 5. Laarhover R J,Aarts E H ,Lenstra J K.Job shop scheduling by simulated annealing.Operation Research,1992,40(1): 113~125 6. Adams J,Balas E ,Zawack D.The shifting bottleneck procedure for job shop scheduling.Management Sci,1988,34(3):391~401 7. Glover F,Kelly J P,Laguna M.Genetic algorithms and tabu search hybrids for optimization.Computers Ops Res,1995,22(1): 111~134 -
点击查看大图
计量
- 文章访问数: 2506
- HTML全文浏览量: 144
- PDF下载量: 880
- 被引次数: 0
下载:
