《基于遗传算法的车间调度算法.doc》由会员分享，可在线阅读，更多相关《基于遗传算法的车间调度算法.doc（8页珍藏版）》请在金锄头文库上搜索。
1、 得分：_南 京 大 学研究生课程论文20112012学年 第一学期课 程 号：73327 课程名称：Matlab语言论文题目：基于遗传算法的车间调度算法学科专业：交通运输工程学 号：姓 名：李三立任课教师：王雄 二一一年十二月基于遗传算法的车间调度算法【摘要】车间调度问题具有建模复杂性、计算复杂性、动态多约束、多目标性等特点。近几年，各种演化计算方法逐渐被引入到生产调度中，特别是遗传算法的应用。本文主要介绍了企业车间调度问题的遗传算法实现，通过Matlab实现对遗传算法的编程，其仿真调度结果验证了遗传算法用于求解车间调度问题的可行性和有效性。【关键词】遗传算法 车间调度 MatlabFlow
2、-Shop scheduling based on genetic algorithmAbstract：The Flow-Shop scheduling problem has the property of modeling complexity, computational complexity, dynamic multi-constraint and multi-targeted. In recent years a variety of evolutionary computation methods, in particular, the application of geneti
3、c algorithms has been gradually introduced into the production scheduling problem. This paper puts forward a method to design Flow-Shop by using genetic algorithm. Program about genetic algorithm designs by using Matlab, Simulation results of our experiment show the feasibility and effectiveness of
4、genetic algorithm for solving Flow-Shop scheduling.Key words：Genetic algorithm Flow-Shop scheduling Matlab引言生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。研究和解决好调度问题，能极大提高企业的生产效率，从而提高这些企业的竞争力。自从1954年Johnson发表第一篇关于流水车间调度问题的文章以来，流水车间调度问题引起了许多学者的关注，提出了许多解决的方法。其中，以遗传算法、模拟退火、禁忌搜索以及人工神经网络为代表的智能化优化
5、技术迅速发展，用来解决流水车间调度问题，受到人们的普遍关注。遗传算法以其优良的计算性能和显著的应用效果而特别引人注目，很多启发式混合方法都是在此基础上发展起来的。本文采用遗传算法进行求解。1车间调度问题描述车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源，提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个代加工的零件在m台机器上加工，车间调度的数学模型如下：（1） 机器集，表示第j台机器，j=1,2,m。（2） 零件集，表示第i个零件，i=1,2,n。（3） 工序序列集，表示零件加工工序序列。（4） 可选机器集,表示零件加工工序j可以选择的加工机器。（
6、5） 使用机器加工零件的时间矩阵T，表示第i个零件使用第j个机器的加工时间。（6） 使用机器加工零件的费用矩阵C，表示第i个零件使用第j个机器的加工费用。另外，问题需要满足的条件包括每个零件的各道工序使用每台机器不多于1次，每个零件加工都按照一定的顺序进行加工。2遗传算法的车间调度算法模型建立基于多层编码遗传算法的车间调度算法流程如下图所示。其中，种群初始化模块初始化种群构成问题的初始解集，适应度值计算模块计算染色体的适用度值，选择操作采用轮盘赌法选择优秀个体；交叉操作采用整数交叉法得到优秀个体，变异操作采用证书变异法得到优秀个体。算法流程图3模型算法的实现3.1个体编码染色体编码方式为证书编
7、码，每个染色体表示全部工件的加工顺序，当待加工的工件总数为n，工件的加工工序共为时，则个体表示为长度为的整数串。其中，染色体的前半部分表示所有工件在机器上的加工顺序，后半部分表示工件每道工序的加工机器序号。如个体2 4 3 1 1 2 3 4 2 1 3 3 2 2 1 3该个体表达了4个加工工序都是2次的工件在3台机器上的加工顺序。其中，前8位表示工件的加工顺序，为工件2工件4工件3工件1工件1工件2工件3工件4；9到16位表示加工机器，依次为机器2机器1机器3机器3机器2机器2机器1机器3。3.2适应度值染色体的适应度值为全部工件的完成时间，适应度值计算公式为：其中，time指全部任务完成
8、时间，全部工件完成时间越短，该染色体越好。3.3选择操作选择操作采用轮盘赌法选择适应度较好的染色体，个体选择概率为：；其中，表示染色体i在每次选择中被选中的概率。3.4交叉操作种群通过交叉操作获得新染色体，从而推动整个种群向前进化，交叉操作采用整数交叉法。交叉操作首先从种群中随机选取两个染色体，并取出每个染色体的前位，然后随机选择交叉位置进行交叉。操作方法如下：交叉位置为5，只对个体前位进行交叉。个体-112 3 2 2 3 交叉 极值-221 211 1 221 211 1交叉后某些工件的工序多余（如个体中的工件2），某些工件的工序缺失（如个体中的工件1），因此，把工件工序多余的操作变为工件
9、工序缺失的操作，并按交叉前个体的操作机器来调整个体位到位的加工机器，如下所示：交叉后个体- 调整 3.5变异操作种群通过变异操作获得新的个体，从而推动整个种群向前进化。变异算子首先从种群中随机选取变异个体，然后选择变异位置pos1和pos2，最后把个体中pos1和pos2位的加工工序以及对应的加工机器序号对换，如下列示，交叉位置为2和4。个体- 交叉 个体-4Matlab程序实现和仿真结果采用多层编码遗传算法求解车间调度问题，共有6个工件，在10台机器上加工，每个工件都要经过6道加工工序，每个工序可选择机器序号下表所示。工序可选机器表工件工件1工件2工件3工件4工件5工件6工序13，1023，
10、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中编程实现基于多层编码遗传算法的车间调度算法，首先进行个体初始化，然后采用选择、交叉和变异操作搜索最佳个
11、体，得到最优的车间调度方法，主要代码如下：PNumber MNumber=size(Jm); %PNumber 工件个数、MNumber工序个数trace=zeros(2, MAXGEN); %寻优结果的初始值WNumber=PNumber*MNumber; %工序总个数Number=zeros(1,PNumber); for i=1:PNumber Number(i)=MNumber; endChrom=zeros(NIND,2*WNumber);for j=1:NIND WPNumberTemp=Number; for i=1:WNumber val=unidrnd(PNumber); w
12、hile WPNumberTemp(val)=0 val=unidrnd(PNumber); end Chrom(j,i)= val; WPNumberTemp(val)=WPNumberTemp(val)-1; Temp=Jmval,MNumber-WPNumberTemp(val); SizeTemp=length(Temp); Chrom(j,i+WNumber)= unidrnd(SizeTemp); endend PVal ObjV P S=cal(Chrom,JmNumber,T,Jm); %计算目标函数值while genMAXGEN % 循环寻找 FitnV=ranking(O
13、bjV); %分配适应度值 SelCh=select(rws, Chrom, FitnV, GGAP); %选择操作 SelCh=across(SelCh,XOVR,Jm,T); %交叉操作 SelCh=aberranceJm(SelCh,MUTR,Jm,T); %变异操作PVal ObjVSel P S=cal(SelCh,JmNumber,T,Jm); %计算目标适应度值end Chrom ObjV =reins(Chrom, SelCh,1, 1, ObjV, ObjVSel); %重新插入新种群 gen=gen+1; trace(1, gen)=min(ObjV); %保存最优值 trace(2, gen)=mean(ObjV); if gen=1 % 记录最佳值 Val1=PVal; Val2=P; MinVal=min(ObjV); STemp=S;
