资源受限条件下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.5 N 元行偶的顺序优化方法
• 第五章 带任意个松弛量的 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 算法的时间复杂性分析
• 第六章 结论
• 参考文献
• 致谢
• 在学期间发表的学术论文和参加科研情况