理解CPM算法

发布时间：2023-05-20

咱们来想一下，如果一个工作有N个子任务完成，子任务需要按照某种规则顺序执行，每个子任务都有在落后于计划日期的情况下执行所需要的时间。为了最小化整体延迟成本，需要确定一个最佳的执行顺序。这种应用场景时常出现在施工项目、新产品研发、电影和影视制作等多个领域。因此，提出了CPM算法。

一、CPM算法简介

CPM全称是Critical Path Method（关键路径法）,是一种网络图分析方法。CPM算法能够根据所有子任务的完成时间和前置约束关系，确定工作完成所需要的最短时间和每个子任务的最早开始时间和最晚开始时间。

二、如何进行CPM分析

CPM分析的第一步是创建一个网络图，然后对网络图进行拓扑排序。拓扑排序主要是在已知节点依赖关系的情况下，将图中所有节点排列成一个线性序列。这样的处理措施就可以形成一个建立在每个子任务完成时间上的流程图。 每个节点代表一项活动，边代表活动间的先后次序关系。

function cpm(nodes) {
    const edges = {}
    const visited = {}
    const stack = []
    // 找到长度为0的节点
    nodes.forEach(node => (visited[node.id] = false))
    nodes.filter(node => !node.edgesTo.length).forEach(node => dfs(node, visited, stack, edges))
    let cnt = 0
    let time = {}
    for (const node of nodes) time[node.id] = { earliestStart: 0, latestStart: Infinity }
    while (stack.length) {
        const node = stack.pop()
        if (!visited[node.id]) {
            visited[node.id] = true
            cnt++
        }
        for (let i = 0; i < node.edgesFrom.length; i++) {
            const edgeNodeId = node.edgesFrom[i]
            const updateList = forwardUpdate(node, time, edges, edgeNodeId)
            time = { ...time, ...updateList }
        }
        if (!cnt) time[node.id].earliestStart = 0
        for (let i = 0; i < node.edgesTo.length; i++) {
            const edgeNodeId = node.edgesTo[i]
            const updateList = backwardUpdate(node, time, edges, edgeNodeId)
            time = { ...time, ...updateList }
        }
    }
    return time
}

三、CPM分析的主要优势

CPM分析有许多优点：

  1. 确定工程任何时间的瓶颈。
  2. 可以对某些节点出现延误时产生的影响进行评估。如果有一个不重要的节点延迟了，对整个工程时间不会产生太大影响。而如果一条关键路径上面的节点延迟了时间，那么代价将非常高昂。
  3. 允许以合理的成本（以时间为单位）内快速安排活动的完成，有效地利用资源。

四、总结

由以上分析可以得出结论：关键路径法是一种很实用的项目管理工具，主要用于提高项目管理人员对项目进行计划、监督、预测和控制的管理效能，其优点显著，这对于提高企业的经济效益是非常有帮助的。

推荐文章