In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity. The objective function is the minimization of the project completion time. Heuristics based on priority rule are considered as initial solution procedures for this problem. The proposed Taboo search algorithm (TSA) is computationally compared, the results are analyzed and discussed, and some conclusions are given. Results obtained on six classes of test problems and comparison with other algorithms from the literature show that our algorithm gives better solutions.