An exact algorithm for minimizing resource availability costs in project scheduling

Autor(es)

Rodrigues, Savio B. ^[1] ; Yamashita, Denise S. ^[2]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 206, n. 3, p. 562-568, NOV 1 2010.
• Citações Web of Science: 28

Resumo

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)

• Processo FAPESP: 07/00209-6 - Métodos de solução para problemas de corte e empacotamento com restrições especiais
• Beneficiário: Denise Sato Yamashita
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado