Abstract
We consider the multi-item discrete lot-sizing and scheduling problem on identical parallel machines. Based on the fact that the machines are identical, we introduce aggregate integer variables instead of individual variables for each machine. For the problem with start-up costs, we show that the inequalities based on a unit flow formulation for each machine can be replaced by a single integer flow formulation without any change in the resulting LP bound. For the resulting integer lot-sizing with start-ups subproblem, we show how inequalities for the unit demand case can be generalized and how an approximate version of the extended formulation of Eppen and Martin can be constructed. The results of some computational experiments carried out to compare the effectiveness of the various mixed-integer programming formulations are presented.
Similar content being viewed by others
References
Belvaux G., Wolsey L.A.: Modelling practical lot-sizing problems as mixed-integer programs. Manag. Sci. 47, 993–1007 (2001)
Constantino, M.: A polyhedral approach to production planning models: startup costs and times and lower bounds on production. PhD thesis, Université catholique de Louvain, Belgique (1995)
Eppen G.D, Martin R.K.: Solving multi-item capacitated lot-sizing problems using variable redefinition. Oper. Res. 35, 832–848 (1987)
Gicquel, C., Minoux, M., Dallery, Y.: A tight MIP formulation for the discrete lot sizing and scheduling problem with parallel resources, International Conference on Computers and Industrial Engineering. Université Technologique de Troyes, Troyes, France (2009)
Jans R., Degraeve Z.: An industrial extension of the discrete lot-sizing and scheduling problem. IIE Trans. 36, 47–58 (2004)
Lasdon L.S.: Optimization theory for large systems. Macmillan, New York (1970)
Lasdon L.S., Terjung R.C.: An efficient algorithm for multi-item scheduling. Oper. Res. 19, 946–969 (1971)
Salomon M., Solomon M., van Wassenhove L.N., Dumas Y., Dauzère-Peres S.: Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the travelling salesman problem with time windows. Eur. J. Oper. Res. 100, 494–513 (1997)
Vanderbeck F., Wolsey L.A.: Valid inequalities for the Lasdon-Terjung production model. J. Oper. Res. Soc. 43, 435–441 (1992)
Van Eijl C.A., van Hoesel C.P.M.: On the discrete lot-sizing and scheduling problem with Wagner-Whitin costs. Oper. Res. Lett. 20, 7–13 (1997)
van Hoesel C.P.M., Kolen A.: A linear description of the discrete lot-sizing and scheduling problem. Eur. J. Oper. Res. 75, 342–353 (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gicquel, C., Wolsey, L.A. & Minoux, M. On discrete lot-sizing and scheduling on identical parallel machines. Optim Lett 6, 545–557 (2012). https://doi.org/10.1007/s11590-011-0280-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0280-8