改进遗传算法的车间调度优化的应用研究
目录
第一章绪论 (1)
1.1论文研究的背景 (1)
1.2车间调度研究的意义 (4)
1.3车间调度问题国内外研究现状 (5)
1.3.1生产调度建模研究现状 (5)
1.3.2生产调度方法研究现状 (6)
1.3.3生产调度软件系统和软件包研究现状 (7)
1.4论文的框架及技术路线 (7)
1.5本章小结 (8)
第二章混合流水线生产调度的原理与方法 (9)
2.1生产调度的概述 (9)
2.1.1生产调度 (9)
2.1.2生产调度问题分类 (10)
2.1.3生产调度问题特点 (10)
2.2生产调度方法及原理 (11)
2.3混合型流水线调度的特征及典型算法 (14)
2.3.1混合型流水线调度的特征 (14)
2.3.2混合流水线调度的分类 (15)
2.3.3混合型流水线调度的典型算法 (15)
2.4本章小结 (17)
第三章混合流水线调度问题的改进遗传算法研究 (18)
3.1混合流水线调度问题的描述 (18)
3.2改进遗传算法研究 (20)
3.3遗传算法的参数选取 (24)
3.4改进遗传算法求解混合流水线调度 (27)
3.4.1混合流水线调度问题模型 (27)
3.4.2遗传算法在MA TLAB中的实现 (27)
3.5改进遗传算法求解混合流水线调度的思路框架 (30)
III
3.6本章小结 (31)
第四章遗传算法在夏弗纳上海车间调度中的应用 (32)
4.1夏弗纳上海车间调度现状 (32)
4.1.1研究对象确立 (32)
4.1.2计划模式及存在的调度问题 (34)
4.2改进遗传算法应用于夏弗纳上海车间调度 (35)
4.2.1夏弗纳上海车间调度问题建模 (35)
4.2.2改进遗传算法参数的确定 (37)
4.2.3改进遗传算法求解车间调度 (38)
4.2.4调度结果的验证 (39)
4.2.5设备使用率的讨论与分析 (45)
4.3本章小结 (47)
第五章总结与展望 (48)
5.1结论 (48)
5.2展望 (49)
参考文献 (50)
附录改进遗传算法程序源代码 (53)
致谢 (62)
攻读学位期间发表的学术论文 (63)
IV
第一章绪论
1.1论文研究的背景
改革开放30多年来，中国经济的飞速发展创造了世界经济发展史上的一个奇迹。作为中国经济增长的引擎中国制造业却在近年来碰到了诸多挑战。随着“刘易斯”拐点的逐渐临近，劳动力成本不断攀升给制造企业带来了巨大压力。以上海市最低工资为例，从2010年的1120元提高到了2013年的1620元，增幅达到44%之多。近十几年来房地产行业的快速发展造成土地资源价格居高不下，极大的提高了制造企业的固定成本（厂房租赁、建设）。原材料价格的不断上涨和人民币升值的不可逆转趋势又对企业利润水平的产生了长期挤压的效应。2011年阿里巴巴对588家制造企业进行了调查，原材料占比从2009年的63.1%升至2010年的64%，人工成本的升幅更为明显，从11.1%逐年上升至12.3%[1]。
同时伴随着经济全球化的不断深入开展以及信息网络技术的不断普及和应用，制造业正面临个性化、多样化、小批量需求和标准品大量需求并存的局面，这又要求制造企业要向专业化、柔性化生产相统一，制造质量更高，制造成本更低，市场响应速度更快，应变能力更强方向发展。
如何充分发挥自身优势、苦练内功，通过技术创新和合理配置与优化利用有限的资源；如何从粗放型经营（增加生产要素量来扩大生产规模以实现经营目标增长）向集约型经营（通过有效生产要素的质量和利用效率的提高来实现经营目标济增长）升级，成为了摆在企业经营者面前的一道难题。作为实业经营的重要组成部分生产制造成为了企业运营改善的重要方向之一，企业与企业之间的竞争最终体现在产品和服务上，生产运营是企业核心竞争力的一个重要方面，生产运营的改善直接影响着企业的绩效。
调度系统是制造系统生产管理的核心，生产任务的顺利实施与完成，有限资源的合理调配与使用都取决于调度的决策水平[2]。近年来在生产管理技术和信息系统的不断发展，ERP，MRP系统的不断普及帮助制造企业极大的提高生产经营效率。实际工作中发现这些系统更多的关注在企业生产计划的编制，对车间层面的控制能
1
基于遗传算法的车间调度算法
得分：_______ 南京林业大学 研究生课程论文 2011～2012学年第一学期 课程号：73327 课程名称：Matlab语言 论文题目：基于遗传算法的车间调度算法 学科专业：交通运输工程 学号：8113102 姓名：闫盖 任课教师：王一雄 二○一一年十二月
基于遗传算法的车间调度算法 【摘要】车间调度问题具有建模复杂性、计算复杂性、动态多约束、多目标性等特点。近几年，各种演化计算方法逐渐被引入到生产调度中，特别是遗传算法的应用。本文主要介绍了企业车间调度问题的遗传算法实现，通过Matlab 实现对遗传算法的编程，其仿真调度结果验证了遗传算法用于求解车间调度问题的可行性和有效性。 【关键词】遗传算法 车间调度 Matlab Flow-Shop scheduling based on genetic algorithm Abstract ：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 genetic 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 genetic algorithm for solving Flow-Shop scheduling. Key words ：Genetic algorithm Flow-Shop scheduling Matlab 引言 生产调度对企业的生产作业过程具有重要的作用。有效的调度方法和优化技术是实现先进制造和提高生产效益的基础和关键。研究和解决好调度问题，能极大提高企业的生产效率，从而提高这些企业的竞争力。自从1954年Johnson 发表第一篇关于流水车间调度问题的文章以来，流水车间调度问题引起了许多学者的关注，提出了许多解决的方法。其中，以遗传算法、模拟退火、禁忌搜索以及人工神经网络为代表的智能化优化技术迅速发展，用来解决流水车间调度问题，受到人们的普遍关注。遗传算法以其优良的计算性能和显著的应用效果而特别引人注目，很多启发式混合方法都是在此基础上发展起来的。本文采用遗传算法进行求解。 1车间调度问题描述 车间调度是指根据产品制造的合理需求分配加工车间顺序，从而达到合理利用产品制造资源，提高企业经济效益的目的。车间调度问题从数学上可以描述为有n 个代加工的零件在m 台机器上加工，车间调度的数学模型如下： （1） 机器集},,{21m m m m M ，?=，j m 表示第j 台机器，j=1,2,…,m 。 （2） 零件集},,{21n p p p P ，?=，i p 表示第i 个零件，i=1,2,…,n 。 （3） 工序序列集},,{21n op op op OP ，?=，},,{21ik i i i op op op op ，?=表示零件i p 加工工序序列。 （4） 可选机器集},,{21ik i i op op op OPM ，?=,},,{21ijk ij ij ij op op op op ，?=表示零件 i p 加工工序j 可以选择的加工机器。
流水线车间生产调度的遗传算法MATLAB源代码
流水线车间生产调度的遗传算法MATLAB源代码 n个任务在流水线上进行m个阶段的加工，每一阶段至少有一台机器且至少有一个阶段存在多台机器，并且同一阶段上各机器的处理性能相同，在每一阶段各任务均要完成一道工序，各任务的每道工序可以在相应阶段上的任意一台机器上加工，已知任务各道工序的处理时间，要求确定所有任务的排序以及每一阶段上机器的分配情况，使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵，存储m个工件n个工序的加工时间 % P 1×n的向量，n个工序中，每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中，各工件各工序的开始时刻，可根据它绘出甘特图 % Y2p 最优方案中，各工件各工序的结束时刻，可根据它绘出甘特图 % Y3p 最优方案中，各工件各工序使用的机器编号 % Xp 最优决策变量的值，决策变量是一个实数编码的m×n矩阵 % LC1 收敛曲线1，各代最优个体适应值的记录 % LC2 收敛曲线2，各代群体平均适应值的记录 % 最后，程序还将绘出三副图片：两条收敛曲线图和甘特图（各工件的调度时序图） %第一步：变量初始化 [m,n]=size(T);%m是总工件数，n是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步：随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N X=zeros(m,n); for j=1:n for i=1:m X(i,j)=1+(P(j)-eps)*rand; end end
基于遗传算法的流水车间调度问题
中文摘要 流水车间调度问题是研究多个工件在若干个机器上的加工次序的问题，有效的调度算法对企业提高生产效率有着重要作用。本文使用遗传算法求解流水车间调度问题，把一个染色体编码成若干个自然数，表示相应工件的排序权值；通过简单交换两个父代的若干相同位置的基因，产生能够继承父代优良特性的子代；并且采用均匀变异，更好地保持种群中的基因的多样性。实验表明，该方法能取得较好的效果。 关键字：遗传算法，流水车间调度方法，实数编码，基因链码，群体，适应度。
外文摘要 Abstract: Flow-shop scheduling problem study the problem the processing sequence of A plurality of workpieces on some working machine,and it makes good effects on proving production efficiency to the industries with effective methods.In the case,we deal with flow-shop scheduling problem using a algorithm,the Genetic Algorithm.There is a chromosome we've just coded into some natural numbers to represent the weight order of these workpieces; exchanging simply two fathers' places of some gene to produce new children that carried good feature on two fathers;we also use the Uniform Mutation,and it keeps its diversity of gene on the population.This experiment show this method can achieve good results. Key Words: Genetic Algorithm, Flow-shop scheduling problem，natural number coding，genic bar code,group，fitness.
遗传算法在作业车间调度问题中的应用——先进制造管理作业
先进制造管理 报告 遗传算法在作业车间调度问题中的应用 专业：管理科学与工程 时间：2015年1月
遗传算法在作业车间调度问题中的应用 1作业车间调度问题 所谓生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹方法、优化技术、自动化与计算机技术发展的核心，有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。 作业车间调度（job-shop）问题可以表述为：设有N个工件在M台机器上加工，根据工件加工工艺的要求，每个工件使用机器的顺序及其每道工序所花时间已给定，调度问题的目标就是如何选择加工顺序使得总的加工时间最短最优。 前提假设： 1. 每一台机器每次只能加工一个工件，每一个工件在机器上的加工被成为一道工序。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序数不大于设备数； 4. 每道工序必须在指定的某种设备上加工； 5. 任何作业没有抢先加工的优先权； 6. 在作业优化过程中既没有新的工件加入也没有取消的工件； 车间作业是指利用车间资源(如机床、刀具、夹具等)完成的某项任务。在实际生产中，这项任务可能是装配一种产品，也可能是完成一批工件的加工。而在本文中，为了研究方便，我们将这项任务限定为加工一批工件。在此基础上，可对车间作业调度问题进行一般性的描述:假定有多个工件，要经过多台机器加工。一个工件在一台机器上的加工程序称为一道“工序”，相应的加工时间称为该工序的“加工时间”。用事先给定的“加工路线”表示工件加工时技术上的约束，即工件的加工工艺过程。用“加工顺序”表示各台机器上各个工件加工的先后顺序。车间作业调度问题中，每个工件都有独特的加工路线。它所要解决的问题就是确定每台机器上不同工件的加工顺序，以及每个工件的所有工序的起始加工时间，以最优化某个性能指标。然而，车间调度是一个 NP-Hard 问题，运用穷举法又会大大增加计算量，所以考虑利用遗传算法求解。
02流水线车间生产调度的遗传算法MATLAB源代码
流水线车间生产调度的遗传算法MATLAB源代码n个任务在流水线上进行m个阶段的加工,每一阶段至少有一台机器且至少有一个阶段存在多台机器,并且同一阶段上各机器的处理性能相同,在每一阶段各任务均要完成一道工序,各任务的每道工序可以在相应阶段上的任意一台机器上加工,已知任务各道工序的处理时间,要求确定所有任务的排序以及每一阶段上机器的分配情况,使得调度指标(一般求Makespan)最小。 function [Zp,Y1p,Y2p,Y3p,Xp,LC1,LC2]=JSPGA(M,N,Pm,T,P) %-------------------------------------------------------------------------- % JSPGA、m % 流水线型车间作业调度遗传算法 % GreenSim团队——专业级算法设计&代写程序 % 欢迎访问GreenSim团队主页→ %-------------------------------------------------------------------------- % 输入参数列表 % M 遗传进化迭代次数 % N 种群规模(取偶数) % Pm 变异概率 % T m×n的矩阵,存储m个工件n个工序的加工时间 % P 1×n的向量,n个工序中,每一个工序所具有的机床数目 % 输出参数列表 % Zp 最优的Makespan值 % Y1p 最优方案中,各工件各工序的开始时刻,可根据它绘出甘特图 % Y2p 最优方案中,各工件各工序的结束时刻,可根据它绘出甘特图 % Y3p 最优方案中,各工件各工序使用的机器编号 % Xp 最优决策变量的值,决策变量就是一个实数编码的m×n矩阵 % LC1 收敛曲线1,各代最优个体适应值的记录 % LC2 收敛曲线2,各代群体平均适应值的记录 % 最后,程序还将绘出三副图片:两条收敛曲线图与甘特图(各工件的调度时序图) %第一步:变量初始化 [m,n]=size(T);%m就是总工件数,n就是总工序数 Xp=zeros(m,n);%最优决策变量 LC1=zeros(1,M);%收敛曲线1 LC2=zeros(1,N);%收敛曲线2 %第二步:随机产生初始种群 farm=cell(1,N);%采用细胞结构存储种群 for k=1:N
遗传算法在生产调度方面的应用
遗传算法在生产调度方面的应用 合肥工业大学吴磊（20080313）陈超峰（20080321）方振中（20080322）周超（20080332）王伦良（20080340） 摘要：生产调度问题是企业生产甚至国际合作的关键问题，但生产调度问题难以精确求解。遗传算法可以很好的解决这一问题，在生产调度、生产规划、任务分配等方面发挥着极其重要的作用。 关键词：生产调度生产调度方式遗传算法 1.遗传算法 遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应全局优化概率的搜索算法。它使用群体搜索技术，通过对当前群体施加选择交叉变异等一系列遗传操作，从而产生新一代的群体，并按优胜劣汰的机制逐步使群体进化到包含或接近最优解的状态。 1.1遗传算法的基本运算过程 选择：从当前种群中选出优良的个体作为父代个体。 对各染色体v k计算适合度eval（v k）；k=1,2,3，…，m 计算选择概率： 对各染色体v k ， P=eval（v k）/∑eval(v k) 交叉：对群体中的个体进行两两随即配对 对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点 对每一对相互配对的个体，依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。 变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。 2.生产调度 生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。 在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。生产调度的重要意义在于：现代工业企业，生产环节多，协作关系复杂，生产连续性强，情