Although several mixed-integer programming (MIP) models have been proposed for the scheduling of chemical manufacturing facilities, the development of solution methods for these formulations has received limited attention. In this article, we develop a constraint propagation algorithm for the calculation of lower bounds on the number and size of tasks necessary to satisfy given demand. These bounds are then used to express four types of valid inequalities which greatly enhance the computational performance of the MIP scheduling model. Specifically, the addition of these inequalities leads to reductions in the computational requirements of more than three orders of magnitude, thereby allowing us to address medium-sized problems of industrial relevance. Importantly, the proposed methods are applicable to a wide range of problem classes and time-indexed MIP models for chemical production scheduling. (C) 2013 American Institute of Chemical Engineers AIChE J, 59: 872-887, 2013