《排序与统筹》PPT课件.ppt

第十一章 排序与统筹方法,第十一章 排序与统筹方法,11.1 车间作业计划模型,11.1 车间作业计划模型,车间作业计划 一个工厂生产工序的计划和安排。 能否在满足加工工艺流程前提下，通过各个零件在各台机床上加工次序上的合理安排， 使得完成这批零件加工任务所需总时间最少； 使得各加工零件在车间里停留的平均时间最短。,11.1 车间作业计划模型,一、一台机器、几个零件的排序问题,11.1 车间作业计划模型,例：某车间有一台磨床，现有六个零件都要求加工，按照什么样的加工顺序来加工这六个零件，才能使它们在车间停留的平均时间最少？,11.1 车间作业计划模型,不管按什么顺序加工这六个零件，都需要 8 小时。 由于各个零件加工时间不同，不同的加工顺序，使得这六个零件在车间里的平均停留时间是不一样的。,11.1 车间作业计划模型,按照某个加工顺序加工零件时，某个零件在车间的停留时间应该等于在它前面加工的各个零件的加工时间与这一零件本身的加工时间之和。,如果用 Pi 表示安排在第 i 位加工的零件所需的时间， 用 Tj 表示安排在第 j 位加工的零件总的停留时间， 则有,11.1 车间作业计划模型,这样可以计算出按照 1、2、3、4、5、6 顺序加工零件，各零件在车间的停留时间，如表所示 于是各零件平均停留时间为,11.1 车间作业计划模型,如果按照 3、2、4、5、6、1 顺序加工零件，也可以计算出各零件在车间的停留时间，如表所示 于是各零件平均停留时间为,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 + 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 个零件的排序问题， 按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。,11.1 车间作业计划模型,例：某车间有一台磨床，现有六个零件都要求加工，按照什么样的加工顺序来加工这六个零件，才能使它们在车间停留的平均时间最少？,从上述结论可知，按照3、4、5、6、1、2 顺序加工零件，可使各个零件的平均停留时间为最少。 各零件平均停留时间为,11.1 车间作业计划模型,习题,11.1 车间作业计划模型,11.1 车间作业计划模型,一、一台机器、几个零件的排序问题 二、两台机器，n 个零件,11.1 车间作业计划模型,例 某工厂要做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工。 应该如何安排这五个零件的先后加工顺序才能使完成这五个零件的总的加工时间为最少？,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.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，则将零件 i 排在第一位加工，并从零件集合中去掉这个零件。 3). 若最小数为 bj，则将零件 j 排在最后一位加工，并从零件集合中去掉这个零件。 4). 对剩下的零件重复上述手续，直到零件集合为空集时停止。,11.1 车间作业计划模型,若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。,11.1 车间作业计划模型,若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。,11.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 台机器 n 个零件，一般找不到类似的有效的求解算法，但可以用求解整数规划的方法加以解决。,习题 p279, 2,11.1 车间作业计划模型,解：此题为两台机器，n 个零件模型， 这种模型加工思路为： 钻床上加工时间越短的零件越早加工， 磨床上加工时间越短的零件越晚加工。 根据以上思路， 则加工顺序为： 2 ， 3 ， 7 ， 5 ， 1 ， 6 ， 4 。 钻床的停工时间是：40.1。磨床的停工时间是：42.6。,第十一章 排序与统筹方法,11.1 车间作业计划模型 11.2 统筹方法,11.2 统筹方法,一、导言,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图,11.2 统筹方法,甘特图（Gantt Chart）,1. 对各项活动进行计划调度与控制 2. 简单、醒目、便于编制 3. 横向表示时间，纵向表示活动 4. 各种图形符号,甘特图的例子,11.2 统筹方法,一、 基本概念,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图 3. 5060年代在美国取得成效,11.2 统筹方法,1956年，美国杜邦公司在制定企业不同业务部门的系统规划时，制定了第一套网络计划。 借助于网络表示各项工作与所需要的时间，以及各项工作的相互关系。 通过网络分析研究工程费用与工期的相互关系。 找出在编制计划时及计划执行过程中的关键路线。 这种方法称为关键路线法（Critical Path Method）简称CPM。 杜邦公司将关键路径法应用于设备维修，使维修停工时间由125小时锐减为7小时。,11.2 统筹方法,1958年，美国海军武器部在制定“北极星”导弹计划时应用了网络分析方法与网络计划。 注重于对各项工作安排的评价和审查。 称为计划评审方法（Program Evaluation and Review Technique）简称为PERT。 在北极星导弹设计中，应用计划评审技术，将项目任务之间的关系模型化，使设计完成时间缩短了2年。,11.2 统筹方法,关键路线法(CPM)主要应用在于以往类似工程中已取得一定经验的承包工程； 计划评审方法(PERT)更多地应用于研究与开发项目； 在这两种方法得到应用推广之后，又陆续出现了类似的最低成本和估算计划法、产品分析控制法、人员分配法、物资分配和多种项目计划制定法等等。 虽然方法很多，各自侧重的目标有所不同，应用的都是CPM和PERT的基本原理和基本方法。,11.2 统筹方法,一、 基本概念,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图 3. 5060年代在美国取得成效 4. 62年前苏联列入国民经济计划中,11.2 统筹方法,在苏联，政府规定所有大的建筑工程都必须采用网络计划技术进行管理； 1961年，美国政府规定，凡是一切由政府进行的工程，都必须采用CPM技术，而在军方，若不编制项目网络计划就不会得到批准； 英国不仅将网络计划技术应用于建筑业，而且还广泛应用于工业，要求直接从事管理和有关业务的专业人员必须掌握此技术。,11.2 统筹方法,一、 基本概念,用网络分析的方法编制的计划称为网络计划。它是二十世纪五十年代末发展起来的一种编制大型工程进度计划的有效方法。,1. 基础来源于图论 2. 前身是甘特图 3. 5060年代在美国取得成效 4. 62年前苏联列入国民经济计划中 5. 1962年进入我国,11.2 统筹方法,20世纪60年代，华罗庚 教授引进和推广了网络计划技术，鉴于其具有“统筹兼顾、合理安排”的特点 ，将这一技术称为“统筹方法”。 并于1965年发表了统筹方法评论，为推广应用网络计划方法奠定了基础。,11.2 统筹方法,一、导言,国内外应用网络计划的实践表明，它具有一系列优点，特别适用于生产技术复杂，工作项目繁多、且联系紧密的一些跨部门的工作计划。 例如： 新产品研制开发、大型工程项目、生产技术准备、设备大修等计划。还可以应用在人力、物力、财力等资源的安排，合理组织报表、文件流程等方面。,11.2 统筹方法,一、导言 二、网络计划图,11.2 统筹方法,二、网络计划图,定义： 反映一个工程项目中各项作业（工序）的内在逻辑关系的一种有向图，称为统筹图，又称计划网络图，以符号G表示。 此中“内在逻辑关系”是指由于工程本身的工艺与组织性要求，而对各工序提出的在时间上和空间上所要求的先后处理关系。,11.2 统筹方法,例 某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其 工序进度表 如下表所示，请画出其统筹方法网络图。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序,工序泛指一切需要消耗人力、物质或时间的具体活动过程，用弧表示。 在弧的上面，标以各工序的代号， 在弧的下面，标上完成此工序所需的时间（或资源）等数据 如图是由工序a、b、c、d、e、f、g，7道工序组成的网络图，工序旁边的数表示完成该工序需要的时间。,(1) 工序,紧前工序紧接在某工序之前的工序， （如图中的d、c是f的紧前工序） 紧后工序紧接在某工序之后的工序； （如图中的e、d均是a的紧后工序） 平行工序可以同时开始进行的各工序。 （如图中的e和d是平行工序）,(1) 工序,虚工序，表示工时为零，不消耗如何资源的虚拟工序。其作用只是为了正确表示前后两个工序之间的逻辑关系。 一般用虚箭线表示:,(1) 工序,虚工序，表示工时为零，不消耗如何资源的虚拟工序。其作用只是为了正确表示前后两个工序之间的逻辑关系。 一般用虚箭线表示:,(1) 工序,回路,虚工序,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序 (2) 事项,前后工序的交接点称为事项，常用“”加数字表示，数字主要起标号作用， 如图中标号从1至6，代表有6个事项，有时也可用来表示工序，如图的工序 e = 。 根据事项之间的相互关系，也可分为前置事项，后继事项、起（始）点事项和终点事项。,(2) 事项,前置事项指某一工序箭尾所连接的事项，它表示一个工序的开始，（如图中 和均是的前置事项，或分别是d、c两工序的前置事项） 后继事项指某一工序箭头所指的事项，它表示一个工序的结束。,(2) 事项,始点事项整个网络图开始的事项，即没有箭头进入的事项，也称为网络始点，如图中的。 终点事项网络图的最后一个事项，即没有箭尾出去的事项，也称网络的终点。如图中的。 介于始点事项和终点事项之间的所有事项均称为中间事项，它们所代表的意义都是双重的：既表示前一项工序的结束，又表示后一项工序的开始。,(2) 事项,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 (1) 工序 (2) 事项 (3) 线路,线路(或路线) 指网络图中从始点到终点的一条道路（沿着箭头的方向），如图中共有三条线路。 aeg 即： adf 即： bcf 即：,(3) 线路,线路长指线路上各工序所延续的时间之和，三条线路长分别是： 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) 工序 (2) 事项 (3) 线路,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项，一个总终点事项,i,(1) 网络图只能有一个总始点事项，一个总终点事项,i,(1) 网络图只能有一个总始点事项，一个总终点事项 （如图中有两个终点事项和，就是错误的。） 一般在实际中应将没有紧前工序的所有事项合并起来，构成网络的始点事项，把没有紧后工序的所有事项合并起来，构成网络的终点事项。,(1) 网络图只能有一个总始点事项，一个总终点事项 （如图中有两个终点事项和，就是错误的。） 一般在实际中应将没有紧前工序的所有事项合并起来，构成网络的始点事项，把没有紧后工序的所有事项合并起来，构成网络的终点事项。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项，一个总终点事项 (2) 网络图中不允许出现循环回路,(2) 网络图中不允许出现循环回路 在网络图中，如果从某个事项出发，顺某一线路能到原出发点，就称为循环回路。 例如图中的,就是一个循环回路。它表示的逻辑关系是错误的。会出现工程永远不能完成的现象。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项，一个总终点事项 (2) 网络图中不允许出现循环回路 (3) 任何两事项之间只能由一条弧连接,(3) 任何两事项之间只能由一条弧连接 否则，不利于分析、计算，甚至无法解决问题，相邻两点之间无论有多少工序，计算机都认为它们是同一个工序。若出现并行作业可引入虚工序.,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项，一个总终点事项 (2) 网络图中不允许出现循环回路 任何两事项之间只能由一条弧连接 (4) 尽量避免弧的交叉,尽量避免弧的交叉 在不改变逻辑关系的情况下合理安排工序间的相对位置，尽量避免弧交叉。 网络图中弧交叉，就显得零乱，不便于分析处理。 如图（a）的网络图中有交叉弧，可以调整为图（b）就避免弧的交叉。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项，一个总终点事项 (2) 网络图中不允许出现循环回路 任何两事项之间只能由一条弧连接 (4) 尽量避免弧的交叉 (5) 弧的方向一律指向或斜向右方 沿弧方向节点编号由小到大，自左向右增长 工序的终点编号大于始点编号,(5) 弧的方向一律指向或斜向右方 沿弧方向节点编号由小到大，自左向右增长 工序的终点编号大于始点编号,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 (1) 网络图只能有一个总始点事项，一个总终点事项 (2) 网络图中不允许出现循环回路 任何两事项之间只能由一条弧连接 (4) 尽量避免弧的交叉 (5) 弧的方向一律指向或斜向右方 沿弧方向节点编号由小到大，自左向右增长 工序的终点编号大于始点编号 (6) 使网络图简便易读,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 最好先画草图！ 再修改、整理，使画面清晰醒目，简单明了。 逻辑关系正确，布局合理、条理清楚， 便于下一步分析、计算及运用。,11.2 统筹方法,二、网络计划图 1、网络计划图的组成 2、网络计划图的编制规则 3、实例,11.2 统筹方法,（1）B、D工作在A工作完成后进行。,A,B,D,A,D,B,11.2 统筹方法,（2）A、B均完成后进行C,A,C,B,11.2 统筹方法,（3）A、B均完成后进行C、D。,A,C,D,B,11.2 统筹方法,（4）A完成后进行C， A、B均完成后进行D。,A,C,11.2 统筹方法,（4）A完成后进行C， A、B均完成后进行D。,A,C,D,B,11.2 统筹方法,（4）A 完成后进行 C， A、B均完成后进行D。,A,C,D,B,11.2 统筹方法,(5) A 完成后进行B， B、C 均完成后进行D。,A,B,D,C,11.2 统筹方法,（6）A、B 均完成后进行D， A、B、C 均完成后进行E， D、E 均完成后进行F。,A,B,D,C,E,F,11.2 统筹方法,例 某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其 工序进度表 如下表所示，请画出其统筹方法网络图。,1,2,a,60,1,2,4,a,60,b,15,1,3,2,4,a,60,b,15,c,13,1,3,2,4,a,60,b,15,c,13,d,38,1,3,2,4,5,a,60,b,15,e,8,c,13,d,38,例 将工序进度表作一些扩充，如下表所示，请画出其统筹方法的网络图。,1,3,2,4,5,a,b,e,c,d,6,f,7,h,g,1,3,2,4,5,a,b,e,c,d,6,f,7,h,g,g,6,1,3,2,4,5,a,b,e,c,d,6,f,7,h,g,6,显微手外科工序明细表,1,2,3,4,5,6,7,8,9,10,11,A,B,C,E,G,F,I,H,J,K,L,3,4,3,3,4,10,4,3,5,2,2,11.2 统筹方法,一、导言 二、网络计划图 三、网络时间与关键路线 1. 事项的时间参数,1. 事项的时间参数,事项本身并不占用时间，它只表示一道工序应在某一时刻开始或某一时刻结束的时间点(如图事项2,即代表a工序的结束，b、c工作的开始)。因此只关注事项的最早时间和最迟时间。,1. 事项的时间参数,（1）事项的最早时间 一个事项的最早时间用tE表示，指该事项为始点的各项工序最早可能开始的时间，也表示以该事项为终点的各项工序最早可能完成的时间。它等于从始点事项到该事项的最长路线上所有工序的工时总和。 （由起点开始，按编号由小到大的顺序逐个向后计算） 其中tE(i)表示事项j相邻的各紧前事项的最早时间,其中tE(i)表示事项j相邻的各紧前事项的最早时间,终点事项的最早时间显然就是整个工程的最早完工时间,（2）事项的最迟结束时间 事项的最迟时间以tL表示，表示在不影响任务总工期的条件下，以该事项为起点的各工序最迟必须开始的时间，或以该事项为终点的各工序的最迟必须结束的时间。一般情况下，将整个工程的最早完工时间作为任务的总工期。 （由起点开始，按编号由小到大的顺序逐个向后计算）,1. 事项的时间参数,其中tE(j)表示事项i相邻的各紧后事项的最迟时间,其中tE(j)表示事项i相邻的各紧后事项的最迟时间,其中tE(j)表示事项i相邻的各紧后事项的最迟时间,其中tE(j)表示事项i相邻的各紧后事项的最迟时间,11.2 统筹方法,一、导言 二、网络计划图 三、网络时间与关键路线 1. 事项的时间参数 2. 工序的时间参数,2. 工序的时间参数,（1）工序的最早开始时间和最早结束时间 工序的最早开始时间用tES表示，它是指本工序可能开始进行的最早时刻。任何一道工序必须等它所有紧前工序全部完成后才能开始，因此工序（i，j）的tES(i，j) 可以通过它的所有紧前工序（k，i）最早开始时间加上其的延续时间 t（i，j）取最大值来计算。 工序的最早结束时间是指工序按最早开始时间开始，所能达到的完工时间。用tEF表示，它等于工序的最早开始时间加上该工序所需时间之和。,2. 工序的时间参数,（2） 工序的最迟开始时间和最迟结束时间 除指向终点事项的工序，每一工序都有一个或几个紧后工序，不影响任务总工期的条件下，本工序最迟必须开始的时刻，称为工序的最迟开始时间，记作tLS ，工序最迟必须结束的时刻，称为工序的最迟结束时间，记作tLF 。,例 某公司装配一条新的生产线，其装配过程中的各个工序与其所需时间以及它们之间的相互衔接关系如表所示，求：完成此工程所需最少时间，关键路线及相应关键工序，各工序的最早开始时间和结束时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。,1,2,3,4,6,7,8,5,a,b,e,c,h,j,i,g,d,f,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,线路长指线路上各工序所延续的时间之和，其中最长的线路称为关键线路，它决定着整个计划任务的总工期。,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,- -就是一条关键路线，170天,线路长指线路上各工序所延续的时间之和，其中最长的线路称为关键线路，它决定着整个计划任务的总工期。,1,2,3,4,6,7,8,5,a,60,b,45,e,c,h,j,35,i,g,10,30,d,20,40,25,f,18,15,- -就是一条关键路线，170天,关键线路是在一定条件下形成的，不是固定不变的，关键路线和非关键线路有时是互相转化的。 (如压缩了关键线路上某工序的持续时间，可能它就不是关键线路了，而拖延某非关键线路上工序的持续时间，就可能使它成为关键线路) 所以在制定网络计划时，要以发展、动态的观点来看待关键线路。 在网络中可能出现多条关键线路，关键线路越多，表明各项作业工序的周期都很紧张，要求必须加强管理、严格控制，以保证任务的按期完成。,下面我们给出找出关键路线的办法。 （1）从网络的发点开始，按顺序计算出每个工序的最迟开始时间，记作tLS ，工序最迟必须结束的时刻，称为工序的最迟结束时间，记作tLF 。,工序a的最早 开始时间,工序a的最早 结束时间,1,2,a0，60,60,a,b,1,3,2,4,5,60,45,e,18,c,10,d,20,7,f,25,8,h,15,g,30,6,35,i,j,40,a0,60,b 60, 105,1,3,2,4,5,60,45,e 60, 100,18,c 60, 70,10,d 60,80,20,7,f 70, 88,25,8,h 100, 115,15,g80,110,30,6,35,i110,135,j135,170,40,下面我们给出找出关键路线的办法。 （2）从网络的收点开始计算出工序的最迟开始时间，记作tLS ，工序最迟必须结束的时刻，称为工序的最迟结束时间，记作tLF 。,a0,60,b 60, 105,1,3,2,4,5,60,45,e 60, 100,18,c 60, 70,10,d 60,80,20,7,f 70, 88,25,8,h 100, 115,15,g80,110,30,6,35,i110,135,j135,170,40,a0,60,b 60, 105,1,3,2,4,5,600,60,4590,135,e 60, 100,18117,135,c 60, 70,10107,117,d 60,80,2060,80,7,f 70, 88,25110,135,8,h 100, 115,15120,135,g80,110,3080,110,6,35135,170,i110,135,j135,170,4080,120,11.2 统筹方法,一、导言 二、网络计划图 三、网络时间与关键路线 1. 事项的时间参数 2. 工序的时间参数 3. 工序的时差,3 . 工序的时差,所谓时差，是指在不影响工程按期完成的条件下，各工序可以灵活机动使用的一段时间，所以又称为机动时间或宽裕时间。 计算和利用时差，是网络分析技术中一个重要的问题，它为计划进度的安排提供了选择的可能性，它是决定关键线路的科学依据。 利用时差可以进一步挖掘潜力，求得计划安排和资源分配的合理方案。常用的时差有两种 （1）工序的总时差 （2）工序的单时差,（1）工序的总时差 在不影响工序总工期的条件下，某工序（i，j）可以延迟其开工时间的最大幅度，叫做该工序的总时差。用 R（i，j）表示，其计算公式如下： R（i，j）= tLS ( i，j ) - tES ( i，j ) 或 R ( i，j ) = tLF ( i，j ) - tEF ( i，j ) （2）工序的单时差 单时差是指在不影响紧后工序最早开工条件下，此工序可以延迟开工时间的最大幅度，用 r ( i，j ) 表示，其计算公式为： r ( i，j ) = tES ( j，k ) - tEF ( i，j ) 其中：（j，k）是工序（i，j）的紧后工序。,（1）工序的总时差,a0,60,b 60, 105,1,3,2,4,5,600,60,4590,135,e 60, 100,18117,135,c 60, 70,10107,117,d 60,80,2060,80,7,f 70, 88,25110,135,8,h 100, 115,15120,135,g80,110,3080,110,6,35135,170,i110,135,j135,170,4080,120,工序b的总时差,为该工序的最早开始时间与最晚开始时间之差. 90-60=30,工序b的单时差,为紧后工序的最早开始时间与该工序最早结束开始时间之差. 135-135=0,工序的总时差 R（i，j）= tLS ( i，j ) - tES ( i，j ) 或 R ( i，j ) = tLF ( i，j ) - tEF ( i，j ),11.2 统筹方法,一、导言 二、网络计划图 三、网络时间与关键路线 1. 事项的时间参数 2. 工序的时间参数 3. 工序的时差 4. 工序所需时间的确定,工序所需时间是指进行该工序的作业所必需的延续时间，可以小时、日、周、月等为单位表示，一道工序所需时间可以用同类工作进行对比、类推或利用参考有关的统计资料来确定，也可以根据经验进行估算，这里根据不同的方法介绍两种类型的时间估算法。,4. 工序所需时间的确定,（1）肯定性估计法 它是对工序所需的时间给出一个肯定值的估计。一般在具备工时定额和劳动定额的任务中，工作的工时可以因这些定额资料确定。有些工作虽无定额可查，但有有关工作的统计资料，也可利用它们通过分析来确定工序的工时。,4. 工序所需时间的确定,（2）非肯定性估计法（不确定） 对于开发、创新性的试制任务，往往不具备前面所讲的资料，对工序所需的时间难以准确估计，只能做到对该工序所需时间给出如下三种估计值：,4. 工序所需时间的确定,a最快可能完工时间 （乐观时间） b最慢可能完工时间 (悲观时间) m最可能完工时间 (最可能时间),(一般地：amb ),4. 工序所需时间的确定,可以认为工序所需时间T是一个随机变量，它近似地服从正态分布，数学上可计算出T的期望值E ( T )、方差D ( T )和标准差：,4. 工序所需时间的确定,华罗庚教授对 曾做出特别说明:,实际工作情况表明，工作进行中出现最顺利或最不顺利的情况都比较少是在最可能完成时间内完成工作，工时的分布近似服从于正态分布。假定m的可能性为a，b可能性的两倍，则由加权平均得到： 在（a, m）间的平均值为（a + 2m）/3 在（m, b）间的平均值为（2m + b）/3 平均(期望)工时为 (a + 2m)/3 + (2m + b)/3,4. 工序所需时间的确定,可计算出工程在指定时间内完工的概率：如一项工程的关键线路上有几道工序，每道工序的平均需要时间为tei，方差为i （i=1，2 , , n），则工程的工期等于关键线路上各工序的时间和.即,4. 工序所需时间的确定,显然工期TN（TE ，2 ），现在指定该工程要在Tk 时间内完成，求能完成的概率是多少？由正态分布的和仍为正态分布得：,4. 工序所需时间的确定,显然TN（ ，2 ），则X的分布函数F(x)可通过积分的变量代换为标准分布函数表示，然后查表求出F(x)的值，事实上,4. 工序所需时间的确定,查标准正态分布表，即可得此概率值。记：,被称为临界值。 反之若要以概率（01）完成某工程，求工期至少为多少？也可由标准正态分布表，查得的临界值，从而求出工期: TK =TE+,计算出T的期望值E ( T )、方差D ( T )和标准差：,4. 工序所需时间的确定,如果一个随机变量的密度函数如下，那么称它服从分布： 其中,4. 工序所需时间的确定,分布通常用来为取值于某有限区间c，d的随机现象建立模型。当然，如果令c为原，而d-c为度量单位，密度函数向右偏斜。,1,2,3,4,5,8,7,6,a,g,b,e,d,f,c,i,h,3,2,2,2,1,4,2,4,2,1,2,3,4,5,8,7,6,a,g,b,e,d,f,c,i,h,3,2,2,2,1,4,2,4,2,我们还可以求出时差 TsLSES，我们把这些信息都填入工序时间表中。,以上的一些工作，我们都可以用管理运筹学软件来完成。 从表 11-15 上我们找到了一条从发点到收点由关键工序组成的关键路线，我们用红线在图 11-15上表示出这条关键路线。从而可知要完成领导干部的工商管理的培训组织工作所需的平均时间为各关键活动的所需平均时间之和，即有：,实际上完成整个培训组织工作所需时间上服从 一定的概率分布的，由于各关键工作所需时间都服从相同的概率分布即 分布，从概率论的中心极限定理可知，完成整个工作所需时间近似服从正态分布，这个正态分布的均值 E(T) 即为关键路线上各关键活动之均值（平均需要时间）之和，其方差 2 也为其关键路线上各关键活动之和，即有,中心极限定理 如果随机变量所描述的随机现象是由大量的相互独立的因素叠加的影响而成的，而且每一因素对总的影响作用不大，则这个随机变量就服从正态分布。,这样我们可以计算出此项培训组织工作不同完工时间的概率，例如这项工作在 16 周内完工的概率。 图11-16 就是以均值为15，方差为 1.05 的正态分布图，其中图中的阴影部分就是在 16 周内完工的概率。,为求得在 16 周内完工的概率，我们可以先求 值。 式中的 T 为预定完工时间即为16，E(T)=15。 即得 查标准正态分布函数表可知概率 () = (0.976) = 0.8355，即在 16 周内完工的概率为 83.55。 如果我们要求以 99 的概率来保证培训组织,工作就能保证培训工作如期做完，使培训工作如期举行，我们应在培训工作开始前多少周开始作培训组织工作，也就是说，概率为 99 的完工时间应为多少周。在标准正态分布函数表中可查出 () = 0.99 的 值， 2.33，再从公式 得 可求得 T2.331.025+1517.39（周）。 也就是说只要在培训工作开始前 17.39 周开始培训组织培训工作就能保证培训工作如期举行。,肯定性估计法，适用于不确定因素较少，有完整的统计资料，或有先例可循的工作； 而非肯定性估计法，是利用概率论的方法处理随机性事件，适用于不确定因素多且无先例可循的工作。 但无论是采用肯定性或非肯定性估计法，对工序所需时间的估计，都是以工序所赖以进行和实现的有关条件为基础的。,4. 工序所需时间的确定,11.2 统筹方法,一、导言 二、网络计划图 三、网络时间与关键路线 1. 事项的时间参数 2. 工序的时间参数 3. 工序的时差 4. 工序所需时间的确定,11.2 统筹方法,一、导言 二、网络计划图 三、网络时间与关键路线 四、网络优化,四、网络优化 绘制网络图、计算网络时间和确定关键路线，得到了一个初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合地考虑进度、资源和降低成本等目标，进行网络优化，确定最优的计划方案。 1. 时间资源优化 在编制网络计划安排工程进度时，我们要合理地利用现有资源，并缩短工程周期。为了使工程,进度与资源利用都得到比较合理安排，我们采用以下做法： 1）优先安排关键工序所需要的资源。 2）利用非关键工序的时差，错开各工序的开始时间，拉平资源需要量的高峰。 3）要统筹兼顾工程进度的要求和现有资源的限制，往往要经过多次综合平衡，才能得到比较合理的计划方案。,下面列举一个拉平资源需要量高峰的实例。在例 5 中，若完成工序 d，f，g，h，i 的机械加工工人人数为 65 人，并假定这些工人可以完成这五个工序中的任一个工序，下面我们来寻求一个时间资源优化方案。 有关 d， f，g，h，i 工序所需工人人数及上述工序开始时间，所需时间及时差如下表所示。,若上述各工序都按最早开始时间安排，那么从 60 天至第 135 天的 75 天里，所需的机械加工工人的人数如图 11-17 所示。,图 11-17,在图的上半部中，工序代号后括号内的数字是所需机械加工工人数，点划线表示非关键工序时差长度。图的下半部表示从第 60 天至 135 天内的 75 天里，所需机械加工工人数，这样的图一般称为资源负荷图。 从图 11-17 中 可见到:一方面在第 70 天至第 80天和从第 100 天至第 110 天这两段时间内，需要工人人数达到 80 与 81 人，远超过了现有工人人数；,另一方面在第 88 天到第 100 天和第 115 天至 135 天所需工人人数仅有 42 人和 26 人，远远少于现有工人数，这种安排资源负荷是不均匀的，不妥当的。 若各工序都按最晚开始时间安排，那么在第 117天至 135 天时期内需要工人数为 87 人，也大大超过了现有工人数。,我们应该优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序 f 从第 80 天开始，工序 h 从第 110 天开始。找到了时间资源优化的方案，在不增加工人的情况下按期完工。,2,5,4,6,7,3,f (22人),I (26人),g (42人),d(58人),h(39人),2、时间费用优化 在编制网络计划时，我们要考虑这样一些时间与费用的问题： . 在既定的时间前工程完工的前提下，使得所需要的费用最少； . 在不超过工程预算的条件下，使得工程最早完工。 这些就是时间费用优化要研究和解决的问题。,为了加快工程进度，使工程早日完工，必须设法缩短关键工序的作业时间，这样就需要增加人力、设备和工作班次，也就是这需要增加一笔费用，我们称之为直接费用。 但同时，由于加快了进度，使工程早日完工，减少了管理人员的工资、办公费等费用我们称之为间接费用。 一般来说工序的作业时间越短，直接费用越多而间接费用越少。,我们缩短工序的作业时间也有一定的限度，这个限度我们称之为工序的最快完成时间。我们设完成工序 j 的正常所需时间为 Tj ，直接费用为 cj，完成工序 j 的最快完成时间为 Tj，直接费用为 cj。这样我们可以计算出缩短工序 j 的一天工程所增加的直接费用，我们用 kj 表示，有 我们称 kj 为直接费用变动率，这是一个平均数。,时间费用优化问题可以建立以下两个线性规划模型。 模型一，在既定的时间 T 前完工的前提下，问各活动的完成时间为多少（即各项活动如何加速）才使因缩短工期而增加的直接费用最少。 我们设网络图上点 i 发生的时间为 xi （例如在图 11-18 中，点 2 的发生时间为 60 天，点 6 的发生时间为 110 天，故有 x2 60，x6 110 ）。,对一个工序，我们既可以用工序的代号 （ 例如a，b, .）来表示，也可以用表示这个工序的弧（例如（1，2）（2，3）,.,（i，j)，.）来表示，为了便于建模这里的工序我们用弧（i，j）来表示。 设工序（i，j）的提前完工时间为 yij，我们用 Tij，Tij 分别表示正常完工时间与最快完工的时间，则有工序（i，j）的实际完工时间为：Tijyij。我们也用cij 和 cij 表示用正常完成时间和最快完成时间,完成工序（i，j）所需要的费用，kij 为工序（i，j）的直接费用变动率。这样我们可以得到这个问题的线形规划模型如下：,在这个模型中，其目标函数就是取其所有缩短工期各工序增加的直接费用之和的最小值，其约束条件中，第一个约束不等式右边表示工序（i，j）的实际作业时间，左边表示弧（i，j）的两个顶点 j 和 i 的发生时间之差，这个不等式表示要有足够的时间间隔让工序（i，j）进行实际作业，这个约束不等式要对每个每个工序都成立；第二个约束不等式的,右边工序（i，j）缩短工序时间的最大允许值，左边 表示工序（i，j）的实际缩短时间，这个约束不等式表示工序（i，j）的实际缩短时间不能超过其缩短工期的最大允许值，这个不等式也要对每个工序完成。第三个约束不等式表示整个工程实际完工时间不能超过给定的期限 T。,例 7. 例 5 所提供的信息都作为本例的信息，列于表 11-10。另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表 11-17 所示。该工程要求在 150 天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在 140 天完工呢？ 表11-17的第一栏“工序”中填入了工序代号和它的弧。,表 11-10,表 11-17,解：本题的网络图，我们已在例 5 中绘制出了如图 11-19 所示，根据此网络图我们来建立数学模型。 设此网络图上第 i 点发生的时间为 xi ，