Constructive heuristics for project scheduling resource availability cost problem with tardiness

This work proposes a deterministic and a probabilistic constructive heuristic for solving the project scheduling resource availability cost problem with tardiness (RACPT), as well as a new mixed integer mathematical formulation with disjunctive constraints and time modeled as a continuous variable. Despite its practical relevance, solution methods to solve this problem are scarce in the literature. The proposed algorithms combine the flexibility of an activity with the flexibility of a resource to select the next activity to be scheduled. Several priority rules from the literature were tested, and the best heuristic was selected. The proposed heuristics' performances were compared with the mathematical formulation solved by an optimization software within a time limit, and the probabilistic constructive heuristic found optimal and near-optimal solutions for small instances. For medium and large instances, it obtained better results than the optimization model in about 20 times lower computational time. The heuristic was also compared with existing solution methods and was applied to a construction practical example, with good overall performance.