Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

An exact algorithm for minimizing resource availability costs in project scheduling

Full text
Author(s):
Rodrigues, Savio B. [1] ; Yamashita, Denise S. [2]
Total Authors: 2
Affiliation:
[1] Univ Fed Sao Carlos, Dept Math, BR-13565905 Sao Carlos, SP - Brazil
[2] Univ Fed Sao Carlos, Dept Prod Engn, BR-13565905 Sao Carlos, SP - Brazil
Total Affiliations: 2
Document type: Journal article
Source: European Journal of Operational Research; v. 206, n. 3, p. 562-568, NOV 1 2010.
Web of Science Citations: 28
Abstract

A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available. (C) 2010 Elsevier B.V. All rights reserved. (AU)