题目

Problem

The network in Figure 1 shows the activities that need to be undertaken to complete a project. Each activity is represented by an arc and the duration of the activity, in days, is shown in brackets. The early event times and late event times are to be shown at each vertex and some have been completed.

Given that

CHN is the critical path for the project
the total float on activity B is twice the duration of the total float on activity I

(a) find the value of $x$ and show that the value of $y$ is 7

(2)

(b) Calculate the missing early event times and late event times and hence complete Diagram 1 in your answer book.

(3)

Each activity requires one worker, and the project must be completed in the shortest possible time.

(c) Draw a cascade chart for this project on Grid 1 in your answer book, and use it 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.

(6)

题目中文翻译

图 1 中的网络显示了完成项目需要进行的活动。每项活动由弧表示，活动的持续时间（单位：天）显示在括号中。每个顶点处应显示最早事件时间和最迟事件时间，部分已完成。

已知

CHN 是项目的关键路径
活动 B 的总时差是活动 I 总时差持续时间的两倍

(a) 找到 $x$ 的值并证明 $y$ 的值为 7

(b) 计算缺失的最早事件时间和最迟事件时间，从而完成答案本中的图 1。

每项活动需要一名工人，项目必须在最短时间内完成。

解答

(a)

解法一

思路

展开

CHN 是关键路径，所以它的总持续时间等于项目工期 26 天，由此先求出 $x$ 。再用“活动总时差 = 终点的最迟事件时刻 $-$ 起点的最早事件时刻 $-$ 活动持续时间”：先由图中已知时刻求 B 的总时差，再利用它是 I 的总时差两倍这一条件推出 $y$ 。

答题过程

展开

Since $CHN$ is the critical path,

7+9+x=26,

\boxed{x=10}.

The total float on activity $B$ is

9-0-5=4.

The total float on activity $I$ is $22-13-y$ . Therefore

4=2(22-13-y)=2(9-y).

Hence

2=9-y

and so, as required,

\boxed{y=7}.

(b)

解法一

思路

展开

最早事件时刻由左至右进行 forward pass：到达同一事件的各条路径取最大值。最迟事件时刻由右至左进行 backward pass：从同一事件出发的各条路径取最小值。虚活动的持续时间为 0，也必须纳入这两次计算。

答题过程

展开

The completed event times are:

Event position	Earliest time	Latest time
Start	0	0
After $A$	4	7
At the head of $B$ and $E$	7	9
After $C$	7	7
At the head of $D$ and $F$	13	15
At the head of $G$ and $J$	16	17
After $H$	16	16
At the head of $I$ and $K$	21	22
Finish	26	26

For example, the forward pass gives

\max(4+8,\ 7+6)=13

at the head of $D$ and $F$ , and

\max(13+7,\ 16+5)=21

at the head of $I$ and $K$ .

The corresponding backward-pass values include

26-4=22

at the head of $I$ and $K$ , and

\min(22-7,\ 17-2)=15

at the head of $D$ and $F$ .

(c)

解法一

思路

展开

级联图先按最早开始时间画出每项活动的持续区间，再紧接着标出总时差区间。关键活动 C、H、N 没有时差。为了证明工人数不能少于 4，要找出无论怎样在时差范围内移动活动都必定重叠的时刻；在 $11<t<12$ 时，H、D、F、G 四项活动必定同时进行。

答题过程

展开

A cascade chart is formed from the following activity and float intervals:

Activity	Activity interval	Float interval
$A$	$0$ to $4$	$4$ to $7$
$B$	$0$ to $5$	$5$ to $9$
$C$	$0$ to $7$	Critical
$D$	$4$ to $12$	$12$ to $15$
$E$	$4$ to $5$	$5$ to $9$
$F$	$7$ to $13$	$13$ to $15$
$G$	$7$ to $13$	$13$ to $17$
$H$	$7$ to $16$	Critical
$I$	$13$ to $20$	$20$ to $22$
$J$	$13$ to $15$	$15$ to $17$
$K$	$16$ to $21$	$21$ to $22$
$L$	$21$ to $25$	$25$ to $26$
$M$	$16$ to $19$	$19$ to $26$
$N$	$16$ to $26$	Critical

For any time $t$ such that

11<t<12,

activities $H$ , $D$ , $F$ and $G$ must all be in progress. Hence at least four workers are required. The cascade chart permits the remaining activities to be scheduled within their floats using four workers, so the minimum number is

\boxed{4\text{ workers}}.

IAL 2022 June D1 Q2

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程