An Exact Procedure for the Resource-Constrained Weighted Earliness–Tardiness Project Scheduling Problem
Vanhoucke, Mario Demeulemeester, Erik Herroelen, Willy
Vanhoucke, Mario
Demeulemeester, Erik
Herroelen, Willy
Citations
Altmetric:
Publication Type
Journal article with impact factor
Editor
Supervisor
Publication Year
2001-02
Journal
Annals of Operations Research
Book
Publication Volume
102
Publication Issue
1-4
Publication Begin page
179
Publication End page
196
Publication Number of pages
Collections
Abstract
In this paper we study the resource-constrained project scheduling problem with weighted earliness–tardinesss penalty costs. Project activities are assumed 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 finish–start precedence constraints and the constant renewable resource availability constraints. With these features the problem becomes highly attractive in just-in-time environments.We introduce a depth-first branch-and-bound algorithm which makes use of extra precedence relations to resolve resource conflicts and relies on a fast recursive search algorithm for the unconstrained weighted earliness–tardinesss problem to compute lower bounds. The procedure has been coded in Visual C++, version 4.0 under Windows NT. Both the recursive search algorithm and the branch-and-bound procedure have been validated on a randomly generated problem set.
Research Projects
Organizational Units
Journal Issue
Keywords
46 Information and Computing Sciences, 49 Mathematical Sciences, 35 Commerce, Management, Tourism and Services, 13 Climate Action