1994年美赛A题：通信网络的文件传输调度

1994年美赛A题：通信网络的文件传输调度是1994年MCM的A题，英文原题名为The Communications Network Problem。

返回1994年美赛赛题。

网络与并发占用

公司每天需要在各部门间交换前一日销售统计、当前生产指导等文件，希望尽快完成全部传输。用顶点$V_y$代表计算机，用边$e_x$代表要在两个端点计算机之间传输的一个文件。

$T(e_x)$为文件传输耗时，$C(V_y)$为一台计算机同时参与传输的容量。例如容量为1表示该机在任何时刻只能参与一次传输。每次传输在整个持续时间内都占用两个端点计算机。

目标是安排各文件的传输时间，使全部传输完成的最晚时刻最小；这一总工期称为makespan。

原题图1：文件传输网络示例，顶点容量和边耗时均保留。

完整网络与文件时间

原题图2：情形A、B共用的28顶点网络。

共有28台计算机。原图中的连接关系改列如下：边1—27构成情形A、B的网络；情形C保留这些边并增加28—42。下面的耗时适用于情形B、C；情形A将前27条边的耗时全部改为1。

文件边号	端点计算机	另一个端点	B/C传输耗时
1	V3	V1	3
2	V3	V2	4.1
3	V5	V7	4
4	V5	V4	7
5	V6	V5	1
6	V6	V3	8
7	V8	V6	3.2
8	V8	V9	2.4
9	V9	V13	5
10	V9	V10	8
11	V10	V12	1
12	V10	V11	4.4
13	V14	V8	9
14	V14	V15	3.2
15	V15	V19	2.1
16	V15	V16	8
17	V16	V18	3.6
18	V16	V17	4.5
19	V14	V20	7
20	V20	V24	7
21	V24	V26	9
22	V24	V25	4.2
23	V26	V27	4.4
24	V26	V28	5
25	V20	V21	7
26	V21	V22	9
27	V21	V23	1.2
28	V18	V11	6
29	V15	V13	1.1
30	V17	V19	5.2
31	V16	V19	4.1
32	V19	V22	4
33	V23	V24	7
34	V24	V3	2.4
35	V26	V1	9
36	V25	V28	3.7
37	V3	V7	6.3
38	V12	V4	6.6
39	V10	V5	5.1
40	V10	V6	7.1
41	V13	V14	3
42	V8	V20	6.1

原图的某些末端顶点标签在扫描件中不清，以上编号以完整28点编号和情形C清晰图对应：边23连接$V_{26},V_{27}$，边24连接$V_{26},V_{28}$。

情形A：相同文件耗时

28个部门每天传输27个文件，即边1—27。所有文件耗时为1，所有计算机容量为1。

给出最优调度和最小工期，论证该工期确实不可能进一步减少，说明求解方法，并讨论方法是否适用于文件耗时、计算机容量和图结构均任意的一般情形。

情形B：文件大小不同

仍使用边1—27和容量1，但耗时取上表给出的数值。

求最优调度和最小工期，说明最优性的依据与求解方法，讨论对一般情形的适用性，并评论特别或出乎预料的结果。

原题图3：情形C扩容后的网络，含新增连接。

情形C：扩容并增加传输

使用全部42条边及其给定时间。部分计算机升级，并发容量如下；未升级者仍为1。

计算机	并发容量
V1	2
V2	2
V3	1
V4	1
V5	1
V6	1
V7	1
V8	1
V9	2
V10	3
V11	1
V12	1
V13	1
V14	2
V15	1
V16	2
V17	1
V18	1
V19	1
V20	1
V21	1
V22	2
V23	1
V24	1
V25	1
V26	2
V27	1
V28	1

给出能够找到的最好调度及工期，讨论能否证明它是这个网络的最小工期，说明方法，并解释特别或出乎预料的结果。

原题与来源

COMAP官方题面（PDF）；题号和年份按COMAP历年赛题矩阵。核对日期：2026年9月22日。