The paper is devoted to a cosmonaut training planning problem, which is some kind of resource-constrained project scheduling problem (RCPSP) with a new goal function. Training of each cosmonaut is divided into special courses. To avoid too sparse courses, we introduce a special objective function—the weighted total sparsity of training courses. This non-regular objective function requires the development of new methods that differ from methods for solving the thoroughly studied RCPSP with the makespan criterion. New heuristic algorithms for solving this problem are proposed. Their efficiency is verified on real-life data. In a reasonable time, the algorithms let us find a solution that is better than the solution found with the help of the solver CPLEX CP Optimizer.