题目

Problem

The network in Figure 2 shows the activities that need to be undertaken by a company to complete a project. Each activity is represented by an arc and the duration, in days, is shown in brackets. Each activity requires one worker. The early event times and late event times are shown at each vertex.

The total float on activity D is twice the total float on activity E.

(a) Find the values of x, y and z.

(3)

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

(4)

(c) Use your cascade chart to determine a lower bound for 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)

(Total 9 marks)

题目中文翻译

图 2 中的网络显示了一家公司完成项目需要进行的各项活动。每项活动用一条弧表示，持续时间（单位：天）显示在括号中。每项活动需要一名工人。每个顶点处显示了最早事件时间和最晚事件时间。

活动 D 上的总时差是活动 E 上总时差的两倍。

(a) 求 x、y 和 z 的值。

(b) 在答案册的 Grid 1 上画出该项目的级联图（cascade chart）。

解答

(a)

解法一

思路

展开

先由中间事件的最迟时间求 $y$ ，再比较 D、E 的总时差求 $x$ 。中央事件的最早时间 $z$ 要取所有进入路线的最早完成时间之最大值，并注意下方事件可经虚活动进入中央事件。

答题过程

展开

Activity $F$ finishes at the central event, whose late event time is $17$ . Hence

y=17-5=12.

The total float of activity $E$ is

17-4-7=6.

The total float of activity $D$ is twice this value, so

24-4-x=2(6).

Therefore

x=8.

The earliest completion times of the routes entering the central event include

4+7=11,\qquad 7+5=12,\qquad 7+9=16.

The lower event has earliest time $17$ and is linked to the central event by a dummy activity. Thus

z=17.

Hence

\boxed{x=8,\qquad y=12,\qquad z=17}.

(b)

解法一

思路

展开

关键活动 C、H、I、J 按最早开始时间首尾相接。其余活动从最早开始时间画实线活动条，再在右侧延伸总时差；这样每项活动只出现一次，并显示可移动范围。

答题过程

展开

The activity bars and their available floats are:

Activity	Earliest interval	Float available after the bar
C	$0$ to $7$	$0$
H	$7$ to $17$	$0$
I	$17$ to $24$	$0$
J	$24$ to $33$	$0$
A	$0$ to $4$	to time $10$
B	$0$ to $5$	to time $12$
D	$4$ to $12$	to time $24$
E	$4$ to $11$	to time $17$
F	$7$ to $12$	to time $17$
G	$7$ to $16$	to time $17$
K	$17$ to $27$	to time $33$
L	$17$ to $28$	to time $33$
M	$17$ to $26$	to time $33$

The completed cascade chart is:

(c)

解法一

思路

展开

寻找一个无论如何移动非关键活动都无法消除的重叠时段。J 在 24 到 33 期间进行，而 K、L、M 都必须在 17 后开始并于 33 前完成；在严格介于 24 与 26 的时刻，这四项活动必然同时进行，因此至少需要四名工人。

答题过程

展开

For any time $t$ such that

24<t<26,

activities $J,K,L$ and $M$ must all be in progress. Since each activity requires one worker, a lower bound for the minimum number of workers is

\boxed{4\text{ workers}}.

IAL 2020 Jan D1 Q3

题目

解答

(a)

解法一

思路

答题过程

(b)

解法一

思路

答题过程

(c)

解法一

思路

答题过程