基于遗传算法的车间调度算法

1、分数：_ _ _ _ _ _ _ _北京南方林业大学研究生课程论文2011-2012学年第一学期课程编号：73327课程名称：Matlab语言论文标题：基于遗传算法的作业车间调度算法学科和专业：运输工程号码：姓氏：涉及教师：王2011年12月基于遗传算法的作业车间调度算法摘要作业车间调度问题具有建模复杂、计算复杂、动态多约束、多目标等特点。近年来，各种进化计算方法逐渐被引入到生产调度中，尤其是遗传算法的应用。本文主要介绍遗传算法在企业车间调度问题中的实现。遗传算法由Matlab编程实现。仿真结果验证了遗传算法求解作业车间调度问题的可行性和有效性。关键词遗传算法车间调度Matlab基于遗传算法的

2、流水车间调度摘要：流水车间调度问题具有建模复杂、计算复杂、动态多约束和多目标的特点。近年来各种进化计算方法，特别是遗传算法的应用已经逐渐引入到生产调度问题中。本文提出了一种用遗传算法设计流水车间的方法。利用Matlab编制了遗传算法设计程序，实验仿真结果表明了遗传算法求解流水车间调度问题的可行性和有效性。关键词：遗传算法流水车间调度Matlab介绍生产调度在企业生产过程中起着重要的作用。有效的调度方法和优化技术是实现先进制造、提高生产效率的基础和关键。研究和解决调度问题可以大大提高企业的生产效率，从而提高这些企业的竞争力。自从1954年约翰逊发表了关于流水车间调度问题的第一篇文章以来，流水车间

3、调度问题引起了许多学者的关注，并提出了许多解决方案。其中，以遗传算法、模拟退火、禁忌搜索和人工神经网络为代表的智能优化技术在解决流水车间调度问题方面发展迅速，引起了广泛关注。遗传算法因其优异的计算性能和显著的应用效果而特别引人注目。许多启发式混合方法就是在此基础上发展起来的。本文采用遗传算法来解决这个问题。1车间调度问题描述车间调度是指根据产品制造的合理需求，对加工车间序列进行分配，从而达到合理利用产品制造资源，提高企业经济效益的目的。数学上，车间调度问题可以描述为在M台机器上处理N个零件。作业车间调度的数学模型如下：(1)机组，即第j台机器，j=1，2，m。(2)表示第I部分的部分集，I=1

4、，2，n .(3)操作顺序集，表示零件加工操作顺序。(4)可选机组，表示零件加工过程中可以选择的加工机器(5)机器加工零件的时间矩阵T表示第一个零件在第J个机器上的加工时间。(6)机器加工零件的成本矩阵C表示第一个零件的第J台机器的加工成本。此外，需要满足的条件包括：每台机器在每个零件的每个工序中使用不超过一次，并且每个零件都按照一定的顺序进行加工。基于遗传算法的作业车间调度算法模型的建立基于多层编码遗传算法的车间调度算法流程如下图所示。种群初始化模块初始化种群构成问题的初始解集，适应值计算模块计算染色体的适应值，选择操作使用轮盘赌选择优秀个体；交叉操作使用整数交叉方法获得优秀个体，变异操作使

5、用证书变异方法获得优秀个体。算法流程图三模型算法的实现3.1个人代码染色体编码方法是证书编码。每条染色体代表所有工件的加工顺序。当待加工工件的总数为N，且工件的加工程序为总数时，个体表示为长度的整数串。染色体的前半部分代表机器上所有工件的加工顺序，后半部分代表工件每个工序的加工机号。比如个人2 4 3 1 1 2 3 4 1 3 2 3 2 1 3 2 1 3个人在3台机器上用4个加工程序两次表达了工件的加工顺序。其中，前8位表示工件的加工顺序，即工件2工件4工件3工件1工件1工件2工件3工件4；位9至16代表加工机器，依次为机器2机器1机器3机器3机器2机器2机器1机器3。3.2健身价值染色

