An engineered evolutionary algorithm for a realistic chemical batch scheduling problem with uncertain data is developed systematically. The problem is formulated as a two stage stochastic integer program with discrete scenarios. The model is solved by a stage decomposition-based hybrid algorithm using in evolutionary algorithm combined with mixed-integer programming. Earlier experiments with a standard evolutionary algorithm led to the hypothesis that the constrained search space is not covered well such that in some cases the population converges to a subset of the solution space which does not include the best known solution. An efficient engineered evolutionary algorithm is developed which is shown to cover the feasible set significantly better such that a high quality feasible schedule can be generated comparatively fast. As the hierarchical structure of the case study is typical for many batch scheduling problems, some general principles may be postulated from the experience gained here. (c) 2007 Elsevier Ltd. All rights reserved.