版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Chapter 12 排序与统筹方法排序与统筹方法12.1车间作业计划模型车间作业计划模型12.2 绘制网络图绘制网络图 12.3网络参数网络参数12.4 网络的优化网络的优化 运运 筹筹 学学 Operations Research Page 2 2022年5月27日星期五 在本章中,我们将介绍车间作业计划模型和统筹方法。这在本章中,我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同,但当我们面临两个问题尽管处理的方法有所不同,但当我们面临必须完成必须完成若干项不能同时进行的工作时,它们都将帮助我们应该按照若干项不能同时进行的工作时,它们都将帮助我们应该按照怎样的次序、怎
2、样的时间表来做这些工作怎样的次序、怎样的时间表来做这些工作,使得效果最佳,使得效果最佳(例如完成全部工作所用时间最短或费用最少等等)。(例如完成全部工作所用时间最短或费用最少等等)。 Page 3 2022年5月27日星期五 1 1车间作业计划模型车间作业计划模型 Page 4 2022年5月27日星期五 1 1车间车间作业作业计划模型计划模型一、一台机器、一、一台机器、n n个零件的排序问题个零件的排序问题 例例1.某车间只有一台高精度的磨床,常常出现很多零件同时要求这台某车间只有一台高精度的磨床,常常出现很多零件同时要求这台磨床加工的情况,现有六个零件同时要求加工,这六个零件加工所需时磨床
3、加工的情况,现有六个零件同时要求加工,这六个零件加工所需时间如下表所示。间如下表所示。 应该按照什么样的加工顺序来加工这六个零件,才能使得这六个零应该按照什么样的加工顺序来加工这六个零件,才能使得这六个零件在车间里停留的平均时间为最少?件在车间里停留的平均时间为最少?零件零件加工时间加工时间(小时)(小时)零件零件加工时间加工时间(小时)(小时)1231.82.00.54560.91.31.5 Page 5 2022年5月27日星期五 1 1车间作业计划模型车间作业计划模型 例1解:如果我们用Pi表示安排在第i位加工的零件所需的时间,用Tj表示安排在第j位加工的零件在车间里总的停留时间,则有T
4、j = P1 + P2 + Pj-1 + Pj = 不同的加工顺序得到不同的各零件的平均停留时间,如何得到一个使得各零件的平均停留时间最少的排序呢?这就是我们最后要解决的优化问题,而且我们要设法找到一种简便的算法。 对于某种加工顺序,我们知道安排在第j位加工的零件在车间里总的停留时间为Tj , Tj = 1jiiPjiiP1 Page 6 2022年5月27日星期五可知这六个零件的停留时间为: T1 + T2 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) +(P1 + P2 + P3
5、+ P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各个零件平均停留时间为从上式可知,对于一台机器n个零件的排序问题,只要系数越大,配上加工时间越少的,即按照加工时间排出加工顺序,加工时加工时间越少的零件排在越前面,加工时间越多的零件排在越后面间越少的零件排在越前面,加工时间越多的零件排在越后面,可使各个零件的平均停留时间为最少。1234566P5P4P3P2PP6 Page 7 2022年5月27日星期五各个零件平均停留时间为:与用“先到先加工”顺序所需平均停留时间4.93相比较,
6、有很大的改进。零件加工时间停留时间 零件 加工时间 停留时间30.50.561.54.240.91.411.86.051.32.732.080.5 1.42.74.26.08.03.8(6小时) Page 8 2022年5月27日星期五二、两台机器,二、两台机器,n个零件个零件问题的提出:设有n个工件需要在、机床上加工,每个工件都必须经过先后两道加工工序,以ai、bj分别表示工件i(1in)在、上的加工时间,问如何安排在两机床上各工件的加工顺序,使在机床上加工第一个工件开始到在机床上加工完最后一个工件为止,所用的加工总时间最少? Page 9 2022年5月27日星期五例:问如何安排,使连续加
7、工完所有工件的加工总时间最少?加工时间机 床工件D1a12b1=5D2a2=6b2=1D3a3=3b3=6 Page 10 2022年5月27日星期五编号 加工次序加工中时间衔接情况总时间D1D2D3A:B:D1D3D2A:B:D3D1D2A:B:265316172356611432656115 Page 11 2022年5月27日星期五三种工件加工次序共有3!6种,以上表格列出三种情况;从表中可知,不论哪种次序,在机床上加工总时间都是11,比较可见,在机床上加工时间最短的放在最后加工,可以节省等待时间,的总时数要小。比较可见,在机床中加工时间最短的放在前面加工,就可较早地开始在机床上加工,因
8、而总时数要小。 Page 12 2022年5月27日星期五最优排序规划:最优排序规划:(1)先作工件的加工时间的工时矩阵;(2)在工时矩阵中找最小元素(若不止一个,任取一个),若它在上行上行,将相应的工件排在最前面加工最前面加工,若它在下行下行,则将相应的工件排在最后加工最后加工。(3)将排定位置工件的对应列从中划掉,然后对余下的工件重复(2),直到所有工件排完。nnbbbaaaM.2121 Page 13 2022年5月27日星期五例: 加工次序: 3745762734*D2*D1*D4*D3*D5总工时28:364775473212.2 绘制网络图绘制网络图 Draw network pl
9、ot Page 15 2022年5月27日星期五 用网络图编制的计划称为用网络图编制的计划称为网络计划网络计划,网络计划技术由,网络计划技术由计划协计划协调技术调技术(Program Evaluation and Review Technique 简写为简写为PERT)与)与关键路径法关键路径法(Critical Path Method 简写为简写为CPM)组)组成。成。12.2.1项目网络图的基本概念项目网络图的基本概念 PERT主要针对完成工作的时间不能确定而是一个随机变量主要针对完成工作的时间不能确定而是一个随机变量时的计划编制方法,活动的完成时间通常用时的计划编制方法,活动的完成时间通
10、常用三点估计法三点估计法,注重,注重计划的评价和审查。计划的评价和审查。12.2 绘制网络图绘制网络图 Draw network plot CPM以经验数据确定工作时间,看作是确定的数值,以经验数据确定工作时间,看作是确定的数值,主要研究项目的费用与工期的相互关系。通常将这两种方主要研究项目的费用与工期的相互关系。通常将这两种方法融为一体,统称为网络计划、网络计划技术法融为一体,统称为网络计划、网络计划技术(PERT/CPM)。 Page 16 2022年5月27日星期五 网络计划主要应用于新产品研制与开发、大型工程项目网络计划主要应用于新产品研制与开发、大型工程项目的计划编制与计划的优化,是
11、项目管理和项目安排领域目前的计划编制与计划的优化,是项目管理和项目安排领域目前比较科学的一种计划编制方法,比甘特图(比较科学的一种计划编制方法,比甘特图(Cantt chart)或)或称横道图称横道图(bar chart)计划方法有许多优点。计划方法有许多优点。 网络计划有利于对计划进行控制、管理、调整和优化,网络计划有利于对计划进行控制、管理、调整和优化,更清晰地了解工作之间的相互联系和相互制约的逻辑关系,更清晰地了解工作之间的相互联系和相互制约的逻辑关系,掌握关键工作和计划的全盘情况掌握关键工作和计划的全盘情况。 PERT最早应用于美国海军北极星导弹的研制系统,由于该最早应用于美国海军北极
12、星导弹的研制系统,由于该导弹的系统非常庞大复杂导弹的系统非常庞大复杂,为找到一种有效的管理技术为找到一种有效的管理技术,设计了设计了PERT这种方法这种方法,并使北极星导弹的研制周期缩短了一年半时间。并使北极星导弹的研制周期缩短了一年半时间。 CPM是与是与PERT十分相似但又是独立发展的另一种技术,十分相似但又是独立发展的另一种技术,是是1957年美国杜邦公司的沃克(年美国杜邦公司的沃克(M.R.walker)和兰德公司的小)和兰德公司的小凯利凯利(J.E.Kelley)共同研制的一种方法。它主要研究大型工程的共同研制的一种方法。它主要研究大型工程的费用与工期的相互关系。费用与工期的相互关系
13、。12.2 绘制网络图绘制网络图 Draw network plot Page 17 2022年5月27日星期五用甘特图进行计划与排程用甘特图进行计划与排程 甘特图是对简单项目进行计划与排程的一种常用工具。它能使管理者先为项目各项活动做好进度安排,然后再随着时间的推移,对比计划进度与实际进度,进行监控工作。某银行建立新直销部门的计划用甘特图表示如下; Page 18 2022年5月27日星期五 开始 2 4 6 8 10 12 14 16 18 20 选址面试应聘者培训员工订办公家具安装电话家具装配迁入/开张 Page 19 2022年5月27日星期五123456选、定址订购家具家具装配面试应
14、聘者雇佣与培训迁入装电话84911631 Page 20 2022年5月27日星期五【例例12.1】(华罗庚:统筹方法平话及补充)某家庭有夫妇两人(华罗庚:统筹方法平话及补充)某家庭有夫妇两人安排家务,要求从上午安排家务,要求从上午11:30开始到下午开始到下午2:00结束去上班,做下结束去上班,做下列列3件事:件事:工序工序 工时工时 代号代号洗衣洗衣 3小时小时 A烧饭烧饭 1小时小时 B吃饭吃饭 0.5小时小时 C 怎样安排,使完成时间最短?怎样安排,使完成时间最短?A,3B,1C,0.54.5A,3B,1C,0.53.5A1,2A2,1C,0.5B,12.512.2 绘制网络图绘制网络
15、图 Draw network plot Page 21 2022年5月27日星期五 工序工序 或称为或称为作业作业、活动活动,指任何消耗时间或资源的活动,如新,指任何消耗时间或资源的活动,如新产品设计中的初步设计、技术设计、工装制造等。根据需要,工产品设计中的初步设计、技术设计、工装制造等。根据需要,工序可以划分得粗一些,也可以划分得细一些。序可以划分得粗一些,也可以划分得细一些。 事件事件 标志工序的开始或结束,本身不消耗时间或资源,或相对标志工序的开始或结束,本身不消耗时间或资源,或相对作业讲,消耗量可以小得忽略不计。作业讲,消耗量可以小得忽略不计。某个事件的实现,标志着在某个事件的实现,
16、标志着在它前面各顶作业(紧前工序)的结束,又标志着在它之后的各项它前面各顶作业(紧前工序)的结束,又标志着在它之后的各项作业(紧后工序)的开始作业(紧后工序)的开始。如机械造业中,只有完成铸锻件毛坯。如机械造业中,只有完成铸锻件毛坯后才能开始机加工;各种零部件都完成后,才能进行总装等。后才能开始机加工;各种零部件都完成后,才能进行总装等。 虚工序虚工序 虚设的工序。用来表达相邻工序之间的衔接关系,虚设的工序。用来表达相邻工序之间的衔接关系,不需要时间和资源。不需要时间和资源。12.2绘制网络图绘制网络图 Draw network plot Page 22 2022年5月27日星期五 网络图网络
17、图 由工序、事件及标有完成各道工序所需时间所由工序、事件及标有完成各道工序所需时间所构成的连通有向图。构成的连通有向图。路路 从起点沿箭头方向到终点的有向路。从起点沿箭头方向到终点的有向路。箭示网络图箭示网络图 用箭条表示工序的计划网络图。本章讲用箭条表示工序的计划网络图。本章讲的就是箭示图的就是箭示图12.2 绘制网络图绘制网络图 Draw network plot Page 23 2022年5月27日星期五紧前工序紧前工序 紧接某项工序的先行工序紧接某项工序的先行工序紧后工序紧后工序 紧接某项工序的后续工序紧接某项工序的后续工序前道工序前道工序 某工序之前的某工序之前的所有所有工序工序后续
18、工序后续工序 某工序之后的某工序之后的所有所有工序工序关键线路关键线路:路长最长的一条线路。 Page 24 2022年5月27日星期五注注:1.如果能够缩短关键工序所需的时间,就可以缩短工程的完工时间,而缩短非关键路线上的各个工序所需要的时间却不能使工程的完工时间提前。既使在一定范围内适当适当地拖长非关键路线上各个工序所需时间,也不至于影响工程的完工时间。2.对各关键工序,优先安排资源,挖掘潜力,采取相应措施,尽量压缩需要的时间,而对非关键路线上的各个工序,只要在不影响工程完工时间的条件下,抽出适当适当的人、财、物力等资源,用在关键工序上,以达到缩短工程工期,合理利用资源等目的。在执行计划过
19、程中,可以明确工作重点,对各个关键工序加以有效控制和调度。“向关键工作要时间,要非关键工作要资源向关键工作要时间,要非关键工作要资源”。即在工程进度管理中即在工程进度管理中, ,应把关键工作作为重点来抓应把关键工作作为重点来抓, ,以保证各项以保证各项工作和整个计划如期完成工作和整个计划如期完成 Page 25 2022年5月27日星期五2天天3天天5天天4天天1天天2天天3天天6天天12ABCDEFGH在下图中,在下图中,A是是D、E的紧前工序,的紧前工序,D、E是是A的紧后工序,的紧后工序,F是是A的的后续工序但不是后续工序但不是A的紧后工序;的紧后工序;A是是D、E、F的前道工序但不是的
20、前道工序但不是 F 的紧前工序。的紧前工序。注意紧前工序、紧后工序、前道工序和后续工序之间的关系。注意紧前工序、紧后工序、前道工序和后续工序之间的关系。12.2 绘制网络图绘制网络图 Draw network plot Page 26 2022年5月27日星期五表表12-1 工序明细表工序明细表 序序号号代代号号工序名称工序名称紧前工序紧前工序时间时间(天天)序序号号代代号号工序名称工序名称紧前工序紧前工序时间时间(天天)1A基础工程基础工程405E装修工程装修工程C252B构件安装构件安装A506F地面工程地面工程D203C屋面工程屋面工程B307G设备安装设备安装B504D专业工程专业工程
21、B208H试运转试运转E、F、G20ABCDGEFH4050302050252020图图121箭线图箭线图12.2 绘制网络图绘制网络图 Draw network plot【例例12.2】某项目由某项目由8道工序组成,工序明细表见表道工序组成,工序明细表见表12-1所示。用所示。用箭线法绘制该项目的项目网络图。箭线法绘制该项目的项目网络图。 Page 27 2022年5月27日星期五abc1.当工序当工序a完工后完工后b和和c可以开工可以开工(a)12.2.2 绘制网络图绘制网络图12.2 绘制网络图绘制网络图 Draw network plota 是是b,c的紧前工序。或的紧前工序。或b,c
22、是是a的紧后工序的紧后工序 Page 28 2022年5月27日星期五abcd(b) 2.当工序当工序a和和b完工后完工后c和和d可以开工可以开工a ,b是是c,d的紧前工序。或的紧前工序。或c,d是是a,b的紧后工序的紧后工序 Page 29 2022年5月27日星期五3.工序工序c在工序在工序a完工后就可以开工,完工后就可以开工,但但工序工序d必须在必须在a和和b都完工后才能都完工后才能开工开工acbd4.事件事件i、j之间有多道工序时之间有多道工序时,添加虚工序,添加虚工序(c)(d)abcabcd() Page 30 2022年5月27日星期五12.2 绘制网络图绘制网络图 Draw
23、network plot5. 用弧用弧(i,j)表示一道工序,事件表示一道工序,事件i是工序的开始,事件是工序的开始,事件j是工序的完成,是工序的完成,规定规定i j。见下图。见下图 ABCDGEFH4050302050252020 Page 31 2022年5月27日星期五acbdacbd(e)(f)ee图图1226. 网络图只有一个发点(项目的开始点)一个收点(项网络图只有一个发点(项目的开始点)一个收点(项目的结束点)。如图目的结束点)。如图122(e)所示,则应合成图)所示,则应合成图122(f)所示的一个始点及一个终点。)所示的一个始点及一个终点。 Page 32 2022年5月27
24、日星期五绘制网络图的基本原则绘制网络图的基本原则 在网络图中不能出现循环线路 12345ABCDE Page 33 2022年5月27日星期五在两个相邻的结点之间只能有一条弧线。 12345ABCD12456ABCD3BB Page 34 2022年5月27日星期五任何一项工序都有自己的编号,号码不能重复,而且结点编号的箭尾编号总比箭头编号小。除始、终点事项外,其余的事项应前后衔接 ,不允许有中断的缺口。尽量美观清晰始点、终点事项分别只有一个始点、终点事项分别只有一个。 Page 35 2022年5月27日星期五绘制网络图步骤:绘制网络图步骤: 任务的分解与分析 工序的时间估计 画图 结点编号
25、 Page 36 2022年5月27日星期五例:指出下图错误,并改之。(1)12345abcef2356abcef14改 Page 37 2022年5月27日星期五(2)1342567根据实际情况来改12345abcefdgabcdefg Page 38 2022年5月27日星期五(3)12345有循环 Page 39 2022年5月27日星期五(4)123456781.不简洁2.有两个终点 Page 40 2022年5月27日星期五例:工序ABCDEFGHIJK紧前工序AABBCDAGFHEGFIJABCDEGFHJIK12345678 Page 41 2022年5月27日星期五例:解:逆向
26、ABCDEFGHIJ工序ABCDEFGHIJ紧后工序BCDJEFGIHJJ123456789 Page 42 2022年5月27日星期五例:解:正向工序ABCDEFGHIJ紧后工序BCDJEFGIHJJABCDEFGHIJ123456789 Page 43 2022年5月27日星期五12.2.3 工序时间的估计工序时间的估计6ijijijba均方差为均方差为三点估计法是事先估计出工序的三种可能完成时间,其期望值三点估计法是事先估计出工序的三种可能完成时间,其期望值就作为工序时间的估计值。就作为工序时间的估计值。三种时间是:三种时间是:(1)完成工序(完成工序(i,j)的最短时间,称为)的最短时
27、间,称为乐观时间乐观时间,记为,记为aij(2) 完成工序(完成工序(i,j)的正常时间,称为)的正常时间,称为最可能时间最可能时间,记为记为mij(3) 完成工序(完成工序(i,j)的最长时间,称为)的最长时间,称为悲观时间悲观时间,记为,记为bij三种时间发生的概率分别为三种时间发生的概率分别为1/6、4/6、1/6,则工序(,则工序(i,j)完)完成时间的期望值和方差为:成时间的期望值和方差为:64)(ijijijijijbmatEt226)(ijijijijabtD12.2 绘制网络图绘制网络图 Draw network plot Page 44 2022年5月27日星期五【例例12.
28、3】根据某项目作业明细表根据某项目作业明细表122的资料,绘制项目网络图的资料,绘制项目网络图 工序工序紧前工序紧前工序工序时间工序时间(天天)工序工序紧前工序紧前工序工序时间工序时间(天天)a6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,h,g20fa,b12lg25表表122【解解】计划网络图如下:计划网络图如下:12.2 绘制网络图绘制网络图 Draw network plot工序工序紧前工序紧前工序 工序时间工序时间(天天) 工序工序紧前工序紧前工序工序时间工序时间(天天)a 6ga,b10b 9he,f12ca13id,h8dc5ji17ec16kd,
29、h,g20fa,b12lg25a,61b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,25图图123箭线网络图箭线网络图12354697810【例例12.4】根据下表作业明细表资料,绘制计划网络图根据下表作业明细表资料,绘制计划网络图工序工序紧前紧前工序工序工序的三种时间工序的三种时间工工序序紧前紧前工序工序工序的三种时间工序的三种时间ambamba679fc182426b5810ge,303542c111214hd,202630da,b,c151719if141722ea91012jf283438a,7.171b,7.83c,12.17d,17e,10.17f,
30、23.33h,25.67g,35.33i,17.33j,33.67图图124 Page 47 2022年5月27日星期五工序工序abcdefghij期望值期望值7.177.8312.171710.1723.3335.3325.6717.3333.67方差方差0.250.690.250.440.251.7842.781.782.78 Page 48 2022年5月27日星期五3.计划网络图的编制规则及其方法计划网络图的编制规则及其方法4.掌握掌握 虚工序的用法虚工序的用法5.编制网络图可以从左到右又可以从右到左或两边向中间画图编制网络图可以从左到右又可以从右到左或两边向中间画图6.网络图初稿完成
31、后对照工序明细表验证紧前紧后工序关系是否网络图初稿完成后对照工序明细表验证紧前紧后工序关系是否正确正确12.2 绘制网络图绘制网络图 Draw network plot1.本节的主要概念本节的主要概念 网络计划、计划网络图、甘特图、网络计划、计划网络图、甘特图、PERT、CPM、 结点图、箭示图、工序、事件、紧前工序、紧后工序结点图、箭示图、工序、事件、紧前工序、紧后工序2.区分紧前工序、紧后工序、前道工序和后续工序之间的关系区分紧前工序、紧后工序、前道工序和后续工序之间的关系7.三种时间估计公式,三种时间估计公式, 工序的期望时间和方差工序的期望时间和方差下一讲:网络参数下一讲:网络参数 1
32、2.3 网络参数网络参数 Network Parameter Page 50 2022年5月27日星期五 书上书上P264页的例题,用软件求得:页的例题,用软件求得:利用软件求解利用软件求解 Page 51 2022年5月27日星期五 Page 52 2022年5月27日星期五 工序的时间参数工序的时间参数TES(i,j)TLS(i,j)TEF(i,j)TLF(i,j)S(i,j) Page 53 2022年5月27日星期五(1)工序)工序(i,j)的最早开始时间(的最早开始时间(Earliest start time for an activity)TES(i,j)。是指紧前工序的最早可能完
33、工时间的最大值,。是指紧前工序的最早可能完工时间的最大值,计算公式为计算公式为 ),(),(max),(itiTjiTESjiES12.3 网络参数网络参数 Network Parameter12.3.1工序的时间参数公式及其含义工序的时间参数公式及其含义TES(1,j)=0例任一工序只有当其所有的紧前工序结束之后才能开始任一工序只有当其所有的紧前工序结束之后才能开始 Page 54 2022年5月27日星期五(2)工序)工序(i,j)的最早完工时间(的最早完工时间(Earliest finish time for an activity)TEF(i,j)。计算公式为。计算公式为 ), (),
34、 (), (jitjiTjiTESEF Page 55 2022年5月27日星期五(4) 工序工序(i,j)的最迟必须结束时间的最迟必须结束时间(Latest finish time for an activity) TLF(i,j)。计算公式为。计算公式为 ),(min),(),(),(jTjitjiTjiTLSjiLSLF(3) 工序工序(i,j)的最迟必须开始时间(的最迟必须开始时间(latest start time for an activity)TLS(i,j)。是指为了不影响紧后工序如期开工,工序最迟必须开工。是指为了不影响紧后工序如期开工,工序最迟必须开工的时间,计算公式为的时
35、间,计算公式为 ),(),(min),(),(min),(jitjTjitjTjiTLSjiLSjiLS12.3 网络参数网络参数 Network Parameter例TLS(i,n)=总工时t(i,n) Page 56 2022年5月27日星期五工序总时差越大,表明该工序在整个网络中的机动时间越大,可工序总时差越大,表明该工序在整个网络中的机动时间越大,可以在一定范围内将该工序的人财物资源利用到关键工序上去,达以在一定范围内将该工序的人财物资源利用到关键工序上去,达到缩短工期的目的。到缩短工期的目的。 (5) 工序工序(i,j)的总时差或松弛时间的总时差或松弛时间(Slack for an
36、activity) S(i,j)。是。是工序工序(i,j)的最迟开始的最迟开始(结束结束)时间与最早开始时间与最早开始(结束结束)时间之差,计算时间之差,计算公式为公式为 ),(),(),(),(),(),(),(),(jitjiTjiTjiTjiTjiTjiTjiSESLFEFLFESLS12.3 网络参数网络参数 Network Parameter在不影响任务总工期的条件下,某工序(i,j)可以延迟其开工时间的最大幅度。把把S(i,j)=0的工序连起来就是关键线路。的工序连起来就是关键线路。 Page 57 2022年5月27日星期五12.3.2网络时间与关键路线网络时间与关键路线 图图1
37、2-8 如图如图12-8 ,-就是一条关键路线,我们要干完所有的工序就是一条关键路线,我们要干完所有的工序就必须走完所有这样的路线,由于很多工序可以同时进行,所以网络中最就必须走完所有这样的路线,由于很多工序可以同时进行,所以网络中最长的路线就决定了完成整个工程所需的最少时间,这条路线称为关键路长的路线就决定了完成整个工程所需的最少时间,这条路线称为关键路线。线。12346785a60b45echj35ig1030d204025f1815 Page 58 2022年5月27日星期五下面我们给出找关键路线的办法下面我们给出找关键路线的办法 首先,从网络的发点开始,按顺序计算出每个工序的最早开始时
38、间首先,从网络的发点开始,按顺序计算出每个工序的最早开始时间(TES )和最早结束时间(和最早结束时间(TEF) ,设一个工序所需的时间为,设一个工序所需的时间为t,这对于同一,这对于同一个工序来说,有个工序来说,有 TEF=TES+t。 工序工序a的最早的最早开始时间开始时间TES工序工序a的最早的最早完成时间完成时间TEF12a0,6060图图12-9 Page 59 2022年5月27日星期五 由于任一工序只有当其所有的紧前工序结束之后才能由于任一工序只有当其所有的紧前工序结束之后才能开始开始.最早时间法则:最早时间法则:任一工序的最早开始时间应该任一工序的最早开始时间应该等于其所有紧前
39、工序最早结束时间中的最后的时间等于其所有紧前工序最早结束时间中的最后的时间,即等于其所有紧前工序最早结束时间中的最大值。即等于其所有紧前工序最早结束时间中的最大值。如如b,c,d,e工序的工序的TES=60. b的的TES=60,b的的TEF=TES+t=60+45=1051236785a0,6060b60,10545e60.100c60,70h100,115j135,17035i110.135g80,11030d60.80204025f70,881841015TESTEFTESTEF Page 60 2022年5月27日星期五其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各
40、个工序的最晚开始时间(缩写为TLS)和最晚结束时间(缩写为TLF),显然对同一工序有 TLS=TLF-t从收点往发点开始计算最后工序的TLF=?最后所有工序的最后所有工序的TEF的最大值的最大值 Page 61 2022年5月27日星期五 运用此法则,可以从收点开始计算出每个工序的运用此法则,可以从收点开始计算出每个工序的TLF与与TLS,如图,如图12-11所示。所示。由于任一工序必须在其所有的紧后工序开始之前结束由于任一工序必须在其所有的紧后工序开始之前结束。最晚时间法则:在不影响整个工程最早结束时间的情况下,任在不影响整个工程最早结束时间的情况下,任一工序的最晚结束时间一工序的最晚结束时
41、间TLF等于其所有紧后工序的最晚开始时等于其所有紧后工序的最晚开始时间间TLS中的最早时间中的最早时间,即等于其所有紧后工序的最晚开始时间即等于其所有紧后工序的最晚开始时间TLS的最小值的最小值. TLF=其所有紧后工序的最晚开始时间的其所有紧后工序的最晚开始时间的TLS的最小值。的最小值。 1236785a0,60600,60b60,1054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,1171512
42、0,135TESTEFTLSTLF Page 62 2022年5月27日星期五 运用此法则,可以从收点开始计算出每个工序的运用此法则,可以从收点开始计算出每个工序的TLF与与TLS,如图,如图12-11所示。所示。 例如工序例如工序b的的TLF的值的值=其紧后工序其紧后工序j的的TLS的最小值,即的最小值,即=135。 b的的TLS=TLF-t=135-45=90 工序工序b,f,i,h的的TLF都都=135 工序工序a的的TLF的值的值=其紧后工序其紧后工序b,c,d,e的的TLS的最小值,即的最小值,即=min90,107,60,80=60。 1236785a0,60600,60b60,1
43、054590,135e60.100c60,70h100,115j135,17035135,170i110.135g80,1103080,110d60.802060,804080,12025110,135f70,8818117,135410107,11715120,135TESTEFTLSTLF Page 63 2022年5月27日星期五TES(1,i)=0 TEF=TES+tTES=其所有紧前工序的其所有紧前工序的TEF的最大值的最大值最后工序的最后工序的TLF=最后所有工序的最后所有工序的TEF的最大值的最大值TLS=TLF-tTLF=其所有紧后工序的其所有紧后工序的TLS的最小值的最小值
44、Page 64 2022年5月27日星期五接着,可以计算出每一个工序的时差,把在不影响工程最早结束时间的条件下,工序最早开始(或结束)的时间可以推迟的时间,成为该工序的时差,对每个工序来说其时差记为Ts有 Ts=TLS-TES=TLF-TEF Page 65 2022年5月27日星期五 最后将各工序的时差,以及其他信息构成工序时间表如表最后将各工序的时差,以及其他信息构成工序时间表如表12-11所示。所示。 这样就找到了一条由关键工序这样就找到了一条由关键工序a,d,g,i和和j依次连接成的从发依次连接成的从发点到收点的关键路线。点到收点的关键路线。 关键线路:关键线路:ad g i j Pa
45、ge 66 2022年5月27日星期五a,6111b,9c,13d,5e,16f,12h,12g,10i,8k,20j,17l,250,60,96,199,219,1919,2419,3535,4747,7219,4447,6747,5555,7212.3 网络参数网络参数 Network Parameter0,614,236,1919,3523,3537,4735,4742,4747,5555,7252,72TESTEFTLSTLF用教材的方法来求解用教材的方法来求解最后工序的最后工序的TLF=最后所有工序的最后所有工序的TEF的最大值的最大值TLS=TLF-tTLF=其所有紧后工序的其所有
46、紧后工序的TLS的最小值的最小值TES(1,i)=0 TEF=TES+tTES=其所有紧前工序的其所有紧前工序的TEF的最大值的最大值 Page 67 2022年5月27日星期五表格形式见表表格形式见表12-5 表表12-5工序工序 (i,j)tijTES(i,j)TEF(i,j)TLS(i,j)TLF(i,j)S(i,j)关键工序关键工序a(1,2)606060是是b(1,3)909142314c(2,4)136196190是是d(4,7)51924424723e(4,5)16193519350是是f(3,5)12921233514g(3,8)10919374728h(5,6)1235473
47、5470是是i(7,10)8475547550是是j(10,11是k(9,11)20476752725l(8,11)25194447722812.3 网络参数网络参数 Network Parameter Page 68 2022年5月27日星期五工序时间是随机变量时,项目的完工期也是随机变量工序时间是随机变量时,项目的完工期也是随机变量设设Xk为关键工序为关键工序 k 所需时间的随机变量,则所需时间的随机变量,则 Xk 相互独立,工序的相互独立,工序的期望时间及方差为期望时间及方差为226)(64)()(kkkkkkkkkabXDbmaktXE工程完工期的期望值及方差
48、为工程完工期的期望值及方差为nkknnkknXE1221)(设关键工序数为设关键工序数为n,工程的完工期是一随机变量,工程的完工期是一随机变量nkkXX112.3.3项目完工的概率项目完工的概率12.3 网络参数网络参数 Network Parameter Page 69 2022年5月27日星期五nnnXZ令则由李雅普诺夫中心极限定理知则由李雅普诺夫中心极限定理知(式中式中n为关键工序数)为关键工序数)dteXZPXFXtnnn2221lim)(lim即当即当n很大时很大时Zn近似服从近似服从N(0,1)分布,则有)分布,则有nnnKZXX近似服从近似服从),(2nnN),(2nnNX即即1
49、2.3 网络参数网络参数 Network Parameter Page 70 2022年5月27日星期五设给定一个时间设给定一个时间X0,则,则工程完工时间不超过工程完工时间不超过X0的概率为的概率为0),(20XnndtNXXpNNXXdtNnn00) 1 , 0(要使工程完工的概率为要使工程完工的概率为p0,至少需要多少时间,至少需要多少时间X0XpdtNXXp00) 1 , 0(nnXX0查正态分布表求出查正态分布表求出X,由,由得得nnXX012.3 网络参数网络参数 Network Parameter Page 71 2022年5月27日星期五a,7.171b,7.83c,12.17
50、d,17e,10.17f,23.33h,25.67g,35.33i,17.33j,33.67【例例12.6】对例对例12.4所示的资料:所示的资料:(1)求工序的最早开始和最迟开始时间。)求工序的最早开始和最迟开始时间。(2)求工程完工期的期望值及其概率。)求工程完工期的期望值及其概率。(3)要求完工的概率为)要求完工的概率为0.98,至少需要多少天。至少需要多少天。00007.177.1712.1712.1712.1735.529.1717.3435.569.1769.1769.1733.8443.551.8435.569.1712.1726.523.6716.518.6700图图127【解
51、解】(1)工序的最早开始和最迟开始时间见图工序的最早开始和最迟开始时间见图12726.526.513.3 网络参数网络参数 Network Parameter Page 72 2022年5月27日星期五 (2) 关键工序是关键工序是c、f 和和j,由表,由表12-4及式及式(12.12)知,项目完工期知,项目完工期的期望值、方差、标准差分别为的期望值、方差、标准差分别为 12.17+23.33+33.6769.1720.25+1.78+2.764.79, =2.1886(3)X072,(X0)/=(7269.17)/2.1886=1.293 9014. 0)293. 1 (720XXp(4)已
52、知概率)已知概率p0=0.98,查正态分布表有,查正态分布表有0)( )0.98,2.05p XXZZ 02.05 2.188669.1773.65()XZ天要使项目完工的概率为要使项目完工的概率为0.98,至少需要,至少需要73.65天天 12.3 网络参数网络参数 Network Parameter Page 73 2022年5月27日星期五书上书上P267页的例题,用软件求得:页的例题,用软件求得:利用软件求解利用软件求解 Page 74 2022年5月27日星期五 Page 75 2022年5月27日星期五 最早完成时间最早完成时间=最早开始时间最早开始时间+工序时间工序时间最迟完成时
53、间最迟完成时间=最迟开始时间最迟开始时间+工序时间工序时间时差时差=最迟开始时间最迟开始时间-最早开始时间最早开始时间=最迟完成时间最迟完成时间-最迟最迟完成时间完成时间时间为时间为0的为关键工序的为关键工序 Page 76 2022年5月27日星期五1.本节介绍了网络参数的计算,共有本节介绍了网络参数的计算,共有8个公式,现综合如下:个公式,现综合如下:工序工序(i , j)的的最早可能开工时间最早可能开工时间 ijtiETiiTjiESTE)(max)(),(工序工序(i , j)的最迟必须开工时间的最迟必须开工时间ijLtjTjiLST)(),(工序工序(i , j)的的最早可能完工时间
54、最早可能完工时间ijESEFtjiTjiT),(),(工序工序(i , j)的的最迟必须完工时间最迟必须完工时间ijLSLFtjiTjiT),(),(工序工序(i , j)的的总时差总时差12.3 网络参数网络参数 Network Parameter),(),(),(),(),(),(),(),(jitjiTjiTjiTjiTjiTjiTjiSESLFEFLFESLS Page 77 2022年5月27日星期五事件事件j 的最早时间表示以的最早时间表示以j为开工事件工序最早可能开工时间为开工事件工序最早可能开工时间ijtiETijET)(max)(ijtjLTjiLT)(min)(事件事件 i
55、 的最迟时间表示以的最迟时间表示以i为完工事件工序最迟必须完工时间为完工事件工序最迟必须完工时间下一讲:网络计划的优化与调整下一讲:网络计划的优化与调整 2.三种时间估计公式,三种时间估计公式, 工序的期望时间和方差工序的期望时间和方差3.要求工程完工时间不超过要求工程完工时间不超过X0时,求完工的概率时,求完工的概率p04.要使工程完工的概率为要使工程完工的概率为p0,求至少需要多少时间,求至少需要多少时间X012.3 网络参数网络参数 Network Parameter12.4 网络的优化网络的优化 Optimization of Network Page 79 2022年5月27日星期五
56、得到初始的计划方案,但通常要对初始方案进行调整与完善。根据计划目标,综合考虑资源和降低成本等目标,进行网络优化,确定最优的计划方案。不同的优化目标有不同的优化方法,下面我们举几个例子来说明优化的几种方法:12.4.1把串联工作改为平行工作或交叉工作把串联工作改为平行工作或交叉工作 为了缩短整个任务的完工期,达到时间优化的目标,可以研究关键路线上串联的每一个工作,有无可能改为平行工作或交叉进行的工作,以缩短工期。 Page 80 2022年5月27日星期五 Page 81 2022年5月27日星期五 Page 82 2022年5月27日星期五12.4.2利用时差利用时差 由于网络图中的非关键路工
57、作都有时差,所以这些工作在开工时间上,具体工时上都具有一定的弹性。为了缩短任务的总工期,可以考虑放慢非关键工作的进度,减少这些工作的人力、资源,转去支援关键工作,以使关键工作的工时缩短来达到目的。 Page 83 2022年5月27日星期五12.4.3. 资源的合理配置资源的合理配置(1) 资源一定,如何组织、安排和调配资源保证项目按期完成。资源一定,如何组织、安排和调配资源保证项目按期完成。(2) 资源不足时,如何协调内部资源和采取应急措施资源不足时,如何协调内部资源和采取应急措施(加班、雇加班、雇工、增加设备、改进施工工艺工、增加设备、改进施工工艺)保证项目按期完成。保证项目按期完成。(3
58、) 资源、时间和成本的整体调整和系统优化资源、时间和成本的整体调整和系统优化 【例例12.7】项目各工序的时间和资源如表项目各工序的时间和资源如表128所示所示 (1)绘制项目网络图,按正常时间计算项目完工期,按期完)绘制项目网络图,按正常时间计算项目完工期,按期完工最多需要多少人。工最多需要多少人。(2)保证按期完工,怎样采取应急措施,使总成本最小又使)保证按期完工,怎样采取应急措施,使总成本最小又使得总人数最少,对计划进行系统优化分析。得总人数最少,对计划进行系统优化分析。12.3 网络的优化网络的优化 Optimization of Network Page 84 2022年5月27日星
59、期五工序工序紧前工紧前工序序每天需要每天需要资源资源(人人)时间时间(天天)成本(万元)成本(万元)时间的最大时间的最大缩量缩量(天天)应急增加成应急增加成本本(万元万元/天天)正常正常应急应急正常正常应急应急A51083070220BA1286130150210CB20107100130310DA12764050110ED201085080215FC,EE103360600G7139708644表表12812.3 网络的优化网络的优化 Optimization of Network Page 85 2022年5月27日星期五【解解】(1)项目网络图及最早最迟开始时间见图)项目网络图及最早最迟
60、开始时间见图1214。项目。项目完工期为完工期为40天。关键工序是天。关键工序是A、D、E和和G,非关键工序是,非关键工序是B、C、F,总时差都等于,总时差都等于9,也是工序,也是工序B、C、F的全部机动时间。的全部机动时间。 A,10B,8D,7C,10E,10F,3G,13H,0000101018172728404037271710190图图12142712.3 网络的优化网络的优化 Optimization of NetworkTESTLS Page 86 2022年5月27日星期五从图从图1215看出,如果非关键工序都按最早时间开始,第看出,如果非关键工序都按最早时间开始,第11天天到
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2027年教育学知识竞赛教育测量与评价冲刺卷
- 2021年度中央公务员遴选笔试真题
- 2027年省考面试计划组织协调预测试卷
- 2026年铪行业创新案例解析与发展策略报告
- 2026年机械零部件采购专员题库
- 2026年黄酒质检技术员考前冲刺试题及答案
- 2026职工权益保障知识竞赛题库及答案
- 京东物流员工培训课件
- (新教材)人教版小学数学六年级上册第2单元分数乘法《分数、小数混合运算及运算律》第一课时(导学案)
- ERP系统应用与实践(基于金蝶K3平台)
- 浙江省国际贸易集团有限公司行测笔试题目汇编2026
- 2026年临床医师三基三严年度培训计划
- 码头装卸作业管理制度
- 中粮米业公司大米加工设备操作规程及注意点
- GB/T 47038-2026航空航天 铝及铝合金化学转化膜层
- 管道护理培训内容
- 战场急救六大技术
- 雨课堂学堂在线学堂云《研究生学术与职业素养讲座》单元测试考核答案
- 2025年山西辅警招聘考试真题及参考答案详解一套
- 非典型溶血尿毒综合征(aHUS)专家共识解读(2025版)
- 《科学命题讲座》课件
评论
0/150
提交评论