资源受限条件下N元行偶顺序优化的理论与方法研究

摘要

资源限制项目排序问题是项目管理的核心内容。现有的解析法和启发式算法在解决该类问题时存在明显缺陷，如计算量大、难以达到最优、缺少普适性等。为了设计出能克服上述缺陷的新算法，先在假设资源无限时做“理想网络计划”，再根据实际资源限制把“理想网络计划”中的平行工序调整为顺序工序，从而使项目排序问题分解为多个平行工序顺序优化的子问题，减小了工作的难度。 本文研究其中一类子问题--将L个平行工序中的2N个调整为N对顺序工序。利用CPM网络自身的特点和机动时间规律，在考虑前、后继工序约束条件下，设计出带松弛量的N元行偶顺序优化算法，并分析算法的时间复杂性。该子问题的解决为资源限制项目排序问题的彻底解决奠定了基础。

目录

文摘

英文文摘

声明

第一章 引言

1.1选题背景及其意义

1.2国内外研究动态

1.3本文的主要研究内容及方法

第二章 时间参数和基本概念

2.1时间参数

2.1.1节点时间参数及其计算方法

2.1.2工序时间参数及其计算方法

2.2基本概念

第三章 基本定理

3.1引理

3.1.1序偶亏值定理

3.1.2行偶亏值定理

3.1.3重心定理

3.2新定理

3.2.1规范行偶定理

3.2.2标准行偶定理

3.2.3含有单个最大亏值的行偶可优化调整的判定定理

3.2.4差量定理

第四章 N元行偶的顺序优化

4.1含有单个最大亏值序偶的规范行偶的优化调整模型

4.1.1含有单个最大亏值序偶的规范行偶优化调整的基本原则

4.1.2模型基本参数

4.1.3必能使规范行偶优化的模型

4.1.4可能使规范行偶优化的模型

4.2只含有两个相邻最大亏值序偶的规范行偶的优化调整模型

4.2.1只含有两个相邻最大亏值序偶的规范行偶优化调整的基本原则

4.2.2模型基本参数

4.2.3必能使规范行偶优化的模型

4.2.4可能使规范行偶优化的模型

4.3含有两个及其以上最大亏值序偶的规范行偶的一般优化调整模型

4.3.1含有两个及其以上最大亏值序偶的规范行偶优化调整的基本原则

4.3.2规范行偶调整的初始模型

4.3.3初始调整后的二度优化调整模型

4.4含有两个及其以上最大亏值序偶的规范行偶的特殊优化调整模型

4.4.1模型的基本形式

4.4.2该规范行偶可优化的判别原则——因子数原则

4.4.3优化调整步骤

4.5N元行偶的顺序优化方法

第五章 带任意个松弛量的N元行偶顺序优化

5.1带任意个松弛量的N元行偶顺序优化的基本原则

5.2构造初始最佳N元行偶

5.3含有单个最大亏值序偶的初始最佳N元行偶的优化调整

5.3.1所需基本参数

5.3.2用行偶松弛量代替初始最佳N元行偶工序的优化步骤

5.4含有两个及其以上最大亏值序偶的初始最佳N元行偶的优化调整

5.4.1所需基本参数

5.4.2用行偶松弛量代替初始最佳N元行偶工序的优化步骤

5.5带任意个松弛量的N元行偶顺序优化

5.6算法的时间复杂性分析

第六章结论

参考文献

致谢