一种基于改进遗传算法的车间调度问题研究

1、一种基于改良遗传算法的车间调度问题研究论文导读:：作业车间调度是一类求解困难的组合优化问题，本文在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性，最终使算法能够趋于全局最优。在次根底上，将遗传算法和模拟退火算法相结合，提出了一种基于遗传和模拟退火的混合算法，并用实例对该算法进行了仿真研究。结果说明，该算法有教好的收敛精度，是可行的，与传统的算法相比拟，有明显的优越性。论文关键词：遗传算法，车间调度，模拟退火1. 引言作业车间调度：机器先于机器加工工件，工件先于工件在机床上加工模拟退火，式中，其中，式(1)表示目标函数，式(2)(3)(4)表示工艺约束条件决定的各工件的各操

2、作的先后加工顺序以及加工各个工件的各机器的先后顺序。式中，符号和分别为工件在机器上的完成时间和加工时间。3用改良遗传算法(MGA)求解3.1编码方式如何将所研究问题的解转换为由编码形式表达的染色体是遗传算法的关键问题【2】。对JSSP问题，遗传算法的编码常见的有以下几种：基于工序(或操作)的编码、基于工件的编码、基于先后表的编码、基于工件对关系的编码、基于优先规那么的编码、基于机器的编码、基于完成时间的编码、随机键编码、基于析取图的编码【3】。这些编码方法都存在这样或者那样的缺乏，鉴于以上车间调度问题编码方法所存在的问题，提出一个既能保证后代的合法性，又能表征全部解空间，解码又相对简单的编码方

3、法很有必要。本文考虑一个基于工序(或操作)的编码方法用来保证搜索空间是一个完整的解空间，并且任何操作者的所有交换可对应于适宜调度，对于每个基因对应一道工序，代表该工序在进行调度操作时的处理优先级，对于n个工件m台机器的调度问题，一个染色体由个基因组成。考虑3个工件和2台机器问题的机器加工次序矩阵：以及加工的时间矩阵：假设一个任意基于操作的解分别为s = (1，3，2，2，1，3)， 其中1，2和3分别代表工件1，2和3论文开题报告范例。通过一个半活动解码过程，工件的加工次序对于机器1对应3-2-1，对于机器2对应1-2-3。它们对应的makespan(工件完工时间)为7的甘特图如图所示：Fig

4、ure 1. Halfactivities scheduling correspond to tmakespan图1 半活动调度对应的makespan我们认为，活动调度编码是半自主调度编码的一个子集，因此，最优调度方案必须是一个活动调度编码对应的工件完工时间【4】。活动调度编码的应用可以在下一个操作之前检查可能的空白的间隔时间所在最后位置模拟退火，并且在最后操作之前填补前一个空白间隔时间直到最后一个操作转化为半活动调度，导致makespan的长度可以变得更短。 因此，Gantt图(图1)被改变为如下列图2所示，同时，对应的makespan 为6 (最优值)。Figure 2. Activiti

5、esscheduling correspond to tmakespan图2 活动码调度对应的makespan3.2解码算法染色体只包含数字编码。在解码时首先要把基因与工序对应起来，即把优先级赋给对应的工序。设：包含t个已调度工序的局部调度；阶段t可调度工序的集合对应给定的。解码步骤如下：步骤1：令t=0，开始为空的局部调度。初始的包括无紧前工序的所有工序。步骤2：比拟中所有工序的调度优先级，把具有最大优先级的工序(假设为，其上道工序的结束时刻为)尽可能早的参加到中，即从时刻开始对该工序所对应机器上各加工空闲依次判断能否将此工件插入加工。假设能，那么在空闲中插入加工，并修改该机器上的加工队列；

6、否那么，把该工序参加到该机器加工队列的末尾，构造一个新的局部调度。步骤3：按如下步骤更新数据集：从中删除工序，通过在中增加工序的直接后续工序构造，t=t+1。步骤4：返回步骤2直至构造一个完整的调度，由此得到的调度为活动调度。3.3交叉，变异算子交叉是最主要的遗传运算，遗传算法的性能在很大程度上取决于采用的交叉运算的性能，根据赌轮盘法【6】从父代群体中选择双亲，采用单点顺序交叉法生成后代。变异算子采用互换变异操作，随机从染色体中选择两个基因进行互换。3.4选择算子选择是遗传算法的推动力，采用扩大的采样空间，从双亲和后代种群中选择个最优的个体作为下一代的双亲。并且增加记忆操作，把截止当前的最优解

