基于遗传算法的车间调度算法VIP免费

得分：_______南京大学研究生课程论文2011～2012学年第一学期二○一一年十二月基于遗传算法的车间调度算法【摘要】车间调度问题具有建模复杂性、计算复杂性、动态多约束、多目标性等特点。近几年，各种演化计算方法逐渐被引入到生产调度中，特别是遗传算法的应用。本文主要介绍了企业车间调度问题的遗传算法实现，通过Matlab实现对遗传算法的编程，其仿真调度结果验证了遗传算法用于求解车间调度问题的可行性和有效性。【关键词】遗传算法车间调度Matlab课程号：73327课程名称：Matlab语言论文题目：基于遗传算法的车间调度算法学科专业：交通运输工程学号：8113102姓名：李三立任课教师：王雄Flow-ShopschedulingbasedongeneticalgorithmAbstract：TheFlow-Shopschedulingproblemhasthepropertyofmodelingcomplexity,computationalcomplexity,dynamicmulti-constraintandmulti-targeted.Inrecentyearsavarietyofevolutionarycomputationmethods,inparticular,theapplicationofgeneticalgorithmshasbeengraduallyintroducedintotheproductionschedulingproblem.ThispaperputsforwardamethodtodesignFlow-Shopbyusinggeneticalgorithm.ProgramaboutgeneticalgorithmdesignsbyusingMatlab,SimulationresultsofourexperimentshowthefeasibilityandeffectivenessofgeneticalgorithmforsolvingFlow-Shopscheduling.Keywords：GeneticalgorithmFlow-ShopschedulingMatlab引言生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。研究和解决好调度问题，能极大提高企业的生产效率，从而提高这些企业的竞争力。自从1954年Johnson发表第一篇关于流水车间调度问题的文章以来，流水车间调度问题引起了许多学者的关注，提出了许多解决的方法。其中，以遗传算法、模拟退火、禁忌搜索以及人工神经网络为代表的智能化优化技术迅速发展，用来解决流水车间调度问题，受到人们的普遍关注。遗传算法以其优良的计算性能和显著的应用效果而特别引人注目，很多启发式混合方法都是在此基础上发展起来的。本文采用遗传算法进行求解。1车间调度问题描述车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源，提高企业经济效益的目的。车间调度问题从数学上可以描述为有n个代加工的零件在m台机器上加工，车间调度的数学模型如下：（1）机器集，表示第j台机器，j=1,2,…,m。（2）零件集，表示第i个零件，i=1,2,…,n。（3）工序序列集，表示零件加工工序序列。（4）可选机器集,表示零件加工工序j可以选择的加工机器。（5）使用机器加工零件的时间矩阵T，，表示第i个零件使用第j个机器的加工时间。（6）使用机器加工零件的费用矩阵C，，表示第i个零件使用第j个机器的加工费用。另外，问题需要满足的条件包括每个零件的各道工序使用每台机器不多于1次，每个零件加工都按照一定的顺序进行加工。2遗传算法的车间调度算法模型建立基于多层编码遗传算法的车间调度算法流程如下图所示。其中，种群初始化模块初始化种群构成问题的初始解集，适应度值计算模块计算染色体的适用度值，选择操作采用轮盘赌法选择优秀个体；交叉操作采用整数交叉法得到优秀个体，变异操作采用证书变异法得到优秀个体。种群初始化适应度值计算算法是否结束结束选择操作交叉操作变异操作YN算法流程图3模型算法的实现3.1个体编码染色体编码方式为证书编码，每个染色体表示全部工件的加工顺序，当待加工的工件总数为n，工件的加工工序共为时，则个体表示为长度为的整数串。其中，染色体的前半部分表示所有工件在机器上的加工顺序，后半部分表示工件每道工序的加工机器序号。如个体[2431123421332213]该个体表达了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指全部任务完成时...