论文部分内容阅读
项目调度是广泛存在于实际项目管理中的一类典型调度问题,传统的研究思路为将其分拆为资源受限项目调度和工程项目工期-成本-质量多目标优化两类子问题。本文将上述两类子问题进行融合构成考虑资源约束的工程项目多目标均衡优化问题,从问题模型来讲,其为两个子问题的简单融合,但由于两个子问题之间存在多重耦合关系,其无法通过子问题优化算法的简单结合来解决,需要从宏观的角度进行模型分析并设计相应的算法。
本文对该问题的特点进行了深入研究,从模型构建、编码方式和算法设计等多方面进行了思考,提出了两种算法对问题进行求解,主要的工作如下:
首先,从模型构建的角度,本文基于相关假设和资源边际效用递减规律,提出活动工期-成本和工期-质量的非线性函数关系,对传统的线性关系进行了扩展,更好的描述了变量之间的关系。
其次,由于问题解涉及到活动工期和优先关系两个优化标的,单纯使用一维编码难以完全表示,为此本文提出了二维编码方式分别存储活动工期序列和优先级序列。对于优先级序列,本文在现有的任务链编码和优先级编码的基础上,提出了不考虑紧前约束的工序编码,与前两种编码方式不同的是,该编码方式由活动编码构成且隐含的排序为活动优先级,具有搜索空间小、无需考虑紧前关系约束的特点。由于问题模型为两类NP-hard问题的融合,决定了其具有较高的复杂性,为了进一步缩小搜索空间,设计了一个简单的压缩技术,将对虚活动的处理固化到算法中,并在编码中删除了首尾虚活动。
第三,本文详细阐述了资源约束对传统网络计划图的深层影响,资源约束只是对网络计划图中的部分活动进行了分解、增加了部分约束,并没有带来其他实质性的影响,传统网络计划图中的规律对其同样适用。针对传统的网络计划图和项目调度,设计了基于时差的局部优化策略,通过在时差范围内增加非关键活动的持续时间达到优化目的。
第四,在求解算法上,本文分别设计了基于分解的进化算法和文化基因算法(MEMETIC),在前者算法设计中通过目标值的归一化平衡了多个目标对最终适应度的影响,在后者的算法中设计了基于时差的局部优化算法,并将其与基于分解的进化算法在MEMETIC算法框架下进行了整合,提高算法的搜索效率。
最后对本文的主要工作和创新点进行了总结,并基于本文研究的不足,进一步阐述了项目调度未来的研究方向。