TY - JOUR

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

AU - Ranjbar, Mohammad

AU - Khalilzadeh, Mohammad

AU - Kianfar, Fereydoon

AU - Etminani, Kobra

PY - 2012/2

Y1 - 2012/2

N2 - 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.

AB - 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.

KW - Branch-and-bound

KW - Resource-constrained project scheduling

KW - Weighted tardiness

UR - http://www.scopus.com/inward/record.url?scp=82755177956&partnerID=8YFLogxK

U2 - 10.1016/j.cie.2011.09.013

DO - 10.1016/j.cie.2011.09.013

M3 - Article

AN - SCOPUS:82755177956

SN - 0360-8352

VL - 62

SP - 264

EP - 270

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

IS - 1

ER -