Groupe d’études et de recherche en analyse des décisions

Mathematical models, theorems and optimization frameworks for solving capacitated lot-sizing problems

Tao Wu Apollo Education Group Inc., États-Unis

Often faced in practical production planning settings, capacitated lot sizing problems aim to schedule production for a number of items over a finite time horizon, while minimizing total cost and ultimately meeting all customer demands. The total relevant costs generally include setup costs and inventory holding costs. The output consists of the setup periods and the time-phased production and inventory for all items over the planning horizon. Effective solution of these problems is one of the most important determinants of cost performance in any dependent-demand production and inventory control system, which includes the well-known material requirements planning systems prevalent in manufacturing practice. Research on strong mathematical models, theorems, and solution methods that facilitate more efficient solution of problems thus has the potential to provide tangible benefits to practitioners.

To effectively solve lot sizing problems, we propose strong mixed integer programming formulations as well as a two-period convex hull closure for big bucket lot sizing problems. We propose a methodology that can approximate the intersection of the convex hulls of all such possible two-period submodels by generating violated valid inequalities. To generate such inequalities, we exactly separate fractional points from a dynamically generated representation of the convex hull of extreme points of each two-period submodel. We also demonstrate the relationships among different formulations when the integrality requirement is relaxed for any subset of binary setup variables. 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.

In addition, we propose 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 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. 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.