A solution approach of production planning problems based on compact formulations for single-item lot-sizing models
(2003)
Files
VanVyve.pdf
Restricted Access - Adobe PDF
- 7.04 MB
Details
- Authors
- Supervisors
- Abstract
- In the first part of the thesis, we investigate the complexity and the polyhedral structure of various extensions of the uncapacitated single-item lot-sizing problem. In particular, we study models involving fixed charges on stocks, constant capacity and backlogging, and lower bounds on production. We describe algorithms, extended formulations, (facet-defining) valid inequalities and separation algorithms. Emphasis is placed on compact (i.e. of polynomial size) exact extended formulations. In a second part, we show how such extended reformulations for single-item problems can help to improve the solution of much more general production planning problems. We first study the single-item uncapacitated lot-sizing problem with fixed charges on stocks. This problem arises naturally in a production environnement where stocking is a complex operation. We show how to solve this problem in $O(n \log n)$ time. We present various exact extended formulations, including a shortest path and a multicommodity reformulation. We also give a description of the convex hull of the solutions of this problem in the original space of variables. The proof is based on a projection of the multicommodity formulation. Finally we show how these results simplify when the costs satisfy the Wagner-Within property. Then, we consider the complexity of lot-sizing problems in which the batch size is finite and constant over time. The main result is to provide an $O(n^3)$ algorithm for the single- item constant-capacity lot-sizing problem with backlogging and a general capacity, i.e. in each time period $t$, we may install up to $m_t$ multiples of the batch capacity, where the $m_t$ are given and are time-dependent. This generalizes earlier results \cite{LS:PW:93,LS:HW:96} as we consider backlogging and a general number of installable batches. We also give faster algorithms for special cases of this general problem. We then consider tight formulations for the constant capacity lot-sizing problem with backlogging. A first formulation applies to the problem with a general cost function and has $O(n^3)$ variables and constraints. The second one, which is exact only when the costs satisfy the Wagner-Whitin property, has only $O(n^2)$ variables and $O(n^3)$ constraints. Finally, we study variable lower bounds on production. In this problem, the production in each period is required to be zero or higher than some specified value $L$. We first study the polyhedral structure of an extension of the mixing set in which two divisible capacities are allowed. We provide an exact extended formulation of size $O(n^2) \times O(n^2)$, the description of the convex hull by linear inequalities and an $O(n \log n)$ separation algorithm. This extension of the mixing set is a relaxation of the lot-sizing problem with divisible constant capacity and constant lower bound. We investigate in which cases the polyhedral structure of the mixing set (i.e. the relaxation) differs from that of the lot-sizing problem. In the second part of the thesis, the focus is on solving production planning problems. Adding strong extended formulations is a theoretical alternative to cutting planes when improving mixed-integer production-planning models. The expected advantage is the simplicity of the approach. The main obstacle is the size of the formulations: even $O(n^2)$ variables and constraints is usually too large for real-sized problems. However, we show that the formulation of single-item problems can be improved by adding only a fraction of the extended variables and constraints. We call these approximate extended formulations. Our description involves a single control parameter $T_k$, which controls the tradeoff between the size and the strength of the approximate formulation. We also show how this approach extendeds to other combinatorial problems, such as the travelling salesman problem. We implement the addition of approximate formulations as procedures written in the modelling language XPRESS-Mosel. This makes the tightening a given model by extended formulations both simple and flexible. We then propose a general solution approach to production planning problems in three steps. First the problem is analyzed to identify single-item lot-sizing relaxations. Then the formulation is improved by adding approximate extended formulations. Finally, the resulting MIP is optimized using an off-the-shelve solver. We demonstrate that various academic and industrial multi-item multi-machine multi-level production planning problems can be tackled surprisingly well using this simple approach.
- Affiliations
Citations
Van Vyve, M. (2003). A solution approach of production planning problems based on compact formulations for single-item lot-sizing models. https://hdl.handle.net/2078.5/251721