Abstract
Production planning in manufacturing industries is concerned with the determination of the production quantities (lot sizes) of some items over a time horizon, in order to satisfy the demand with minimum cost, subject to some production constraints.
In general, production planning problems become harder when different types of constraints are present, such as capacity constraints, minimum lot sizes, changeover times, among others. Models incorporating some of these constraints yield, in general, NP-hard problems.
We consider a single-machine, multi-item lot-sizing problem, with those difficult characteristics. There is a natural mixed integer programming formulation for this problem. However, the bounds given by linear relaxation are in general weak, so solving this problem by LP based branch and bound is inefficient. In order to improve the LP bounds, we strengthen the formulation by adding cutting planes. Several families of valid inequalities for the set of feasible solutions are derived, and the corresponding separation problems are addressed. The result is a branch and cut algorithm, which is able to solve some real life instances with 5 items and up to 36 periods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Aggarwal and J. Park, Improved algorithms for economic lot size problems, Operations Research 41 (1993) 549–571.
I. Barany, T.J. Van Roy and L.A. Wolsey, Strong formulations for multi-item capacitated lot sizing, Management Science 30 (1984) 1255–1261.
I. Barany, T.J. Van Roy and L.A. Wolsey, Uncapacitated lot sizing: the convex hull of solutions, Mathematical Programming Study 22 (1984) 32–43.
M. Constantino, A polyhedral approach to production planning models: start-up costs and times, upper and lower bounds on production, Ph.D. Dissertation, Universit´e Catholique de Louvain, Belgium (1995).
M. Constantino, Valid inequalities for lot-sizing with start-up costs and times, upper and lower bounds on production, Working Paper, Centro de Investigaca¸ã Operacional, University of Lisbon, Portugal (1996).
M. Constantino, A cutting plane approach to capacitated lot-sizing with start-up costs, Mathematical Programming 75 (1996) 353–376.
CPLEX Optimization, Inc., Using the CPLEX Callable Library and CPLEX Mixed Integer Library (Incline Village, NV, USA, 1994).
C.A. van Eijl, A polyhedral approach to the discrete lot-sizing and scheduling problem, Ph.D.Dissertation, Technische Universiteit Eindhoven, The Netherlands (1996).
A. Federgruen and M. Tzur, A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(nlog n) or O(n) time, Management Science 37 (1991) 909–925.
C.P.M. van Hoesel and A.W.J. Kolen, A Linear description of the discrete lot-sizing and scheduling problem, European Journal of Operational Research 75 (1994) 342–353.
C.P.M. van Hoesel, A.P.M. Wagelmans and L.A. Wolsey, Polyhedral characterization of the economic lot-sizing problem with start-up costs, SIAM Journal of Discrete Mathematics 7 (1994) 141–151.
J. Leung, T.M. Magnanti and R. Vachani, Facets and algorithms for capacitated lot-sizing, Mathematical Programming 45 (1989) 331–359.
T.M. Magnanti and R. Vachani, A strong cutting plane algorithm for production scheduling with changeover costs, Operations Research 38 (1990) 456–473.
G.L. Nemhauser and M.W.P. Savelsbergh, MINTO, a Mixed INTeger Optimizer, Operations Research Letters 15 (1994) 47–58.
M.W. Padberg and G. Rinaldi, A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review 33 (1991) 60–100.
Y. Pochet, Valid inequalities and separation for capacitated economic lot-sizing, Operations Research Letters 7 (1988) 109–116.
Y. Pochet and L.A. Wolsey, Lot-size models with backlogging: strong reformulation and cutting planes, Mathematical Programming 40 (1988) 317–335.
Y. Pochet and L.A. Wolsey, Solving multi-item lot-sizing problems using strong cutting planes, Management Science 37 (1991) 53–67.
Y. Pochet and L.A. Wolsey, Lot-sizing with constant batches: formulation and valid inequalities, Mathematics of Operations Research 18 (1993) 767–785.
Y. Pochet and L.A. Wolsey, Polyhedra for lot-sizing with Wagner-Whitin costs, Mathematical Programming 67 (1994) 297–323.
Y. Pochet and L.A. Wolsey, Algorithms and reformulations for lot sizing problems, in: Combinatorial Optimization, eds. W. Cook et al., DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20 (1995) 245–293.
A.P.M. Wagelmans, C.P.M. van Hoesel and A.W.J. Kolen, Economic lot-sizing: an O(n log n) algorithm that runs in linear time in the Wagner-Whitin case, Operations Research 40 (1992) 145–156.
H.M. Wagner and T.M. Whitin, Dynamic version of the economic lot size model, Management Science 5 (1958) 89–96.
L.A. Wolsey, Uncapacitated lot-sizing problems with start-up costs, Mathematics of Operations Research 18 (1989) 767–785.
Rights and permissions
About this article
Cite this article
Constantino, M. A polyhedral approach to a production planning problem. Annals of Operations Research 96, 75–95 (2000). https://doi.org/10.1023/A:1018963805173
Issue Date:
DOI: https://doi.org/10.1023/A:1018963805173