Capacitated production planning problems: Strong formulations, theorems and an optimization framework

Lot sizing investigates how to effectively allocate resources to produce different products and aims to find the most cost-efficient production plan. Effective solution of lot sizing problems is one of the most important determinants of cost performance in any production and inventory control system, which includes the well-known material requirements planning systems prevalent in manufacturing practice.;To effectively solve lot-sizing problems, this thesis proposes new strong mixed integer programming formulations, demonstrates the relationships among different formulations when the integrality requirement is relaxed for any subset of binary setup variables, shows the relative effectiveness of these formulations in obtaining lower bound solutions associated with linear programming relaxations. These research results are expected to provide significant guidelines on the selection of an effective formulation for the development of methodologies in which one of these formulations is needed.;This thesis also proposes a new partitioning and sampling based optimization framework, which is referred to as the lower and upper bound guided nested partitions framework. In this framework, exact methods are used to generate lower bound solutions, while heuristic methods are used to achieve feasible upper bound solutions. The optimization framework effectively utilizes both lower and upper bound solutions, and then provides an efficient partitioning and sampling strategy. Also, using the domain knowledge from the upper bound and lower bound solutions, the framework can efficiently find promising regions where good solutions are likely clustered from the entire solution region, and then focus computational effort on the most promising region of the solution space. The basic premise of the framework is that an efficient partitioning and sampling strategy can be achieved by combining domain knowledge from exact and heuristic methods to leverage the strengths of both of these approaches.;This thesis specifically implements the framework to solve capacitated multi-item lot sizing problems with setup times and capacitated multi-level lot sizing problems with backlogging. Computational results based on benchmark test problems show that the framework is computationally tractable and is able to obtain competitive results when compared with other state-of-the-art approaches.