Minimizing Total Resource Tardiness Penalty Costs in the Resource Constrained Project Scheduling Problem with Metaheuristic Algorithms

Abstract

In this paper, we study a resource-constrained project-scheduling problem in which the objective is minimizing total Resource Tardiness Penalty Costs. We assume renewable resources that are limited in number, are restricted to very expensive equipment and machines, therefore they are rented and used in other projects, and are not available in all project periods. In other words, there exists a predefined ready-date as well as a due date for each renewable resource type. In this way, no resource is utilized before its ready date. Nevertheless, resources are allowed to be used after their due date by paying penalty costs depending on the resource type. The objective is to minimize the costs of renewable resource usages. We formulated and mathematically modeled this problem as an integer-Linear programming model. Since our problem is NP-hard and also exact methods are only applicable in small scale, therefore metaheuristic methods are practical approaches for this problem; this means that metaheuristics are better for this problem. In order to authenticate the model and solution algorithm in small scale, we consider a network with low activity, and then solve the model of this network with both exact algorithms and SA-GA-TS metaheuristic algorithms. For more activities, as well as getting closer to the real world, we present a Simulated Annealing Algorithm to solve this problem. In order to examine the performance of this algorithm, data that had been derived from studied literature were used, and their answers were compared with Genetic Algorithm (GA) and Tabu Search Algorithm (TS). Results show that in average, quality of SA answers was better than those of the GA and TS algorithms. In addition, we use relaxation method to achieve an even higher validation for the SA algorithm. Finally all results in this paper indicate that both model and solution algorithm have high validity.