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