制造执行系统第二章

1、制造执行系统制造执行系统主讲人：葛茂根主讲人：葛茂根合肥工业大学合肥工业大学2.1 零件加工任务的承接零件加工任务的承接2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程2.3 基于基于GA的生产排程的生产排程2.4 原材料与制造资源的准备原材料与制造资源的准备2、生产准备、生产准备制造执行系统制造执行系统 粗生产计划：粗生产计划：是指企业对计划期应达到的产品品种、质量、产量和产值等生产任务的初步计划和对产品生产进度的初步安排。2.1 零件加工任务的承接零件加工任务的承接1.粗生产计划：形态粗生产计划：形态1 任务来源是制造任务来源是制造BOM或或ERP的粗生产计划的特点：的

2、粗生产计划的特点：车间的生产能力一般能够满足任务的需求，只需要提供具体的信息即可。 由于外协加工任务外协加工任务具有不确定性的特点，因此当前车间能否完场加工任务，不仅需要考虑车间物料需求，而且还需考虑车间的动态产能。2.1 零件加工任务的承接零件加工任务的承接2. 外协加工任务：形态外协加工任务：形态2 任务来源是外协加工任务的粗生产计划的特点：任务来源是外协加工任务的粗生产计划的特点： 车间的生产能力不一定能够满足任务的需求，需要先判断当前的动态产能。2.1 零件加工任务的承接零件加工任务的承接零件加工工艺规划零件加工工艺规划将零件的粗生产形态转化为指导生产过程的精细化后的加工任务，其中生产

3、排程、批量和批次的确定是工艺规划的重要环节。2.1 零件加工任务的承接零件加工任务的承接3.零件加工工艺规划零件加工工艺规划零件加工工艺规划需补充的生产准备与制造信息：零件加工工艺规划需补充的生产准备与制造信息： 产品种类、批量与交货期 生产时间与生产成本 车间资源类别 紧急情况（紧急任务、设备维护）2.1 零件加工任务的承接零件加工任务的承接生产排程的必要性：生产排程的必要性： 可以顺利应对短交货期 减少生产中的中间品的浪费库存 可以推迟供应时间 可以减少完成品后中间品的安全库存量 因此，可以改善现金流转，消减不良库存2.1 零件加工任务的承接零件加工任务的承接2.2 工序图式模型、甘特图与

4、生产排程工序图式模型、甘特图与生产排程2.3 基于基于GA的生产排程的生产排程2.4 原材料与制造资源的准备原材料与制造资源的准备2、生产准备、生产准备制造执行系统制造执行系统生产排程定义生产排程定义生产排程生产排程是在考虑能力和设备的前提下，在物料数量一定的情况下，安排各生产任务的生产顺序，优化生产顺序，优化选择生产设备，使得减少等待时间，平衡各机器和工人的生产负荷。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程1.生产排程的定义与作用生产排程的定义与作用生产排程作用生产排程作用生产排程生产排程是一个NP-hard问题。析取图（析取图（disjunctive graph

5、）模型是生产排程问题的一类重要的描述形式，Balas等较早将其运用与车间生产排程问题。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程2.工序图式模型工序图式模型N: 所有工序组成节点集；A:连接同一工件的邻接工序间的连接（有向）弧集；E:同一机床上不同加工工序的析取弧集。 数学表示数学表示 G=（N,A,E） 图形示例图形示例（3工件、3机器排程问题的析取图）甘特图（甘特图（Gantt Chart）由亨利甘特于1910年开发的，他通过条状图来显示项目、进度和其他时间相关的系统进展的内在关系随着事件进展的情况。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产

6、排程3.甘特图甘特图 生产排程甘特图实例生产排程甘特图实例特点：特点：甘特图可以直观的表明任务计划在什么时候进行，及实际进展与计划要求的对比。管理者由此可便利地弄清每一项任务（项目）还剩下哪些工作要做，并可评估工作进度。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程生产排程的输入输出信息生产排程的输入输出信息输入：输入：零件的工艺信息和零件的批次划分范围；输出：输出：为车间提供可执行的静态排程甘特图；方法：方法：设计合适的优化算法，进行优化求解；2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程4.生产排程的数学建模生产排程的数学建模 解决问题的步骤：解

7、决问题的步骤：建模目的：建模目的：为车间提供一份详细的零件作业计划，合理的利用制造资源，高效率低成本的按时完成生产任务。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程优化目标：优化目标：基于各加工设备的最短完成时间和总加工成本最小为目标；约束条件：约束条件：l 同一机床上某一时刻，只能加工某种零件的某批次工序，一个批次加工完才可加工另一个批次；l 某种零件的某批次工序在某一时刻，只能在一台设备上加工；l 某种工件的某批次加工完后一起运送到下一个工序所要用的机床上；l 某种零件的某批次在上道工序完成后方可进入下一道工序加工；l 零件每道工序开始后除非设备故障否则不可中断；l

