问题 | n,m | MGA | SA | GA |
MT06 | 6,6 | 55 | 55 | 55 |
MT10 | 10,10 | 930 | 939 | 997 |
MT20 | 20,5 | 1165 | 1227 | 1247 |
LA01 | 10,5 | 666 | 666 | 666 |
LA06 | 15,5 | 926 | 926 | 926 |
LA11 | 20,5 | 1222 | 1222 | 1222 |
LA16 | 10,10 | 945 | 979 | 979 |
LA21 | 15,10 | 1058 | 1083 | 1156 |
LA26 | 20,10 | 1218 | 1253 | 1328 |
LA31 | 30,10 | 1784 | 1784 | 1836 |
LA36 | 15,15 | 1291 | 1321 | 1384 |
在同样的参数和终止标准的执行下,改进遗传算法(MGA)、简单遗传算法(GA)与模拟退火算法(SA)之间的计算结果见表1,从表1的结果来看改进遗传算法(MGA)的结果优于简单遗传算法(GA)与模拟退火算法(SA)。
5.结束语
车间调度问题已经证明为NP问题[10],难以找到能够求得最优解的确定性调度算法。又由于遗传算法的优良特性,因此,采用遗传算法对车间调度问题进行求解已成为求解该类问题的趋势。本文提出的基于混合遗传算法的调度算法,同时融入模拟退火算法赋予搜索过程一种时变且最终趋于零的概率跳跃性,避免陷入局部最优并最终趋于全局最优。仿真实验表明了该改进遗传算法是可行的、有效的、具有较好的搜索能力。
参考文献:
[1]GERVEY M R,JOHSON D S,SOTHI R..The complexity offlowshop and jobshop scheduling[J].Mathematics and OperationsResearch1976(1):117-129.
[2]R. Cheng, M. Gen and Y. Tsujimura, “A tutorialsurvey of jobshop scheduling problems using genetic algorithms – I.Representation”, Computers and Industrial Engineering, 1976(30):983–997
[3]D. E. Goldberg, Genetic Algorithms in Search,Optimization and Machine Learning, Addison Wesley, New York, 1989.
[4]L. Wang and D. Z. Zheng, “An effective hybridoptimization strategy for job-shop scheduling problems”, Computers andOperations Research, 28, pp. 585–596, 2001.
[5]G. Shi, “A genetic algorithm applied to a classicjob-shop scheduling problem”, International Journal of Systems Science, 28(1),pp.25–32, 1997.
[6]Srinivas M,Patnaik L M.G enetic algorithm s:asurvey[J].C om puter,1994,27(6):17~26.
[7]B. Hajek, “Cooling schedules for optimalannealing”, Mathematics of Operations Research, 13(2), pp. 311–329, 1988
[8]J. F. Muth and G. Thompson, Industrial scheduling,Prentice Hall, Englewood Cliffs, NJ, 1963.
[9]S. Lawrence, “Resource constrained projectscheduling: an experimental investigation of heuristic scheduling techniques”,Graduate School of Industrial Administration, Pittsburgh, Carnegie Mellon University, 1984
[10]Blazewicz J, Finke G,Haopt G. New trends inmachine scheduling. European Journal of Operational Research, 1988; 37: 303—317