Generation schemes for the resource-constrained project scheduling problem with partially renewable resources and generalized precedence constraints
研究了带有部分可再生资源和广义优先约束的项目调度问题，目标是缩短工期，并提出了两种快速生成可行解的方案：基于构造的启发式和基于松弛的生成方案。
Abstract In recent years, new resource types have been established in project scheduling. These include so-called partially renewable resources, whose total capacity applies only to a subset of periods in the planning horizon. In this paper, we consider the extension of the resource-constrained project scheduling problem with those partially renewable resources as well as generalized precedence constraints with the objective of minimizing the project duration (RCPSP/max- $$\pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>π</mml:mi> </mml:math> ). For this problem it is known that already the determination of a feasible solution is NP-hard in the strong sense. Hence, we present two different generation schemes that are able to find good feasible solutions in short time for most tested instances. The first one is a construction-based heuristic wherein the activities of the project are scheduled iteratively time- and resource-feasibly. The second one is a relaxation-based generation scheme, in which—starting from the schedule consisting of the earliest start times—resource conflicts are identified and resolved by inserting additional resource constraints.