GraphGists

项目管理

介绍

在上个学期的优化课程中，我们简要讨论了项目管理，其中有一组具有给定持续时间的活动，某些活动需要在其他活动开始之前完成。我们被教导在 Excel 中探索项目时间表的管理，这很繁琐，并且由于其手动过程而容易出错。

项目

在此示例中，一家保险公司希望构建一个办公室局域网。他们希望了解项目的来龙去脉；即每个活动的开始/完成的最早时间和开始/完成的最晚时间，因为这些细节在项目管理中起着至关重要的作用。最终，他们希望了解每个活动的 *松弛时间* 和 *关键路径*，我们很快将定义它们。以下列出了活动及其持续时间。

标签 活动描述 持续时间（天）
A 执行需求分析 10
B 制定规范 6
C 选择服务器 6
D 选择软件 12
E 选择电缆 4
F 购买设备 3
G 编写用户手册 6
H 布线办公室 12
I 设置服务器 3
J 开发培训计划 14
K 安装软件 4
L 连接网络 3
M 培训用户 8
N 测试和调试系统 12
O 获得管理层认可 4

每个活动的依赖关系在此图中表示

每个活动的依赖关系

例如，活动 C 和 D（选择服务器和选择软件）需要在活动 G（编写用户手册）开始之前完成。

一些定义

项目经理对每个活动的以下属性感兴趣，我将简要定义它们，然后添加到图中。

最早完成时间

活动 \(j\) 最早完成的时间 \(EF_j\) 是活动的开始时间 \(ES_j\) 加上其持续时间 \(d_j\)

\(EF_j = ES_j + d_j\)

最早开始时间

由于活动必须在所有直接前置活动完成之后才能开始，因此活动 \(j\) 的最早开始时间 \(ES_j\) 是其 \(i\) 个直接前置活动的完成时间的最大值

\(ES_j = max(EF_i)\)

最晚开始时间

活动 \(j\) 最晚开始的时间，而不会延迟项目，是其最晚完成时间 \(LF_j\) 减去其持续时间 \(d_j\)

\(LS_j = LF_j - d_j\)

最晚完成时间

活动 \(i\) 最晚完成的时间，而不会延迟项目，\(LF_i\) 是其 \(j\) 个直接后继活动的开始时间的最小值

\(LF_i = min(LS_j)\)

项目完成时间、关键路径和松弛

完成项目所需的总时间是完成节点的开始时间

\(项目完成时间 = ES_{完成}\)

这也是图中（从开始到结束）最长的路径，在累积持续时间方面，其中累积持续时间是项目完成时间。这条最长的路径是 **关键路径**。关键路径包括持续时间增加会延长项目完成时间的活动。这些活动的 **松弛时间** 为 0；如果持续时间增加，则没有空间，不会影响项目的总体完成时间。不在关键路径上的活动 \(j\) 将具有正的松弛时间，它是最晚开始时间和最早开始时间之间的差

\(松弛_j = LS_j - ES_j\)

活动 \(j\) 的持续时间可以增加 \(松弛_j\) 而不影响项目的总体完成时间。

笔记

\(ES_{开始} = EF_{开始} = LS_{开始} = LF_{开始} = 0\)

\(ES_{完成} = EF_{完成} = LS_{完成} = LF_{完成} = 项目完成时间\)

数据设置

探索项目的 basics

Cypher 可以轻松回答关于项目的一些基本问题。

活动的直接依赖关系

假设我们想知道活动 M（培训用户）的直接前置活动

MATCH p = (:Activity)-[:PRECEDES]->(:Activity {description:'Train users'})
RETURN p

活动的全部依赖关系

假设我们想知道活动 G（编写用户手册）开始之前需要完成的所有活动

MATCH p = (:Activity)-[:PRECEDES*]->(:Activity {description:'Develop user manuals'})
RETURN p

项目完成时间

如前所述，项目的总体完成时间是在累积持续时间方面从开始到结束的最长路径

MATCH p = (:Activity {description:'Start'})-[:PRECEDES*]->(:Activity {description:'Finish'})
WITH p, REDUCE(x = 0, a IN NODES(p) | x + a.duration) AS cum_duration
ORDER BY cum_duration DESC
LIMIT 1
RETURN cum_duration AS `Project Completion Time`

