第十二章排序与统筹.ppt
《第十二章排序与统筹.ppt》由会员分享,可在线阅读,更多相关《第十二章排序与统筹.ppt(203页珍藏版)》请在三一文库上搜索。
1、第十一章 排序与统筹方法,第十一章 排序与统筹方法,11.1 车间作业计划模型,11.1 车间作业计划模型,车间作业计划 一个工厂生产工序的计划和安排。 能否在满足加工工艺流程前提下,通过各个零件在各台机床上加工次序上的合理安排, 使得完成这批零件加工任务所需总时间最少; 使得各加工零件在车间里停留的平均时间最短。,11.1 车间作业计划模型,一、一台机器、几个零件的排序问题,11.1 车间作业计划模型,例:某车间有一台磨床,现有六个零件都要求加工,按照什么样的加工顺序来加工这六个零件,才能使它们在车间停留的平均时间最少?,11.1 车间作业计划模型,不管按什么顺序加工这六个零件,都需要 8
2、小时。 由于各个零件加工时间不同,不同的加工顺序,使得这六个零件在车间里的平均停留时间是不一样的。,11.1 车间作业计划模型,按照某个加工顺序加工零件时,某个零件在车间的停留时间应该等于在它前面加工的各个零件的加工时间与这一零件本身的加工时间之和。,如果用 Pi 表示安排在第 i 位加工的零件所需的时间, 用 Tj 表示安排在第 j 位加工的零件总的停留时间, 则有,11.1 车间作业计划模型,这样可以计算出按照 1、2、3、4、5、6 顺序加工零件,各零件在车间的停留时间,如表所示 于是各零件平均停留时间为,11.1 车间作业计划模型,如果按照 3、2、4、5、6、1 顺序加工零件,也可以
3、计算出各零件在车间的停留时间,如表所示 于是各零件平均停留时间为,11.1 车间作业计划模型,不同加工顺序得到不同的各零件的平均停留时间, 求一个使得各零件的平均停留时间最少呢?,11.1 车间作业计划模型,对于某种加工顺序,安排在第 j 位加工的零件在车间里总的停留时间为Tj ,具体表示如下: 零件 1 : T1 = P1 零件 2 : T2 = P1 + P2 零件 3 : T3 = P1 + P2 + P3 零件 4 : T4 = P1 + P2 + P3 + P4 零件 5 : T5 = P1 + P2 + P3 + P4 + P5 零件 6 : T6 = P1 + P2 + P3 +
4、 P4 + P5 + P6,11.1 车间作业计划模型,六个零件的总停留时间为: T1+T2+T3+T4+T5+T6 =6P1+5P2+ 4P3+ 3P4+ 2P5+ P6; 各零件的平均停留时间为 由此可见,要使各个零件平均停留时间为最少,只要 6P1+5P2+ 4P3+ 3P4+ 2P5+ P6 的值为最小即可。,11.1 车间作业计划模型,要使6P1+5P2+ 4P3+ 3P4+ 2P5+ P6 的值为最小。 即将 P1, P2, P3, P4, P5, P6 从小到大排序,较小的数对应的零件先加工。,11.1 车间作业计划模型,结论: 对于一台机器 n 个零件的排序问题, 按照加工时间
5、从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。,11.1 车间作业计划模型,例:某车间有一台磨床,现有六个零件都要求加工,按照什么样的加工顺序来加工这六个零件,才能使它们在车间停留的平均时间最少?,从上述结论可知,按照3、4、5、6、1、2 顺序加工零件,可使各个零件的平均停留时间为最少。 各零件平均停留时间为,11.1 车间作业计划模型,习题,11.1 车间作业计划模型,11.1 车间作业计划模型,一、一台机器、几个零件的排序问题 二、两台机器,n 个零件,11.1 车间作业计划模型,例 某工厂要做一些零件,这些零件要求先在车床上车削,然后再在磨床上加工。 应该如何安排这五个
6、零件的先后加工顺序才能使完成这五个零件的总的加工时间为最少?,11.1 车间作业计划模型,解:由于每个零件必须先进行车床加工,再进行磨床加工,所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的。,11.1 车间作业计划模型,11.1 车间作业计划模型,1 2 3 4 5,1,车床,磨床,8:00 9:00 10:00 11:00 12:00 1:00 2:00 3:00 4:00 5:00 6:00,11.1 车间作业计划模型,1 2 3 4 5,1,2,车床,磨床,8:00 9:00 10:00 11:00 12:00 1:00 2:00 3:00 4:00 5:00 6:00,11
7、.1 车间作业计划模型,共需要10小时,11.1 车间作业计划模型,11.1 车间作业计划模型,11.1 车间作业计划模型,共需要9小时,11.1 车间作业计划模型,11.1 车间作业计划模型,可知加工时间的延长主要是由于磨床的停工待料, 车床上加工时间越短的零件,越早加工, 磨床上加工时间越短的零件,越晚加工,,11.1 车间作业计划模型,设 a1, a2,an; 和 b1, b2,bn 分别是零件 1,2,n 在机器 A 和 B 上的加工时间,则使得全部零件的总加工时间最短的排序算法为:,1). 找出加工时间 a1,a2,an,b1,b2,bn,中的最小数。 2). 若最小数为 ai,则将
8、零件 i 排在第一位加工,并从零件集合中去掉这个零件。 3). 若最小数为 bj,则将零件 j 排在最后一位加工,并从零件集合中去掉这个零件。 4). 对剩下的零件重复上述手续,直到零件集合为空集时停止。,11.1 车间作业计划模型,若最小数为 ai,则将零件 i 排在第一位加工; 若最小数为 bj,则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,若最小数为 ai,则将零件 i 排在第一位加工; 若最小数为 bj,则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,若最小数为 ai,则将零件 i 排在第一位加工; 若最小数为 bj,则将零件 j 排在最后一位加工。,11
9、.1 车间作业计划模型,若最小数为 ai,则将零件 i 排在第一位加工; 若最小数为 bj,则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,若最小数为 ai,则将零件 i 排在第一位加工; 若最小数为 bj,则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,若最小数为 ai,则将零件 i 排在第一位加工; 若最小数为 bj,则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,11.1 车间作业计划模型,共需要7小时,11.1 车间作业计划模型,以上介绍了求解一台机器 n 个零件和二台机器 n 个零件的排序问题的算法。 在一般的车间作业计划问题中,有 m 台机
10、器 n 个零件,一般找不到类似的有效的求解算法,但可以用求解整数规划的方法加以解决。,习题 p279, 2,11.1 车间作业计划模型,解:此题为两台机器,n 个零件模型, 这种模型加工思路为: 钻床上加工时间越短的零件越早加工, 磨床上加工时间越短的零件越晚加工。 根据以上思路, 则加工顺序为: 2 , 3 , 7 , 5 , 1 , 6 , 4 。 钻床的停工时间是:40.1。磨床的停工时间是:42.6。,第十一章 排序与统筹方法,11.1 车间作业计划模型 11.2 统筹方法,11.2 统筹方法,一、导言,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大
11、型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图,11.2 统筹方法,甘特图(Gantt Chart),1. 对各项活动进行计划调度与控制 2. 简单、醒目、便于编制 3. 横向表示时间,纵向表示活动 4. 各种图形符号,甘特图的例子,11.2 统筹方法,一、 基本概念,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图 3. 5060年代在美国取得成效,11.2 统筹方法,1956年,美国杜邦公司在制定企业不同业务部门的系统规划时,制定了第一套网络计划。 借助于网络表示各项
12、工作与所需要的时间,以及各项工作的相互关系。 通过网络分析研究工程费用与工期的相互关系。 找出在编制计划时及计划执行过程中的关键路线。 这种方法称为关键路线法(Critical Path Method)简称CPM。 杜邦公司将关键路径法应用于设备维修,使维修停工时间由125小时锐减为7小时。,11.2 统筹方法,1958年,美国海军武器部在制定“北极星”导弹计划时应用了网络分析方法与网络计划。 注重于对各项工作安排的评价和审查。 称为计划评审方法(Program Evaluation and Review Technique)简称为PERT。 在北极星导弹设计中,应用计划评审技术,将项目任务之
13、间的关系模型化,使设计完成时间缩短了2年。,11.2 统筹方法,关键路线法(CPM)主要应用在于以往类似工程中已取得一定经验的承包工程; 计划评审方法(PERT)更多地应用于研究与开发项目; 在这两种方法得到应用推广之后,又陆续出现了类似的最低成本和估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。 虽然方法很多,各自侧重的目标有所不同,应用的都是CPM和PERT的基本原理和基本方法。,11.2 统筹方法,一、 基本概念,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图
14、 3. 5060年代在美国取得成效 4. 62年前苏联列入国民经济计划中,11.2 统筹方法,在苏联,政府规定所有大的建筑工程都必须采用网络计划技术进行管理; 1961年,美国政府规定,凡是一切由政府进行的工程,都必须采用CPM技术,而在军方,若不编制项目网络计划就不会得到批准; 英国不仅将网络计划技术应用于建筑业,而且还广泛应用于工业,要求直接从事管理和有关业务的专业人员必须掌握此技术。,11.2 统筹方法,一、 基本概念,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图 3. 5060年代
15、在美国取得成效 4. 62年前苏联列入国民经济计划中 5. 1962年进入我国,11.2 统筹方法,20世纪60年代,华罗庚 教授引进和推广了网络计划技术,鉴于其具有“统筹兼顾、合理安排”的特点 ,将这一技术称为“统筹方法”。 并于1965年发表了统筹方法评论,为推广应用网络计划方法奠定了基础。,11.2 统筹方法,一、导言,国内外应用网络计划的实践表明,它具有一系列优点,特别适用于生产技术复杂,工作项目繁多、且联系紧密的一些跨部门的工作计划。 例如: 新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排,合理组织报表、文件流程等方面。,11.2
16、 统筹方法,一、导言 二、网络计划图,11.2 统筹方法,二、网络计划图,定义: 反映一个工程项目中各项作业(工序)的内在逻辑关系的一种有向图,称为统筹图,又称计划网络图,以符号G表示。 此中“内在逻辑关系”是指由于工程本身的工艺与组织性要求,而对各工序提出的在时间上和空间上所要求的先后处理关系。,11.2 统筹方法,例 某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其 工序进度表 如下表所示,请画出其统筹方法网络图。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序,工序泛指一切需要消耗人力、物质或时间的具体活动过程,用弧表示。 在弧的上面,标以各工
17、序的代号, 在弧的下面,标上完成此工序所需的时间(或资源)等数据 如图是由工序a、b、c、d、e、f、g,7道工序组成的网络图,工序旁边的数表示完成该工序需要的时间。,(1) 工序,紧前工序紧接在某工序之前的工序, (如图中的d、c是f的紧前工序) 紧后工序紧接在某工序之后的工序; (如图中的e、d均是a的紧后工序) 平行工序可以同时开始进行的各工序。 (如图中的e和d是平行工序),(1) 工序,虚工序,表示工时为零,不消耗如何资源的虚拟工序。其作用只是为了正确表示前后两个工序之间的逻辑关系。 一般用虚箭线表示:,(1) 工序,虚工序,表示工时为零,不消耗如何资源的虚拟工序。其作用只是为了正确
18、表示前后两个工序之间的逻辑关系。 一般用虚箭线表示:,(1) 工序,回路,虚工序,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序 (2) 事项,前后工序的交接点称为事项,常用“”加数字表示,数字主要起标号作用, 如图中标号从1至6,代表有6个事项,有时也可用来表示工序,如图的工序 e = 。 根据事项之间的相互关系,也可分为前置事项,后继事项、起(始)点事项和终点事项。,(2) 事项,前置事项指某一工序箭尾所连接的事项,它表示一个工序的开始,(如图中 和均是的前置事项,或分别是d、c两工序的前置事项) 后继事项指某一工序箭头所指的事项,它表示一个工序的结束。,(2) 事
19、项,始点事项整个网络图开始的事项,即没有箭头进入的事项,也称为网络始点,如图中的。 终点事项网络图的最后一个事项,即没有箭尾出去的事项,也称网络的终点。如图中的。 介于始点事项和终点事项之间的所有事项均称为中间事项,它们所代表的意义都是双重的:既表示前一项工序的结束,又表示后一项工序的开始。,(2) 事项,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序 (2) 事项 (3) 线路,线路(或路线) 指网络图中从始点到终点的一条道路(沿着箭头的方向),如图中共有三条线路。 aeg 即: adf 即: bcf 即:,(3) 线路,线路长指线路上各工序所延续的时间之和,三条线路
20、长分别是: 2+5+2=9,2+3+1=6,3+2+1=6。 其中最长的线路称为关键线路,它决定着整个计划任务的总工期。关键线路上的工序和事项分别被称为关键工序和关键事项。,(3) 线路,线路(或路线) 指网络图中从始点到终点的一条道路(沿着箭头的方向),如图中共有三条线路。 aeg 即: 9h adf 即: 6h bcf 即: 6h,(3) 线路,线路(或路线) 指网络图中从始点到终点的一条道路(沿着箭头的方向),如图中共有三条线路。 aeg 即: 9h adf 即: 6h bcf 即: 6h,(3) 线路,关键线路,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序 (
21、2) 事项 (3) 线路,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项,一个总终点事项,i,(1) 网络图只能有一个总始点事项,一个总终点事项,i,(1) 网络图只能有一个总始点事项,一个总终点事项 (如图中有两个终点事项和,就是错误的。) 一般在实际中应将没有紧前工序的所有事项合并起来,构成网络的始点事项,把没有紧后工序的所有事项合并起来,构成网络的终点事项。,(1) 网络图只能有一个总始点事项,一个总终点事项 (如图中有两个终点事项和,就是错误的。) 一般在实际中应将没有紧前工序的所有事项合并起来,构成网络的始点事项
22、,把没有紧后工序的所有事项合并起来,构成网络的终点事项。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项,一个总终点事项 (2) 网络图中不允许出现循环回路,(2) 网络图中不允许出现循环回路 在网络图中,如果从某个事项出发,顺某一线路能到原出发点,就称为循环回路。 例如图中的,就是一个循环回路。它表示的逻辑关系是错误的。会出现工程永远不能完成的现象。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项,一个总终点事项 (2) 网络图中不允许出现循环回路
23、(3) 任何两事项之间只能由一条弧连接,(3) 任何两事项之间只能由一条弧连接 否则,不利于分析、计算,甚至无法解决问题,相邻两点之间无论有多少工序,计算机都认为它们是同一个工序。若出现并行作业可引入虚工序.,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项,一个总终点事项 (2) 网络图中不允许出现循环回路 任何两事项之间只能由一条弧连接 (4) 尽量避免弧的交叉,尽量避免弧的交叉 在不改变逻辑关系的情况下合理安排工序间的相对位置,尽量避免弧交叉。 网络图中弧交叉,就显得零乱,不便于分析处理。 如图(a)的网络图中有交叉弧
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十二 排序 统筹
链接地址:https://www.31doc.com/p-3168479.html