8、 考虑了设备开始加工时的准备时间。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程5.基于数学规划方法生产排程模型的解算基于数学规划方法生产排程模型的解算 生产排程求解方法：生产排程求解方法：2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程问题的求解方法：问题的求解方法：通过线性规划或者最优化迭代的方法求出函数Z最大或者最小值时变量xi的值即完成问题的求解。 混合整数规划：混合整数规划： 数学规则中求解生产排程问题的最常见方法是混合整数规划，其中一般形式：部分或者全部为整数2.2 工序图

9、式模型、甘特图与生产排程工序图式模型、甘特图与生产排程6.基于计算智能方法生产排程模型的解算基于计算智能方法生产排程模型的解算小结：小结：数学规划求解生产排程问题的对于单目标的问题求解具有一定的可行性，但是对于多目标问题数学规划的方法就行不通了，因此，实际应用中我们常用计算智能的方式来解决排程问题。计算智能方法：计算智能方法：求解生产排程模型问题即是使用计算智能的方法对已经建立好的数学模型进行求解，其求解思路简单，求解速度也较快。 计算智能方法求解生产排程模型问题的基本流程：计算智能方法求解生产排程模型问题的基本流程：2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程7.关于

10、面向月关于面向月/周周/日日/时的生产排程的分割时的生产排程的分割生产排程的分割生产排程的分割是把企业全年的生产任务具体的分配到各车间、工段、班组以致每个工作地和工人，规定他们在月、旬、周、日以至轮班和小时内的具体生产任务，从而保证按品种、质量、数量、期限和成本完成企业的生产任务。2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程批量：批量：相同产品或零件一次投入或出产的数量。生产间隔期：生产间隔期：相邻两批相同产品或零件投入或产出的时间间隔。批量=生产间隔期平均每日产量小结：小结：生产排程的分割是为了合理的组织企业生产活动，而在生产产品或零件的数量和期限方面规定了一定的数据

11、，从而确定车间合理的生产节拍。2.1 零件加工任务的承接零件加工任务的承接2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程2.3 基于基于GA的生产排程的生产排程2.4 原材料与制造资源的准备原材料与制造资源的准备2、生产准备、生产准备制造执行系统制造执行系统2.3 基于基于GA的生产排程的生产排程遗传算法的定义：遗传算法的定义：遗传算法（遗传算法（Genetic Algorithm , GA）,也称作基因算法，是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机搜索方法。1.遗传算法的定义、作用与特点遗传算法的定义、作用与特点应用：应用：2.3 基于基于

12、GA的生产排程的生产排程特点：特点：u从问题解的集中开始搜索，而不是从单个解开始u遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序u遗传算法有极强的容错能力u遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则2.3 基于基于GA的生产排程的生产排程遗传算法的核心要素：遗传算法的核心要素：2.遗传算法的核心要素遗传算法的核心要素染色体编码：染色体编码： 染色体编码染色体编码是把遗传算法不能直接处理的问题空间的参数转换成遗传空间的由基因按一定结构组成的染色体或个体的操作。2.3 基于基于GA的生产排程的生产排程染色体编码需要满足以下三个规范：染色体编码需要满足以下三个规范：

13、完备性：问题空间中的所有点（候选解）都能作为GA空间中的点（染色体）表现。 健全性：GA空间中的染色体能对应所有问题空间中的候选解。 非冗余性：染色体和候选解一一对应。染色体编码染色体编码目前的几种编码方法有二进制编码，浮点数编码，字符编码，整数编码等。2.3 基于基于GA的生产排程的生产排程选择操作：选择操作： 选择操作选择操作是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体，个体选择的依据是其适应度值。2.3 基于基于GA的生产排程的生产排程Tips：选择操作即是在模仿自然界生物进化中的优胜劣汰。操作说明：操作说明：个体适应按比例转化为选中概率，将轮盘分为10个扇区，因为要进行1

14、0次选择，所以产生10个0,1之间的随机数，相当于10次轮盘停止时时针的位置，指针停止在某一个扇区，该扇区代表的个体即被选中。2.3 基于基于GA的生产排程的生产排程交叉操作：交叉操作： 交叉操作交叉操作是指结合来自父代交配种群的信息产生新的个体。 Tips：交叉操作的目的是为了得到含有父代遗传基因的新的基因种群，在算法上看，交叉操作使得算法获得全局搜索的能力。2.3 基于基于GA的生产排程的生产排程变异操作：变异操作： 变异操作变异操作是一种局部随机搜索，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力；同时使得遗传算法保持种群多样性，以防止出现非成熟收敛。 实值变异实值变异 变异步

15、长的选择比较困难，建议采用如下的变异算子： 式中，,a(i)以概率1/m取值1，以1-1/m取值0，通常m=20；L为变量的取值范围；X为变异前的变量取值；x为变异后取值2.3 基于基于GA的生产排程的生产排程 二进制变异二进制变异 对于二进制编码个体而言，变异意味着变量的翻转。如下所示，有11位变量的个体，第4位发生了翻转：变异前：变异前： 01110011010变异后：变异后： 01100011010 除了上述基本位变异以外，还有其他的变异方法，如换位、复制、插入、删除等 Tips：变异操作是模仿生物进化中的基因突变，在算法中比例较少，但作用很大，防止算法提前收敛，陷入局部最优。2.3 基

