The cosmonauts training planning problem is a problem of construc- tion of cosmonauts training timetable. Each cosmonaut has his own set of tasks which should be performed with respect to resource and time con- straints. The problem is to determine start moments for all considered tasks. This problem is a generalization of the resource-constrained project scheduling problem with “time windows”. In addition, the investigated problem is extended with restrictions of different kinds. Previously, for solving this problem the authors proposed an approach based on methods of integer linear programming. However, this approach turned out to be ineffective for high-dimensional problems. A new heuristic method based on constraint programming is developed. The effectiveness of the method is verified on real data.