An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem

In this paper we study the resource-constrained project scheduling problem with weighted earliness-tardinesss penalty costs. Project activities are as sumed to have a known deterministic due date, a unit earliness as well as a unit tardiness penalty cost and constant renewable resource requirements. The objective is to schedule the activities in order to minimize the total weighted earliness-tardinesss penalty cost of the project subject to the fi nish-start precedence constraints and the constant renewable resource avail ability constraints. With these features the problem becomes highly attract ive in just-in-time environments. We introduce a depth-first branch-and-bound algorithm which makes use of ex tra precedence relations to resolve resource conflicts and relies on a fast recursive search algorithm for the unconstrained weighted earliness-tardin esss problem to compute lower bounds. The procedure has been coded in Visua l C++, version 4.0 under Windows NT. Both the recursive search algorithm an d the branch-and-bound procedure have been validated on a randomly generate d problem set.