从 中删除工序 ，通过在中增加工序的直接后续工序构造 ，t=t+1。
步骤4：返回步骤2直至构造一个完整的调度，由此得到的调度为活动调度。
3.3交叉，变异算子
交叉是最主要的遗传运算，遗传算法的性能在很大程度上取决于采用的交叉运算的性能，根据赌轮盘法[6]从父代群体中选择双亲，采用单点顺序交叉法生成后代。变异算子采用互换变异操作，随机从染色体中选择两个基因进行互换。
3.4选择算子
选择是遗传算法的推动力，采用扩大的采样空间，从双亲和后代种群中选择 个最优的个体作为下一代的双亲。并且增加记忆操作，把截止当前的最优解记录下来，在下次迭代中，若最优解优于该值，则替代之。运算结束时输出该值，即为寻得的最优解。
3.5初始温度的确定
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一，初始温度高模拟退火，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，可节约计算时间，但全局搜索性能可能受到影响[7]。
初始温度可以用 估计，其中 为充分大的数， 为目标函数的最坏情况 和最好情况 的差值，实际计算可以选 等值，此时对应的 0.9048,0.9512,0.9900等，已经达到充分大的要求，这里取 为所有工件所有工序加工时间之和； 为所有工件中所需加工时间最长的工件的加工时间，这是目标函数的两个可以估计的上下界，由此确定的初始温度可以保证是足够大的。
3.6计算过程
车间调度问题是最小化问题，可以通过下边的方法直接将目标函数转化成适应度函数：
 （5）
计算步骤如下：
步骤1：初始化种群数目，交叉概率 ，变异概率 ，退火速率 ，输入机器顺序矩阵 ,，加工时间矩阵 ，计算初始温度 。
步骤2：随机产生个个体构成初始群体，并进行解码。令最优值 为当前种群的最优个体， 。
步骤3：判断当前温度是否小于给定的终止温度，若是，结束；否则转步骤4论文开题报告范例。
步骤4：对种群进行交叉操作。
步骤5：对所有个体进行变异操作。
步骤6：对所有各个个体都进行定步长抽样的模拟退火操作，对旧个体采用swap方式产生新个体，以概率 接受后代。
步骤7：保留原种群和产生的新种群中个最好个体，及时更新。
步骤8：令 ，然后进行退火操作 ， 并返回步骤3。
步骤9：输出结果，并结束计算。
4. 实验结果与分析
为了测试上述所提出算法的性能，本文选取了Brandimarte基准问题和经典的Benchmarks基准问题模拟退火， Brandimarte基准问题包括工件数分别为（6，10，20），机器数为（6，10，5）的3个问题实例，Benchmarks基准问题包括工件数从10到30之间，机器数从5到15之间的8个问题实例在不同的范围的相同条件下的几个测试参数基准被选择，现采用文献[8]中提到的MT06， MT10和MT20的MGA的表现，和文献[9]中提到的LA01、LA06、LA11、LA16、LA21、LA26、LA31和LA36的LA类问题。
Table 1. Comparison of the MGA, SA, GA resulting dataof experiment
表1 比较MGA,SA,GA的计算结果
|
问题
|
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
2/2 首页 上一页 1 2 |