7、记录下来，在下次迭代中，假设最优解优于该值，那么替代之。运算结束时输出该值，即为寻得的最优解。3.5初始温度确实定温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一，初始温度高模拟退火，那么搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，可节约计算时间，但全局搜索性能可能受到影响【7】。初始温度可以用估计，其中为充分大的数，为目标函数的最坏情况和最好情况的差值，实际计算可以选等值，此时对应的0.9048,0.9512,0.9900等，已经到达充分大的要求，这里取为所有工件所有工序加工时间之和；为所有工件中所需加工时间最长的工件的加工时间，这是目标函数的两个可以估计的上

8、下界，由此确定的初始温度可以保证是足够大的。3.6计算过程车间调度问题是最小化问题，可以通过下边的方法直接将目标函数转化成适应度函数： 计算步骤如下：步骤1：初始化种群数目，交叉概率，变异概率，退火速率，输入机器顺序矩阵,，加工时间矩阵，计算初始温度。步骤2：随机产生个个体构成初始群体，并进行解码。令最优值为当前种群的最优个体，。步骤3：判断当前温度是否小于给定的终止温度，假设是，结束；否那么转步骤4论文开题报告范例。步骤4：对种群进行交叉操作。步骤5：对所有个体进行变异操作。步骤6：对所有各个个体都进行定步长抽样的模拟退火操作，对旧个体采用swap方式产生新个体，以概率接受后代。步骤7：保存

9、原种群和产生的新种群中个最好个体，及时更新。步骤8：令，然后进行退火操作，并返回步骤3。步骤9：输出结果，并结束计算。4. 实验结果与分析为了测试上述所提出算法的性能，本文选取了Brandimarte基准问题和经典的Benchmarks基准问题模拟退火， Brandimarte基准问题包括工件数分别为6，10，20，机器数为6，10，5的3个问题实例，Benchmarks基准问题包括工件数从10到30之间，机器数从5到15之间的8个问题实例在不同的范围的相同条件下的几个测试参数基准被选择，现采用文献中提到的MT06， MT10和MT20的MGA的表现，和文献中提到的LA01、LA06、LA11

10、、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

11、,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问题，难以找到能够求得最优解确实定性调度算法。又由于遗传算法的优良特性，因此，采用遗传算法对车间调度问题进行求解已成为求解该类问题的趋势。本文提出的基于混合遗

12、传算法的调度算法，同时融入模拟退火算法赋予搜索过程一种时变且最终趋于零的概率跳跃性，防止陷入局部最优并最终趋于全局最优。仿真实验说明了该改良遗传算法是可行的、有效的、具有较好的搜索能力。参考文献:【1】GERVEY M R,JOHSON D S,SOTHI R.The complexity offlowshop and jobshop scheduling.Mathematics and OperationsResearch1976(1):117-129【2】R. Cheng, M. Gen and Y. Tsujimura, A tutorialsurvey of jobshop sched

13、uling problems using genetic algorithms I.Representation;, Computers and Industrial Engineering, 1976(30):983997【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 j

14、ob-shop scheduling problems;, Computers andOperations Research, 28, pp. 585596, 2001.【5】G. Shi, A genetic algorithm applied to a classicjob-shop scheduling problem;, International Journal of Systems Science, 28(1),pp.2532, 1997.【6】Srinivas M,Patnaik L M.G enetic algorithm s:asurvey.C om puter,1994,2

15、7(6):1726.【7】B. Hajek, Cooling schedules for optimalannealing;, Mathematics of Operations Research, 13(2), pp. 311329, 1988J. F. Muth and G. Thompson, Industrial scheduling,Prentice Hall, Englewood Cliffs, NJ, 1963.S. Lawrence, Resource constrained projectscheduling: an experimental investigation of heurist