16、于基于GA的生产排程的生产排程适应度函数适应度函数 也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。一般而言，适应度函数是由目标函数转换而来的。适应度函数的设计主要满足以下条件： 单值、连续、非负、最大化 合理、一致性 计算量小 通用性强 终止条件：终止条件： 常见的遗传算法的终止条件有：常见的遗传算法的终止条件有： 种群中个体的最大适应度超过预先设定值 种群中个体的平均适应度超过预先设定值 遗传优化世代数超过预先设定值2.3 基于基于GA的生产排程的生产排程遗传算法流程：遗传算法流程：3.遗传算法构造与流程框图遗传算法构造与流程框图2.3 基于基

17、于GA的生产排程的生产排程生产排程问题描述生产排程问题描述假设有某生产排程问题：某车间有M台机床，现有n个加工任务，每个加工任务有J道工序，如何排程能使总加工时间最短？4.生产排程问题的生产排程问题的GA描述描述 制造任务定义制造任务定义 （“i”，“j”，“f”，“st”，“pt”）字符“i”表示加工任务编号，“j”表示加工任务“i”的工序编号，“f”表示关联工序“j”的加工设备编号，“st”表示工序“j”在加工设备“f”上的开始加工时间，“pt”则表示工序“j”在加工设备“f”上的加工时间。2.3 基于基于GA的生产排程的生产排程 加工设备定义加工设备定义 （ “f”， “e”）字符“f”

18、表示加工设备编号，“e”表示该加工设备隶属的制造车间编号。 任务在设备间的运输时间定义任务在设备间的运输时间定义 （ “f”，“f”，“tt”）字符“f”, “f”表示加工设备的编号，“tt”表示任务在两设备之间的运输时间。2.3 基于基于GA的生产排程的生产排程 优化模型建立优化模型建立调度约束调度约束调度目标函数调度目标函数左式的工程含义是：选取所有制造任务的完工时间的最大值，对该值做最小化操作，作为最终调度结果值。2.3 基于基于GA的生产排程的生产排程l 资源约束：资源约束：表示在同一时间两道不同工序不能在同一设备上加工2.3 基于基于GA的生产排程的生产排程 染色体编码染色体编码2.

19、3 基于基于GA的生产排程的生产排程 适应度函数构造适应度函数构造以最小化调度时间为目标，设计如下适应度函数：选择：选择：对于选择算子，本算法采用轮盘赌方法。而根据适应度函数可得出，适应度值越小的个体，其生存空间越大。因此，为适应轮盘赌方法的选择概率计算方法，将适应度函数做如下变换：Fitness=1/Fitness指每个染色体的调度结果中最后一道工序的完工的最大时间。 遗传操作设计遗传操作设计2.3 基于基于GA的生产排程的生产排程交叉：交叉：对于选择算子，本算法采用两点交叉方案，其交叉逻辑如下图：变异：变异：由于被选择的待变基因对应于某一具体制造任务的具体某道工序的加工设备，因此，在变异时

20、，算法控制其只能在该工序所对应的的可选加工设备集中进行选择变异。基于该变异方法，可提高算法的收敛速度。2.3 基于基于GA的生产排程的生产排程 求解终止条件求解终止条件 解码操作是将遗传算法的优化结果转化为最终的调度结果。影响调度结果的关键因素之一是调度规则的设计，不同的调度规则将导致不同的调度结果。l 连续几代个体的最佳适应度之差小于设定的阀值： 解码操作解码操作l 迭代循环代数超过设定的代数调度规则分类调度规则分类2.3 基于基于GA的生产排程的生产排程5.案例分析案例分析假定有6个制造任务需在某制造车间加工，每个制造任务由6道工序构成，同时该车间包含6台机床，以最小化完成时间为调度目标。

21、 初始条件与参数初始条件与参数2.3 基于基于GA的生产排程的生产排程2.3 基于基于GA的生产排程的生产排程 结果分析结果分析算法在第866代时收敛，右图为调度甘特图2.3 基于基于GA的生产排程的生产排程 同算法不同求解规模同算法不同求解规模5. GA的求解性能分析的求解性能分析2.3 基于基于GA的生产排程的生产排程 同规模不同算法同规模不同算法2.1 零件加工任务的承接零件加工任务的承接2.2 工序图式模型、甘特图与生产排程工序图式模型、甘特图与生产排程2.3 基于基于GA的生产排程的生产排程2.4 原材料与制造资源的准备原材料与制造资源的准备2、生产准备、生产准备制造执行系统制造执行系统2.4 原材料与制造资源的准备原材料与制造资源的准备 制造资源的定义：制造资源的定义：1. 制造资源的定义与分类制造资源的定义与分类 制造资源制造资源是指完成产品整个生命周期的所有生产活动的软、硬件元素，包括了设计、制造、维护等相关活动过