Minimizing Earliness-Tardiness Costs of Resource-Constrained Projects
Minimizing Earliness-Tardiness Costs of Resource-Constrained Projects
复制标题
最大限度地降低资源有限项目的提前-延迟成本
DOI：
10.1007/978-3-642-58300-1_62
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
C. Schwindt
中科院分区：
文献类型：
--
作者：
C. Schwindt
我们考虑相互依赖的子项目的调度，这些子项目会招致提前或延迟完成的成本。具有里程碑意义。每个分项目由若干活动组成，在这些活动之间必须遵守从开始到开始的最小和最大时间间隔。此外，活动的处理占用了稀缺的共享资源。问题是确定一个符合时间约束的活动计划，使得资源需求可以与任何时间点的能力相匹配，并使项目的提前-拖期成本最小化。对于资源不受限的情况，我们分别提出了基于局部最优下降方向迭代计算的原始算法和基于局部最优上升方向迭代计算的对偶算法。将原始方法应用于资源松弛问题，确定了具有资源约束问题的初始(一般为资源不可行)调度。在分支定界算法中，通过枚举同时执行且其需求超过至少一个资源的能力的活动之间的优先约束集来解决资源冲突。在每个枚举结点，从父结点的调度开始，用对偶算法求解相应的松弛。
We consider the scheduling of interdependent subprojects incurring costs for early or tardy completion w.r.t. given milestones. Each subproject consists of several activities between which minimum and maximum start-to-start time lags have to be observed. In addition, the processing of activities takes up scarce shared resources. The problem is to determine an activity schedule complying with the temporal constraints such that the resource requirements can be matched by the capacities at any point in time and the earliness-tardiness costs of the project are minimized. For solving the resource-unconstrained version of this problem, we propose a primal and a dual algorithm which are based on the iterative calculation of locally optimal descent and ascent directions, respectively. An initial (generally resource-infeasible) schedule for the problem with resource constraints is determined by applying the primal method to the resource relaxation. Within a branch-and-bound algorithm, resource conflicts are resolved by enumerating sets of precedence constraints between activities which are executed simultaneously and whose requirements exceed the capacity of at least one resource. At each enumeration node, the corresponding relaxation is solved by the dual algorithm starting with the schedule of the father node.