Consider a project consisting of a set of n operations to be performed. Some pairs {j,j′} of operations are incompatible, which can have two different meanings. On the one hand, it can be allowed to perform j and j′ at common time periods. In such a case, incompatibility costs are encountered and penalized in the objective function. On the other hand, it can be strictly forbidden to perform j and j′ concurrently. In such a case, the overall project duration has to be minimized. In this paper, three project scheduling problems (P 1), (P 2) and (P 3) are considered. It will be showed that tabu search relying on graph coloring models is a very competitive method for such problems. The overall approach is called graph coloring tabu search and denoted GCTS.