基于优先规则的活动成本目标资源受限工程调度

Priority-rule-based Resource-Constrained Project Scheduling with the Objective of Minimizing Activities' Cost

首先给出了该问题的数学模型,问题分析得出该问题也是一类NP完全问题,继而讨论了启发式方法进行问题求解的基本思想,基于此,结合活动成本目标的特性提出了问题求解的串行调度方案和并行调度方案,并设计了相应的几种优先规则,分析了算法的时间复杂性.基于改造PSPLIB中的单模式算例测试,并行调度方案的结果大多优于串行调度方案,而在最大最早完成时间和最大活动先序相关成本等两种优先规则下的调度方法计算效果相对较好.

Resource-Constrained Project Scheduling Problem（RCPSP） is a key sub-problem in partner selection of construction supply chain. Its mathematic model is presented firstly, and analysis on the characteristic of the problem shows that the problem is NP-eomplete following which the basic idea for solution is clarified. Based on this, Serial Scheduling Schema（SSS） and Parallel Scheduling Schema（PSS） are proposed, and some priority rules are designed. The time complexity of the algorithms is also analyzed. Computational Study with the single-mode instances in updated PSPLIB shows that the results of PSS are generally better than those of SSS and the efficiency of the two schemas will become better when maximal earliest finish time or maximal transitive relative cost of feasible activities is used as priority rule.