关键路径的求解与可视化显示.PDF

[课程设计题一] 关键路径的求解与可视化显示 [问题描述] 施工过程或生产流程一类的工程项 目，其进展过程和子项 目之间的制约关系可以通过 “活动网络”（AOE ）加以研究。顶点描述所要发生的事件，带权的有向弧描述工程必须要 进行的施工活动。通过关键路径的算法，可以求得一项工程的“关键路径”，投入资源于 关键路径，加快该路径上活动的施工效率，将提前整个工程的完工期限。一 AOE 网及所求 的关键路径安排示例，见下图所示。 还应注意，在实际的工程问题中，事件之间存在无须安排消耗资源的活动，但事件之 间需要依据一定的 “次序关系”，称为“虚活动”。例如装修工程中，需在 “油漆涂刷” 之后才 “安装金属配饰”。这种现象对应的活动以虚线标出，见下图。 [基本要求] 通过图形界面，输入 AOE 网的弧（i, j, duration ），及顶点所对应的事件名称（i, event）。 所求的活动安排由工程进度表的形式输出，关键路径以特殊颜色的闪烁方式提示，给出总 工期，并能提供进一步的工程改进方案建议。 [测试数据] 以说明的插图示例，对顶点及活动命名，作为基本的测试数据。下一步，同学可对建 筑施工和房屋装修的实际问题进行调研，以解决一个有实际背景的工程项目安排问题。AOE 网的顶点数一般应大于20 。 [实现提示] 该题目的主要数据结构及算法已有成熟的资料可供借鉴，主要工作是工程进度表的人 性化图形输出、交互操作，并能提供施工改进意见的解决方案。 实际的真实问题可能会涉及到“虚活动”，尽管虚活动不消耗物资资源，但可能要产 生时滞现象，例如等待油漆的干燥、水泥的凝固等等。 最终的图形界面建议如下，如有多个解或图形较大可考虑使用滚动条。 [问题讨论] 实际问题比书本的简单模型要复杂得多，例如关键路径可能不止一个，需要安排虚活 动，提供改进方案和成本核算的投资建议等等。 在做改进方案时，如能直接在屏幕上进行交互式的输入和编辑，将会更符合现场的使 用。