6、体的适应值是所有工件的完成时间，适应值的计算公式为：其中时间是指所有任务的完成时间，所有工件的完成时间越短，染色体越好。3.3选择操作选择操作使用轮盘来选择适应度较好的染色体，个体选择概率为：；其中，指出了在每次选择中选择染色体1的概率。3.4交叉操作种群通过交叉操作获得新的染色体，从而推动整个种群向前进化。交叉操作采用整数交叉方法。交叉操作首先从种群中随机选择两条染色体，取出每条染色体的前端位置，然后随机选择交叉位置进行交叉。操作方法如下：交叉位置为5，只交叉个人的前方位置。个人-112 3 2 2 3交叉极值-221 211 1 221 211 1交叉后，一些工件具有冗余工序(例如，单个工

7、件中的工件2)，一些工件具有缺失工序(例如，单个工件中的工件1)。因此，工件工序的冗余操作变为缺少工件工序的操作，交叉前根据个人的操作机调整单独位置的加工机，如下图所示：交叉个体后-调整3.5突变操作种群通过变异操作获得新的个体，从而推动整个种群向前进化。变异算子首先从种群中随机选择变异个体，然后选择变异位置pos1和pos2，最后将pos1和pos2的处理过程与个体中对应的处理机序列号交换，如下图所示，交叉位置为2和4。个人-交叉个人-4Matlab程序实现及仿真结果多层编码遗传算法用于求解作业车间调度问题。有6个工件，在10台机器上加工。每个工件必须经过6道工序。可为每个程序选择机器序列号

8、，如下表所示。操作可选机台工件工件1工件2工件3工件4工件5工件6流程13，1023，9452程序2134，71，92，74，7程序325，86，83，73，106，9步骤44，76，712，86，91步骤56，812，10515，8程序654，10564，83每个过程的处理时间如下表所示。过程进度表工件工件1工件2工件3工件4工件5工件6流程13，561，4762程序21085，74，310，124，7程序391，45，64，67，96，9步骤45，45，653，58，81步骤53，339，11155，8程序6103，3134，73根据多层编码遗传算法的原理，在Matlab中编程实现了基于多

9、层编码遗传算法的车间调度算法。首先初始化个体，然后通过选择、交叉和变异操作搜索最优个体，得到最优车间调度方法。主要代码如下：PnNumber MnNumber=大小(Jm)；% n工件数量，操作数量trace=，MAXGEN)；%优化结果的初始值WnNumber=pNumber * mNumber；总操作百分比数字=零(1，PnNumber)；对于I=1: p数字数字(I)=MnNumber；目标Chrom=zeros，2 * wnNumber)；对于j=1:NINDWPNumberTemp=数字；对于i=1:WNumberval=unid rnd(PnNumber)；而WPNumberTem

10、p(val)=0val=unid rnd(PnNumber)；目标Chrom(j，I)=val；WPnumberTemp(val)=WPnumberTemp(val)-1；TemPVal ObjV P S=cal(Chrom，JmNumber，T，Jm)；%计算目标函数值而gentrace (1，gen)%记录了最小的操作Val1=PVal。val 2=P；MinVal=trace(1，gen)；STemp=S；目标目标PVal=Val1P=Val2S=STemp。图(1) %描述了解决方案的变化绘图(轨迹(1，)；坚持住。图(迹线(2，)，-。)；网格；图例(溶液的变化，人口平均值的变化)；图(2)；%显示最佳解决方案MP=S(1，数字*数字1:数字*数字* 2)；对于i=1:WNumberval=P(1，I)；a=(mod(val，100)；b=(val-a)/100)；Temp=Jmb，a。多行文字=温度(MP(1，I)；x1=PVal(1，I)；x2=PVal(2，I)；y1=MText-1；y2=多行文字；PlotRec(x1，x2，MText)；PloTrac(PvAl(1，I)，PVal(2，I)，MText)；坚持住。填充(x1，x2，x2，x1，y1，y1，y2，y2，1-1/b，1/