The nascent field of Genetic Algorithms (GA's), and a set of tough scheduling problems provide the focus for this research. The job-shop scheduling problem, a real-world scheduling problem and a multi-objective permutation flow-shop problem are dealt with, and the following new results are obtained. * A new selection procedure for genetic algorithms capable of keeping a diverse population through the generations is proposed. The method is based on a random sampling of individuals and partial enumeration of neighboring solutions. An intensive selection procedure, applied after the partial enumeration, and the elitist strategy are fundamental elements for introducing selection pressure in the algorithm. The idea of using random sampling comes from the basic statistics concept saying that an adequate sample set of individuals would have the representative properties of the whole population. The partial enumeration is used as a properties-discovering procedure of the sampled individuals. The relative robustness of this algorithm applied to the job-shop (the central problem for this research) is compared against a standard GA and the advantages of the proposed algorithm are highlighted. * It is shown through numerical experiments that the success in the design of robust algorithms is based on a tight combination of accuracy and diversity. * For the real-world scheduling, operating in the job-shop mode, a new decoding technique is proposed. This decoding technique is a part of the genotype, introducing in this way a problem specific knowledge in the individual representation. A comparable accuracy result in a short computing time is achieved by means of the proposed method. * In case of the multi-objective permutation flow-shop problem, an analysis of operators is proposed in such a way that it becomes a natural extension of the landscape study already known for single-objective problems. This analysis shows that a design procedure following our ideas outperforms substantially previous existing procedures for the same multi-objective permutation flow-shop problem.