The paper proposes to manage complexity and cost issues of the fault-tolerant programs not at a single program level, but rather from the point of view of the whole set of such programs, which are to be run under time constraints. The paper introduces a family of scheduling problems called fault-tolerant programs scheduling. Since, the discussed problems are, in general, computationally difficult, a challenge is to find effective scheduling procedures. Several evolution-based algorithms solving three basic kinds of fault-tolerant programs scheduling problems have been proposed. The problems involve scheduling multiple variant or multiple processor tasks on multiple, identical processors, under time constraints. To validate the algorithms computational experiment has been conducted. Experimental results show that evolution based algorithms produce satisfactory to good solutions in a reasonable time.