i
工作名称或代号 持续时间
j
工作代号 工作名称 持续时间
工作代号 工作名称 持续时间
计划网络图例题
某公司研制新产品的部分工序与所需时间以及它们之 间的相互关系如表所示，请画出其统筹方法网络图。
工序 工序内容 代号 a b c d e 产品设计与工 艺设计 外购配套零件 外购生产原料 自制主件 主配件可靠性 试验 所需时 间 /天 60 15 13 38 8 紧前 工序 a a c b,d
11000 400 12500 500 5440 230 12500 350
10000 35
h(5,7)
i(6,7) j(7,8) b g
15
25 35 f
3750
6250
10
15
5750
9150
400
290
12000 35
12000 -
1
a
6 h
i
7
j
8
5
解：设网络图上第i点发生的时间为xi，工序(i,j)提前完工的时间为 yij，则
d 58人
3 2 d(58人)
f (22人)
4
g(42人)
5
6
i(26人)
7
h(39人)
g 42人
i 26人
60
70
80
90 f 22人 (Ts=47)
100
110
120
130
时间/天
h 39人 (Ts=20)
网络计划的优化——时间-费用优化
模型一：因缩短工期而增加的直接费用最少
设网络上点i发生的时间为xi,工序用(i,j)表示。设工序(i,j)的提前 完工时间为yij，用Tij,Tij’分别表示正常完工时间与最快完工的 时间，则工序(i,j)实际完工时间为Tij- yij。cij和cij’表示用正常 时间和最快完成时间所需要的费用。
6
乐观时间、最可能时间和悲观时间 发生都具有一定概率，根据经验，这 些时间的概率分布被认为是正态分布
ba 6
2
2
a 4m b D 6
2 1 3 工序 ES LS EF LF Ts 4
5 7 6 是否关键工序
i[13,15]
2[13,15]
8
a
b c
0
2 0
0
2 1
f(22人) 18
4
2
g(42人) 30
5
6
i(26人) 25
7
h(39人) 15
d 58人 g 42人
i 26人
60
70
80 f 22人 (Ts=47)
90
100
110
120
130
时间/天
h 39人 (Ts=20)
应当优先安排关 键工序所需的工人， 再利用非关键工序的 时差，错开各工序的 开始时间，从而拉平 工人需要量的高峰
3
f 18
5
线路 线路的组成
1 2 3 4 5 ①→②→⑦→⑧ ①→②→③→⑦→⑧ ①→②→④→⑥→⑦→⑧ ①→②→④→⑤→⑦→⑧ ①→②→⑤→⑦→⑧
各工作的持续时间之和
60+45+35=140 60+10+18+35=123 60+20+30+25+35=170 60+20+15+35=130 60+40+15+35=150
90 107 60 80 117 80 120 110 135
105 70 80 100 88 110 115 135 170
135 117 80 120 135 110 135 135 170
30 47 0 20 47 0 20 0 0
否 否 是 否 否 是 否 是 是
b[60,105] 45[90,135] 3 a[0,60] 60[0,60] f[70,88] 18[117,135] 7 j[135,170] 35[135,170] 8
练习：指出下列计划网络图中的错误
v2
a v1 d b v4 f v6 h
v7
g i
c
v3
e
j v5
v5
v2 i v3
v2
a v1 b v3 c f
d
e v4
h
v7
v1
v4
v6
g
v6
v5
网络时间与关键路线例题
某公司装配一条新的生 产线，其装配过程中的各个 工序与其所需时间以及相互 衔接关系如下表所示，求： 完成此工程所需最少时间， 关键路线及相应关键工序， 各工序的最早开始时间及结 束时间和非关键工序在不影 响工程完成时间的前提下， 其开始时间与结束时间可以 推迟多久。
1
a 60
2
b 15
4
e 8
5
13 c
3
d 38
把工序进度表做一些扩充，如下表所示，请画出其统 筹方法网络图。
工序代号 需时/天 紧前工序 工序代号 需时/天 紧前工序
a
b c d a 60
60
15 13 38
a a c b 15
e
f g h 5 0
8
10 16 5 e 8 f 10 0 6 g 16
1
2
i[110,135] g[80,110] d[60,80] 4 6 20[60,80] 25[110,135] 30[80,110] e[60,100] h[100,115]
40[80,120]
5
15[120,135]
关键路线的特征：在线路上从起点到终点都由关键工序组成， 一般关键工序的时差都为零
15
16
网络计划的优化——资源优化
⑴优先安排关键工作所需要的资源。 ⑵利用非关键工作的总时差，错开各工作的开始时 间，避开在同一时区内集中使用同一资源，以免 出现高峰。 ⑶在确实受到资源制约，或在考虑综合经济效益的 条件下，在许可时，也可以适当地推迟工程的工 期，实现错开高峰的目的。
网络计划的优化——时间-费用优化例题
c 2 d e 3 4
工序
正常情况下
采取措施后
直接费用 变动率kij
a(1,2) b(2,7) c(2,3) d(2,4) e(2,5) f(3,7) g10000 60 4500 2800 7000 3600 9000 30 5 10 10 20
10000 6300 4300 120 300
计划网络图基本术语
• 计划网络图是在网络图上标注时标和时间参数的进度计划 图，实质上是有时序的有向赋权图 • 节点、箭线是计划网络图的基本组成元素
• 工作（也称工序、活动、作业），将整个项目按需要粗细 程度分解成若干需要耗费资源的子项目和单元，是计划网 络图的基本组成部分
计划网络图基本术语
• 双代号计划网络图 • 单代号计划网络图
最可能时间 悲观时间
2.0
2.5 2.0
2.5
6.0 3.0
2.0
1.0 2.0 3.5 4.0
2.5
1.5 3.0 7.0 5.0
2.0
2.5
绘制出统筹方 法的网络图
2 4
5 7
1
i
8
3
活动 a b c d e f g h i 平均 方差σ2 时间T 2 3 2 2 1 2 4 4 2 0.028 0.445 0.111 0.028 0.028 0.111 0.445 0.111 0.028
原工期170天，缩短为150天。先 关键工序 可缩短时间 直接费用变动率 在关键路线上找出直接费用变 d 10 400 动率最低的关键工序:i<g<d g 10 350 这三道工序各允许缩短工期10天， i 10 290 因此缩短g,i各10天
第七讲 排序与统筹方法
王晓婷 wangxt@
网络计划技术在现代管理中的应用
• 应用网络计划技术组织与管理生产和项目一般能缩短工期 20%左右，降低成本10%左右 • 美国政府于1962年规定，凡与政府签订合同的企业，都 必须采用网络计划技术 • 我国从20世纪60年代初期应用网络计划技术。钱学森引 入该技术应用于航天系统，华罗庚发表《统筹方法平话》 进行推广 • 实例：上海宝钢炼铁厂1号高炉土建工程，广州白天鹅宾 馆建设工程，50周年大阅兵
min f (kij yij )
(i , j )
s.t. xj-xi≥ Tij- yij （工序间的时间间隔大于任一工序时间） yij ≤ Tij-Tij’ （实际缩短时间小于缩短工期的最大允许值） xn-x1 ≤T （整个工程完成时间不能超过给定的期限T） xi ≥0, yij ≥0
给出在装配过程中 各道工序所需正常完工 时间与最快完工时间， 以及对应的直接费用与 缩短工期所增加的直接 费用。该工程要求150 天内完工，问每个工序 应比正常完工时间提前 多少天完成，才能使整 个工程因缩短工期增加 的直接费用最少。如果 工期要求在140天呢？
min f = 120y27 +300y23 +400y24 +500y25 +230y37 +350y46 +400y57 +290y67 s.t. x2 -x1≥60-y12; x7 –x2≥45-y27; x3 –x2≥10-y23; x4 –x2≥20-y24; x5 –x2≥40-y25; x7 –x3≥18-y37; x5 –x4≥0;虚拟弧（4,5） x7-x5≥15-y57; x7-x6≥25-y67; x8 –x7≥35-y78; x1=0；y12≤0； y27≤15； y23≤5； y24≤10； y25≤5； y37≤8； y46≤10； y57≤5； y67≤10； y78≤0； x8≤150； xi≥0,yij≥0；