网站做哪些比较有意思,微商分销商城模块源码,合肥网络推广公司乐蜂,wordpress模板编辑关键路径算法#xff08;Critical Path Method, CPM#xff09;是一种用于项目管理和调度的技术#xff0c;通过分析项目任务的最早开始时间、最晚完成时间和总时差#xff0c;找出项目中关键的任务路径。这条关键路径决定了项目的最短完成时间#xff0c;因为关键路径上的…关键路径算法Critical Path Method, CPM是一种用于项目管理和调度的技术通过分析项目任务的最早开始时间、最晚完成时间和总时差找出项目中关键的任务路径。这条关键路径决定了项目的最短完成时间因为关键路径上的每个任务都不能被延迟否则整个项目会被延迟。
关键路径算法的步骤 构建有向图将项目中的任务和任务间的依赖关系表示为有向图节点表示任务边表示依赖关系。 计算任务的最早开始时间和最早完成时间 最早开始时间ES, Earliest Start Time某任务可以开始的最早时间。最早完成时间EF, Earliest Finish Time某任务可以完成的最早时间EF ES 任务持续时间。 计算任务的最晚开始时间和最晚完成时间 最晚完成时间LF, Latest Finish Time某任务必须完成的最晚时间不会延误项目。最晚开始时间LS, Latest Start Time某任务必须开始的最晚时间LS LF - 任务持续时间。 计算总时差和自由时差 总时差Total Float, TF某任务可以延迟的时间TF LF - EF 或 TF LS - ES。自由时差Free Float, FF某任务可以延迟的时间不会延误后续任务FF min(ES of next tasks) - EF of current task。 找出关键路径关键路径上的任务总时差为 0连接这些任务的路径就是关键路径。
示例与实现
考虑一个简单的项目有 6 个任务A、B、C、D、E、F以及它们的持续时间和依赖关系如下
任务 A持续时间 3 天任务 B持续时间 2 天依赖于任务 A任务 C持续时间 4 天依赖于任务 A任务 D持续时间 2 天依赖于任务 B任务 E持续时间 1 天依赖于任务 C任务 F持续时间 3 天依赖于任务 D 和任务 E
构建有向图
A (3)
| \
B (2) C (4)
| |
D (2) E (1)\ /\ /F (3)计算最早开始时间和最早完成时间
任务 A: ES 0, EF 3任务 B: ES 3, EF 5任务 C: ES 3, EF 7任务 D: ES 5, EF 7任务 E: ES 7, EF 8任务 F: ES 8, EF 11
计算最晚开始时间和最晚完成时间
任务 F: LF 11, LS 8任务 D: LF 8, LS 6任务 E: LF 8, LS 7任务 B: LF 6, LS 4任务 C: LF 7, LS 3任务 A: LF 3, LS 0
计算总时差和自由时差
任务 A: TF 0任务 B: TF 1任务 C: TF 0任务 D: TF 1任务 E: TF 0任务 F: TF 0
找出关键路径
关键路径上的任务总时差为 0路径为 A - C - E - F。
Java 实现
import java.util.*;public class CriticalPathMethod {static class Task {String id;int duration;ListString dependencies;Task(String id, int duration, ListString dependencies) {this.id id;this.duration duration;this.dependencies dependencies;}}static class Graph {MapString, Task tasks;MapString, ListString adjList;MapString, Integer earliestStart;MapString, Integer earliestFinish;MapString, Integer latestStart;MapString, Integer latestFinish;MapString, Integer totalFloat;MapString, Integer freeFloat;Graph(ListTask taskList) {tasks new HashMap();adjList new HashMap();earliestStart new HashMap();earliestFinish new HashMap();latestStart new HashMap();latestFinish new HashMap();totalFloat new HashMap();freeFloat new HashMap();for (Task task : taskList) {tasks.put(task.id, task);adjList.put(task.id, new ArrayList());earliestStart.put(task.id, 0);earliestFinish.put(task.id, 0);latestStart.put(task.id, Integer.MAX_VALUE);latestFinish.put(task.id, Integer.MAX_VALUE);totalFloat.put(task.id, 0);freeFloat.put(task.id, 0);}}void addEdge(String from, String to) {adjList.get(from).add(to);}void calculateEarliestTimes() {for (String task : tasks.keySet()) {calculateEarliestTimes(task);}}int calculateEarliestTimes(String task) {if (earliestFinish.get(task) 0) {return earliestFinish.get(task);}int duration tasks.get(task).duration;int es 0;for (String dep : tasks.get(task).dependencies) {es Math.max(es, calculateEarliestTimes(dep));}earliestStart.put(task, es);earliestFinish.put(task, es duration);return earliestFinish.get(task);}void calculateLatestTimes() {int maxTime Collections.max(earliestFinish.values());for (String task : tasks.keySet()) {latestFinish.put(task, maxTime);}for (String task : tasks.keySet()) {calculateLatestTimes(task);}}int calculateLatestTimes(String task) {int duration tasks.get(task).duration;int lf latestFinish.get(task);for (String neighbor : adjList.get(task)) {lf Math.min(lf, calculateLatestTimes(neighbor) - duration);}latestStart.put(task, lf - duration);latestFinish.put(task, lf);return latestStart.get(task);}void calculateTotalAndFreeFloat() {for (String task : tasks.keySet()) {totalFloat.put(task, latestStart.get(task) - earliestStart.get(task));int minFreeFloat Integer.MAX_VALUE;for (String neighbor : adjList.get(task)) {minFreeFloat Math.min(minFreeFloat, earliestStart.get(neighbor) - earliestFinish.get(task));}freeFloat.put(task, minFreeFloat Integer.MAX_VALUE ? totalFloat.get(task) : minFreeFloat);}}ListString getCriticalPath() {ListString criticalPath new ArrayList();for (String task : tasks.keySet()) {if (totalFloat.get(task) 0) {criticalPath.add(task);}}return criticalPath;}}public static void main(String[] args) {ListTask tasks Arrays.asList(new Task(A, 3, Collections.emptyList()),new Task(B, 2, Arrays.asList(A)),new Task(C, 4, Arrays.asList(A)),new Task(D, 2, Arrays.asList(B)),new Task(E, 1, Arrays.asList(C)),new Task(F, 3, Arrays.asList(D, E)));Graph graph new Graph(tasks);graph.addEdge(A, B);graph.addEdge(A, C);graph.addEdge(B, D);graph.addEdge(C, E);graph.addEdge(D, F);graph.addEdge(E, F);graph.calculateEarliestTimes();graph.calculateLatestTimes();graph.calculateTotalAndFreeFloat();System.out.println(Earliest Start Times: graph.earliestStart);System.out.println(Earliest Finish Times: graph.earliestFinish);System.out.println(Latest Start Times: graph.latestStart);System.out.println(Latest Finish Times: graph.latestFinish);System.out.println(Total Float: graph.totalFloat);System.out.println(Free Float: graph.freeFloat);System.out.println(Critical Path: graph.getCriticalPath());}
}
