第十二章统筹方法

Chapter12统筹方法(SchedulingMethods)计划网络图网络时间与关键路线完成工序的网络时间与关键路线网络优化本章主要内容：21956年，美国杜邦公司运用网络计划技术来统筹各项工作，并找出编制与执行计划的关键路线，称为关键路线法(CriticalPathMethod)，简称CPM。1958年，美国海军武器局在制定研制“北极星”导弹计划时，开发出了计划评审技术(ProgramEvaluationandReviewTechnique)，简称PERT。1962年产生了能够体现随机因素作用的图示评审技术(GraphicEvaluationandReviewTechnique)，简称GERT。20世纪70年代，美国G.L.穆勒等人，在GERT基础上提出了风险评审技术(VentureEvaluationReviewTechnique)，简称VERT。这些技术方法均以网络描述工序及工序之间的关系。统筹方法3统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：一、计划网络图统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。工序•一项需要人力、物力或时间等资源的相对独立的活动过程，又称作业，•在网络图中用箭线“→”表示，•与某道工序前面直接相连的工序称为紧前工序，•其后直接相连的后继工序为紧后工序。计划网络图4结点(事件)结点(事件)是相邻工序的分界点，一般用圆圈来表示，每个结点编上顺序号：•箭尾结点表示工序的开始，•箭头结点表示工序的完成。结点(事件)既不消耗人力、物力，也不占用时间。由工序、事件及时间参数所构成的有向图即为网络图。用箭线表示工序，结点表示工序间相互关系的网络图，称箭线式网络。计划网络图5例1、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-1所示，请画出其统筹方法网络图。表12-1工序代号工序内容所需时间（天)紧前工序abcde产品设计与工艺设计外购配套零件外购生产原料自制主件主配可靠性试验601513388-aacb,d计划网络图6解:用网络图表示上述的工序进度表网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数．１２４５３abcde601383815图12-1计划网络图7例2、把例1的工序进度表做一些扩充，如表12-2，请画出其统筹方法的网络图。表12-2工序代号所需时间（天）紧前工序工序代号所需时间（天）紧前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ计划网络图8解：我们把工序ｆ扩充到图12-1发生了问题，由于ｄ是ｆ的紧前工序，故ｄ的结束应该是ｆ的开始，所以代表ｆ的弧的起点应该是④，由于工序ｂ的结束也是④，所以工序ｂ也成了工序ｆ的紧前工序，与题意不符。为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。ab15264360158e1013dc38f图12-2计划网络图ab9在网络图上添加ｇ、ｈ工序得网络图12-3。在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了一个点和虚工序如图12-4。1256734a6015bec13d388h510fg16图12-3计划网络图10在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。图12-41257834a6015bec13d388h510f616g计划网络图11•工序表示的规定：一条箭线和它的相关事项只能代表一道工序，不能代表多道工序，两个结点之间只能有一条箭线相连。•不允许出现缺口与回路：网络图中只能有一个始点和一个终点，使得自网络图的始点经由任何路径都可以到达终点。•虚工序：虚工序是为了表达相邻工序之间的逻辑关系而虚设的工序。不消耗时间、费用和资源，一般用虚箭线表示。•方向的规定：网络图是有方向的，工序应按工艺流程顺序或工作的逻辑关系从左向右排列。•编号的规定：编号应从始结点开始，按照时序依次从小到大对结点编号，直到终结点。编号时不允许箭头编号小于箭尾编号。绘制网络图的规则12二、网络时间与关键路线（P266）在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。网络时间与关键路线13例5、某公司装配一条新的生产线，具体过程如表12-3,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。(P267)表12-3工序代号工序内容所需时间（天）紧前工序abcdefghij生产线设计外购零配件下料、锻件工装制造1木模、铸件机械加工1工装制造2机械加工2机械加工3装配调试60451020401830152535/aaaacdd,egb,i,f,h144012346785a60b45echj35ig1030d2025f1815解：据表12-3,绘制网络图如图12-5。图12-5如图12-5,①-②-③-⑦-⑧就是一条关键路线，我们要干完所有的工序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路线。网络时间与关键路线154015•下面我们给出找关键路线的办法首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES)和最早结束时间（EF)，设一个工序所需的时间为t，这对于同一个工序来说，有EF=ES+t。工序a的最早开始时间工序a的最早完成时间12a[0，60]60图12-6网络时间与关键路线16其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF),显然对同一工序有LS=LF-t1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]1841015图12-7网络时间与关键路线17运用此法则，可以从首点开始计算出每个工序的LF与LS，如图12-8所示。1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,135]接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为Ts有Ts=LS-ES=LF-EF网络时间与关键路线18最后将各工序的时差，以及其他信息构成工序时间表如表12-5所示。这样就找到了一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。网络时间与关键路线19三、完成工序所需时间与关键路线当完成工序所需时间不确定的情况下如何求网络时间和关键路线？例6.长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表12-6所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。解：由表12-6，绘出统筹方法的网络图如图12-9所示。图12-1212356487abecdfghi完成工序所需时间与关键路线20活动（工序）活动（工序）内容紧前活动（工序）abcdefghi制定培训计划选聘培训教师列出一些可供选择的培训地点确定培训地点确定培训的日程安排落实教学设备，器材，资料发培训通知并确定学员名单订旅馆房间处理最后的一些事务-a-cb,deb,dgf,g完成工序所需时间与关键路线21由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.悲观时间。指不顺利情况下，最多时间，用b表示。如表12-7所示：表12-7单位：周活动乐观时间最可能时间悲观时间abcdefghi1.52.01.01.50.51.03.03.01.52.02.52.02.01.02.03.54.02.02.56.03.02.51.53.07.05.02.5完成工序所需时间与关键路线22显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从分布。我们可以用如下公式计算出完成活动所需的平均时间：以及方差：例如：完成工作g所需平均时间：同时求出方差为：64bmaT262)(ab460.75.340.364bmaTg94完成工序所需时间与关键路线23同样可以求出每个活动的完成所需平均时间及方差，如表12-8：表12-8活动T（平均时间）方差活动T方差a20.028f20.111b30.445g40.445c20.111h40.111d20.028i20.028e10.028完成工序所需时间与关键路线24下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图12-10所示。12345876同样也可以标上最晚开始时间和最晚完成时间等。a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]32221424212345876a[0,2]g[5,9]b[2,5]e[5,6]d[2,4]f[6,8]c[0,2]i[13,15]h[9,13]2[1,3]1[10,11]4[5,9]4[9,13]2[3,5]2[0,2]3[2,5]2[13,15]2[11,13]图12-10图12-11完成工序所需时间与关键路线25从表12-8上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和1.05。由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周内完工的概率。为求此概率，可以先求u值。式中的T为预定完工时间16，E（T）=15，算得u=0.976。查正态分布函数表可知概率为0.8355。即16周内完工的概率为83.55%.)(TETu025.105.1ihgbaTTTTT完成工序所需时间与关键路线26其正态分布图如图12-12所示：1615)(025.1TE图12-12完成工序所需时间与关键路线27四、网络优化(P275)得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。1.时间-资源优化做法：1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-9所示：网络优化28表12-9工序需要人数最早开始时