An optimal procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem

摘要

We present an optimal solution procedure for minimizing total weighted resource tardiness penalty costs in the resource-constrained project scheduling problem. In this problem, we assume the constrained renewable resources are limited to very expensive equipments and machines that are used in other projects and are not available in all periods of time of a project. In other words, for each resource, there is a dictated ready date as well as a due date such that no resource can be available before its ready date but the resources are permitted to be used after their due dates by paying penalty cost depending on the resource type. We also assume that only one unit of each resource type is available and no activity needs more than it for execution. The objective is to determine a schedule with minimal total weighted resource tardiness penalty costs. For this purpose, we present a branch-and-bound algorithm in which the branching scheme starts from a graph representing a set of conjunctions (the classical finish-start precedence constraints) and disjunctions (introduced by the resource constraints). In the search tree, each node is branched to two child nodes based on the two opposite directions of each undirected arc of disjunctions. Selection sequence of undirected arcs in the search tree affects the performance of the algorithm. Hence, we developed different rules for this issue and compare the performance of the algorithm under these rules using a randomly generated benchmark problem set.