论文部分内容阅读
项目调度是计算机应用的重要领域。项目调度一般使用有向无环图表示，由于有向无环图能够很好地表示出项目调度中任务的持续时间、任务间的偏序关系以及任务间的延迟时间，利用有向无环图还可以验证各种调度算法的正确性和可行性，因此根据各种输入参数正确的生成有向无环图是项目调度领域的重要研究内容。本文主要研究了AOA网归约复杂度的概念和基于归约复杂度生成AOA网的方法。重点内容为：
1.根据AON网和AOA网的结点和弧之间不同的概念，提出了AON网转换成为AOA网的方法。转换后的AOA网不存在虚结点并具有最小的归约复杂度。
2.提出了两种AOA网归约复杂度的计算方法，分别是定义法和复杂图最小结点覆盖法。相比于定义法，复杂图最小结点覆盖法减少了归约复杂度计算的时间复杂度。
3.提出并实现了有向无环图生成的两种方法：方法一是根据任务数和结点最大出度生成有向无环图；方法二是根据给定的归约复杂度生成AOA网，这种方法是由最小结点覆盖的逆过程推导得出的。
4.设计并实现了原型系统，并从功能和效率两方面对其进行测试。同时通过建立项目调度实例库来存储大量实例，以便研究调度算法时使用。