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_{结束} = 项目完成时间\)


数据设置


探索项目基础信息

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`

我们需要根据之前显示的洞察更新结束节点的属性,然后才能在图中‘向后’遍历以找到最晚开始时间和最晚完成时间

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

设置浮动时间

回顾: \(浮动时间_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)),因为三天的延迟超过了培训用户活动的两天浮动时间,多了一天。

© . All rights reserved.