"关键活动软件开发环境下工程项目任务调度与最短时间计算"

山东大学计算机科学与技术学院《数据结构与算法》课程设计报告 学号：201700301147 姓名：杜瀛川 班级：17.4 上机学时：4 日期：2019.3.25 课程设计题目：关键活动软件开发环境：Qt Creater 项目最终效果图 报告内容： 1. 需求描述 1.1 问题描述 一个工程项目一般有一些子任务（活动）构成，子任务之间有的可以并行执行，有的则必须在完成了其它一些任务后才能执行。如果给出了完成每个任务需要的时间，则可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天，也不会影响全局的工期，但是有些任务必须准时完成，否则整个工程项目就要因此延误，这种任务就称为“关键活动”。 1.2 基本要求 判断一个工程项目的任务调度是否可行，如果可行，则计算出完成整个工程需要的最短时间，输出所有的关键活动，各项活动的最早开始时间，以及不影响全局工期的最晚开始时间。 1.3 输入说明 1.3.1 初始化 用户点击窗口中的初始化选项，进行AOE网络初始化，会弹出提示对话框，提示用户将要输入信息的格式。需要输入任意行，每行包含三个数字，分别是起始事件、终止事件、耗费事件。之后会打开输入对话框，用户输入相关信息。 2. 算法设计 2.1 图的表示 采用邻接矩阵表示图，其中矩阵matrix[i][j]=1表示i事件到j事件有一条直接路径。 2.2 初始化 根据用户输入的信息生成邻接矩阵，同时计算出每个事件的入度，存入in[]数组。 2.3 关键路径分析 采用拓扑排序和动态规划的方法，计算每个事件的最早发生时间ve(i)和最晚发生时间vl(i)。其中ve(i)表示从源点到i事件的最长路径长度，vl(i)表示从i事件到汇点的最长路径长度。同时，根据最早发生时间和最晚发生时间计算出关键活动。 3. 算法实现 3.1 初始化 根据用户输入的信息，生成邻接矩阵，并统计每个事件的入度。 3.2 拓扑排序 采用深度优先搜索的方法进行拓扑排序，在排序过程中计算每个事件的最早发生时间ve(i)。 3.3 动态规划 使用动态规划的思想计算每个事件的最晚发生时间vl(i)，并根据最早发生时间和最晚发生时间计算出关键活动。 4. 实验结果 通过对不同工程项目进行测试，验证了算法的正确性。输出结果包括完成整个工程需要的最短时间，所有的关键活动，以及各项活动的最早开始时间和不影响全局工期的最晚开始时间。 5. 结论 本课程设计实现了一个关键活动软件，可用于判断工程项目的任务调度是否可行，并计算出完成整个工程需要的最短时间，输出所有的关键活动，各项活动的最早开始时间，以及不影响全局工期的最晚开始时间。 总结： 本次课程设计通过采用邻接矩阵表示图，拓扑排序和动态规划的算法，实现了一个关键活动软件，能够准确计算工程项目的最短时间和关键活动。通过对不同工程项目的测试，验证了算法的正确性和可行性。该软件对于工程项目的管理和调度有着重要的意义。