第十二章：统筹方法

Chapter12统筹方法

(SchedulingMethods)计划网络图网络时间与关键路线完成工序的网络时间与关键路线网络优化本章主要内容：21956年，美国杜邦公司运用网络计划技术来统筹各项工作，并找出编制与执行计划的关键路线，称为关键路线法(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发生了问题，由于ｄ是ｆ的紧前工序，故ｄ的结束应该是ｆ的开始，所以代表ｆ的弧的起点应该是④，由于工序ｂ的结束也是④，所以工序ｂ也成了工序ｆ的紧前工序，与题意不符。为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。

a1013dc38f图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所需平均时间：同时求出方差为：完成工序所需时间与关键路线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%.完成工序所需时间与关键路线26其正态分布图如图12-12所示：16图12-12完成工序所需时间与关键路线27四、网络优化(P275)得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。

1.时间-资源优化做法：

1）优先安排关键工序所需的资源。

2）利用非关键工序的时差，错开各工序的开始时间。

3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-9所示：网络优化28表12-9工序需要人数最早开始时间所需时间时差d5860200f22701847g428030h391001520i26110250

若上述工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人人数如图12-13所示。网络优化29

在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键工序时差长度。图的下半部表示从第60天至135天内的75天里，所需机械加工工人数，这样的图称为资源负荷图。

274635f(22人）18h(39人)1558人64人80人81人42人26人65人6080100120130d(58人）

i(26人）

g(42人）302025图12-13网络优化30

同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。246753

f(22人）

h(39人）

d(58人）

i(26人）

g(42人）工人数65人608010012013058人42人64人26人65人图12-14网络优化312.时间-费用优化(P278)需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。

直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。

间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。网络优化32

工序的最快完成时间：指完成时间的最高限度。我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为T`j,直接费用为c`j。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有

时间--费用优化问题可建立两个线性规划模型。网络优化33

模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。设工序（i,j)的提前完工时间为Yij,我们用Tij,T`ij分别表示正常完工时间与最快完工的时间，则有工序（i,j)的实际完工时间为：Tij-Yij。我们用Cij,C`ij表示用正常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（i,j)的直接费用变动率。得到这个问题的线性规划模型如下：

minf=∑（Kij*Yij)

（i,j)S.t.Xj-XiTij-Y`ij,对一切弧（i,j)YijTij-T`ij,对一切弧（i,j)Xn-X1T,

Xi0，Yij0。网络优化34例7.例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-10所示。表12-10工序Tij正常完工Cij直接费用T`ij最快完工C`ij直接费用直接费用变动率a60100006010000-b454500306300120c10280054300300d2070001011000400e40100003512500500f183600105440230g3090002012500350h153750105750400i256250159150290j35120003512000-网络优化35

该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？12345678abfechgijd图12-15网络优化36解：绘出如图12-15所示，根据此网络图建立数学模型。设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40虚拟弧（4，5）

x7-x515-y57x7-x625-y67x1=0,y120,网络优化

y2715,y235y2410