题目

Problem

A project is modelled by the activity network shown in Figure 1. The activities are represented by the arcs. The number in brackets on each arc gives the time, in hours, to complete the corresponding activity. Each activity requires one worker. The project is to be completed in the shortest possible time.

(a) Complete Diagram 1 in the answer book to show the early event times and the late event times.

(4)

(b) Draw a cascade chart for this project on Grid 1 in the answer book.

(4)

(c) Use your cascade chart to determine the minimum number of workers needed to complete the project in the shortest possible time. You must make specific reference to time and activities. (You do not need to provide a schedule of the activities.)

(2)

题目中文翻译

一个项目由图 1 所示的活动网络模拟。活动由弧表示。每条弧上的括号内的数字表示完成相应活动所需的时间（单位：小时）。每项活动需要一名工人。项目应在最短时间内完成。

(a) 在答案本中完成图 1，显示最早事件时间和最迟事件时间。

(b) 在答案本的网格 1 上画出此项目的级联图。

解答

(a)

解法一

思路

展开

先按箭头方向做 forward pass：起点取 0，每个事件的最早时间取所有进入路线完成时间的最大值。再从项目完成时间 28 开始反向做 backward pass：每个事件的最迟时间取所有离开路线所允许时间的最小值。虚活动的工期为 0，但其优先关系仍须计入。

答题过程

展开

The early event times are found by a forward pass, taking the maximum value at each merge event. The late event times are found by a backward pass, taking the minimum value at each burst event.

The completed event times are:

Event position	Early event time	Late event time
Start	$0$	$0$
End of $A$	$3$	$7$
End of $C$	$2$	$2$
End of $B,E$	$7$	$7$
End of $D,F$ and upper dummy	$14$	$14$
End of $G$	$14$	$14$
End of $H,I$ and lower dummy	$14$	$17$
End of $J$	$20$	$20$
End of $K,L,M,N$	$24$	$24$
End of $P,Q$	$28$	$28$

Thus the completed activity network is:

(b)

解法一

思路

展开

级联图中，每项活动从其最早开始时间画起，先画活动本身的持续时间，再在其后标出总浮时。关键活动的总浮时为 0，依次连接成一条从时间 0 到 28 的关键路径。

答题过程

展开

For an activity from event $i$ to event $j$ with duration $d$ , its total float is

\text{total float}=L_j-E_i-d.

The information required for the cascade chart is:

Activity	Earliest start	Duration	Total float
$A$	$0$	$3$	$4$
$B$	$0$	$4$	$3$
$C$	$0$	$2$	$0$
$D$	$3$	$5$	$6$
$E$	$2$	$5$	$0$
$F$	$7$	$2$	$5$
$G$	$7$	$7$	$0$
$H$	$7$	$6$	$4$
$I$	$2$	$4$	$11$
$J$	$14$	$6$	$0$
$K$	$14$	$8$	$2$
$L$	$14$	$4$	$6$
$M$	$14$	$7$	$3$
$N$	$20$	$4$	$0$
$P$	$24$	$4$	$0$
$Q$	$14$	$8$	$6$

Hence the critical activities are

\boxed{C,E,G,J,N,P},

and the cascade chart is:

(c)

解法一

思路

展开

在级联图上寻找无论怎样利用浮时都必然同时进行的活动。时间刚超过 20 而尚未到 21 时， $N$ 正在关键路径上进行； $K$ 、 $M$ 和 $Q$ 也都尚未结束，因此此时至少需要 4 名工人。

答题过程

展开

For any time $t$ such that

20<t<21,

activities $K$ , $M$ , $N$ and $Q$ must be in progress simultaneously.

Since each activity requires one worker, the minimum number of workers required is therefore

\boxed{4\text{ workers}}.

IAL 2021 June D1 Q2

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程