Abstract
We consider a multi-item lot-sizing problem with joint set-up costs and constant capacities. Apart from the usual per unit production and storage costs for each item, a set-up cost is incurred for each batch of production, where a batch consists of up to C units of any mix of the items. In addition, an upper bound on the number of batches may be imposed. Under widely applicable conditions on the storage costs, namely that the production and storage costs are nonspeculative, and for any two items the one that has a higher storage cost in one period has a higher storage cost in every period, we show that there is a tight linear program with O(mT 2) constraints and variables that solves the joint set-up multi-item lot-sizing problem, where m is the number of items and T is the number of time periods. This establishes that under the above storage cost conditions this problem is polynomially solvable. For the problem with backlogging, a similar linear programming result is described for the uncapacitated case under very restrictive conditions on the storage and backlogging costs. Computational results are presented to test the effectiveness of using these tight linear programs in strengthening the basic mixed integer programming formulations of the joint set-up problem both when the storage cost conditions are satisfied, and also when they are violated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anily S. and Tzur M. (2005). Shipping multiple-items by capacitated vehicles—an optimal dynamic programming approach. Transportation Sci. 39: 233–248
Anily S. and Tzur M. (2006). Algorithms for the multi-item capacitated dynamic lot sizing problem. Naval Res. Logistics 53: 157–169
Anily, S., Tzur, M., Wolsey, L.A.: Multi-item lot-sizing with joint set-up cost, CORE Discussion Paper DP 2005/70, Louvain-la-Neuve, 2005 (revised November 2006) (2005)
Bitran G.R. and Yanasse H.H. (1982). Computational complexity of the capacitated lot size problem. Manage. Sci. 28: 1174–1186
Eppen G.D. and Martin R.K. (1987). Solving multi-item lot-sizing problems using variable definition. Oper. Res. 35: 832–848
Federgruen A. and Tzur M. (1991). A simple forward algorithm to solve general dynamic lot-size models with n periods in O(n log n) or O(n) time. Manage. Sci. 37: 909–925
Florian M. and Klein M. (1971). Deterministic production planning with concave costs and capacity constraints. Manage. Sci. 18: 12–20
Florian M., Lenstra J.K. and Rinnooy K.A.N. (1980). Deterministic production planning: Algorithms and complexity. Manage. Sci. 26: 669–679
Lee C.Y. (1989). A solution to the multiple set-up problem with dynamic demand. IIE Trans. 21: 266–270
Levi, R., Lodi, A., Sviridenko, M.: Approximation algorithms for the multi-item capacitated lot-sizing problem via flow cover inequalities, Report, 5th Feb. 2007 (2007)
Levi R., Roundy R.O. and Shmoys D.B. (2006). Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. 31: 267–284
Miller A. and Wolsey L.A. (2003a). Tight MIP formulations for multi-item discrete lot-sizing problems. Oper. Res. 51: 557–565
Miller A. and Wolsey L.A. (2003b). Tight formulations for some simple mixed integer programs and convex objective integer programs. Math. Program. B 98: 73–88
Pochet Y. and Wolsey L.A. (1993). Lot-sizing with constant batches: Formulation and valid inequalities. Math. Oper. Res. 18: 767–785
Pochet Y. and Wolsey L.A. (1994). Polyhedra for lot-sizing with Wagner–Whitin costs. Math. Program. 67: 297–324
Pochet Y. and Wolsey L.A. (2006). Production Planning by Mixed Integer Programming. Springer, New York
van Hoesel C.P.M. and Wagelmans A.P.M. (1996). An O(T 3) algorithm for the economic lot-sizing problem with constant capacities. Manage. Sci. 42: 142–150
Van Vyve M. and Wolsey L.A. (2006). Approximate extended formulations. Math. Program. B 105: 501–522
Wagelmans A.P.M., van Hoesel C.P.M. and Kolen A.W.J. (1992). Economic lot-sizing: an O(n log n) algorithm that runs in linear time in the Wagner–Whitin case. Oper. Res. 40: 145–156
Wolsey L.A. (2002). Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation. Manage. Sci. 48: 1587–1602
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Anily, S., Tzur, M. & Wolsey, L.A. Multi-item lot-sizing with joint set-up costs. Math. Program. 119, 79–94 (2009). https://doi.org/10.1007/s10107-007-0202-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0202-9