时间－费用权衡问题中超大型网络化简的理论与方法

论文摘要

对时间-费用权衡问题的研究始于上世纪六十年代初,并且所涉及的范围在随后的几十年中大为扩展,但在问题的解决上却一直未取得突破性进展,最主要的瓶颈就是解决该类问题时所遇到的高复杂度和大计算量。为了消除该瓶颈,本论文采用新的思路,通过简化问题所涉及的计算对象来降低求解时所面临的高复杂度和大计算量,而不是去设计或改进解决问题的算法。本论文用关键路线法（Critical Path Method,简称为CPM）网络计划技术作为工具,在机动时间特性研究的基础上,把超大型工序网络化简为等效的简单网络,从而使不可计算的问题转化为可计算的问题,使很复杂的问题转化为比较简单的问题,尤其是利用化简后的网络求解时间-费用权衡问题,无论使用任何一种算法其计算量都会大大减小。因此,本论文的研究不仅具有重要的理论意义,而且具有极大的实用价值。本论文研究的主要内容如下:1.本论文在前人对同一工序机动时间关系和相邻工序机动时间关系研究的基础上,利用机动时间的新概念首次研究了一个工序使用机动时间对其它工序的影响,构建了一个工序使用机动时间与其它工序机动时间减少量之间相互关系的数学模型。通过这个模型又进一步研究了一个工序使用机动时间所造成的影响范围,以及哪些工序在其它工序使用机动时间时自身机动时间始终保持不变的规律性。2.本论文研究了前单时差和后单时差在一条路线上的分布规律,并利用该结论设计了求k阶次关键路线的方法。3.本论文首次创设了时间-费用权衡问题中超大型网络的等效化简方法。主要包括:1)寻找路线的方法,即通过寻找原网络中所必需考虑的较长路线构建等效子网络;该方法建立在寻找k阶次关键路线的方法研究基础上。2)删减路线的方法,即通过删减原网络中无需考虑的较短路线构建等效子网络。上述方法均利用了机动时间与路长的关系定理,包括总时差定理、节点时差定理、后单时差定理和前单时差定理等。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 选题背景及意义
• 1.2 时间-费用权衡问题的国内外研究现状
• 1.3 本论文研究的主要内容
• 第二章 基本概念
• 2.1 时间参数概念
• 2.1.1 节点时间参数概念
• 2.1.2 工序时间参数概念
• 2.2 机动时间概念
• 2.2.1 机动时间传统概念
• 2.2.2 机动时间新概念
• 2.3 小结
• 第三章 工序机动时间之间的关系
• 3.1 同一工序机动时间之间的关系
• 3.1.1 同一工序前共用时差和前单时差之间的关系
• 3.1.2 同一工序后共用时差和后单时差之间的关系
• 3.2 相邻工序机动时间之间的关系
• 3.3 不相邻工序机动时间之间的关系——传递性与稳定性的新探索
• 3.3.1 对工序机动时间传递性的新探索
• 3.3.2 对工序机动时间稳定性的新探索
• 3.4 小结
• 第四章 机动时间与路长之间的关联规律
• 4.1 后单时差的特性
• 4.2 前单时差的特性
• 4.3 总时差的特性
• 4.4 节点时差的特性
• 4.5 小结
• 第五章 时间-费用权衡问题中超大型网络化简的新理论和新方法
• 5.1 求k阶次关键路线的新方法
• 5.1.1 求k阶次关键路线的后单时差法
• 5.1.2 求k阶次关键路线的前单时差法
• 5.1.3 应用举例
• 5.2 构建等效子网络的新方法
• 5.2.1 构建等效子网络的前单时差法
• 5.2.2 构建等效子网络的后单时差法
• 5.2.3 构建等效子网络的总时差-节点时差法
• 5.2.4 等效子网络的扩展研究
• 5.2.5 应用举例
• 5.3 小结
• 第六章 结论与展望
• 6.1 主要结论及创新点
• 6.2 未来研究展望
• 参考文献
• 致谢
• 攻读博士学位期间发表的学术论文
• 攻读博士学位期间参加的科研工作