该项目将需要 62 天才能完成（如果没有任何延迟）。

关键路径

MATCH p = (:Activity {description:'Start'})-[:PRECEDES*]->(:Activity {description:'Finish'})
WITH p, REDUCE(x = 0, a IN NODES(p) | x + a.duration) AS cum_duration
ORDER BY cum_duration DESC
LIMIT 1
RETURN p

关键路径中显示的活动的持续时间，如果增加，将延长项目的总体完成时间。项目经理现在知道他时间表上哪些活动对延迟最敏感。

将 EF、ES、LS、LF 和松弛时间添加到图中

这些有见地的属性可以使用 Cypher 轻松添加到图中，在我看来，这比手动将函数键入到多个 Excel 单元格中要好得多。

设置最早完成时间

回想一下：\(EF_j = ES_j + d_j\)

MATCH p = (:Activity {description:'Start'})-[:PRECEDES*]->(j:Activity)
WITH j, MAX(REDUCE(x = 0, a IN NODES(p) | x + a.duration)) AS ef
SET j.earliest_finish = ef

设置最早开始时间

回想一下：\(ES_j = max(EF_i)\)

MATCH (i:Activity)-[:PRECEDES]->(j:Activity)
WITH j, MAX(i.earliest_finish) AS max_ef
SET j.earliest_start = max_ef

更新完成节点

我们已经通过找到最长路径找到了项目的总体完成时间，但此属性也被捕获为完成节点的最早开始时间

MATCH (f:Activity {description:'Finish'})
RETURN f.earliest_start AS `Project Completion Time`

我们需要根据 前面显示的见解 更新 完成 节点的属性，然后才能“向后”遍历图以找到 LS 和 LF 时间

MATCH (f:Activity {description:'Finish'})
SET f.earliest_finish = f.earliest_start, f.latest_start = f.earliest_start, f.latest_finish = f.earliest_start

设置最晚开始时间

回想一下：\(LS_j = LF_j - d_j\)

MATCH p = (j:Activity)-[:PRECEDES*]->(f:Activity {description:'Finish'})
WITH j, MIN(REDUCE(x = f.earliest_start, a IN NODES(p) | x - a.duration)) AS ls
SET j.latest_start = ls

设置最晚完成时间

回想一下：\(LF_i = min(LS_j)\)

MATCH (i:Activity)-[:PRECEDES]->(j:Activity)
WITH i, MIN(j.latest_start) AS min_ls
SET i.latest_finish = min_ls

设置松弛时间

回顾：\(slack_j = LS_j - ES_j\)

MATCH (a:Activity)
SET a.slack = a.latest_start - a.earliest_start

查看更新后的图表

查看 ES、EF、LS、LF 和松弛时间

MATCH (a:Activity)
RETURN a.description AS Activity, a.earliest_start AS `Earliest Start Time`, a.earliest_finish AS `Earliest Finish Time`, a.latest_start AS `Latest Start Time`, a.latest_finish AS `Latest Finish Time`, a.slack AS Slack
ORDER BY a.id

松弛时间告诉项目经理，每个活动可以在其最早开始时间之后延迟多少天，而不会影响整个项目的完成时间。松弛时间为 0 的活动处于关键路径上，因为它们不能延迟；将这些活动与查询 5中的活动列表进行比较。

回答重要问题

没有哪个项目能一帆风顺，因此项目经理会想知道各种挫折会如何影响最终结果。所有这些问题都可以通过查看活动的松弛时间来解答。

如果设置服务器延迟两天，这将如何影响整个项目的完成时间？

MATCH (a:Activity {description:'Set up server'})
RETURN a.slack AS Slack

设置服务器延迟两天不会影响项目的完成时间，因为设置服务器的松弛时间为五天。

负责培训用户的家伙打电话说他将在最初承诺的日期之后三天到达。

这将如何影响整个项目的完成时间？

MATCH (a:Activity {description:'Train users'})
RETURN a.slack AS Slack

整个项目的完成时间将从 62 天增加到 63 天 (62 + (3 - 2))，因为三天的延迟超过了用户培训的两天松弛时间一天。