Lagrangean Heuristic for a Multi-Plant Lot-Sizing Problem with Transfer and Storage Capacities

Samuel Deleplanque; Safia Kedad-Sidhoum; Alain Quilliot

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 4, page 429-443
  • ISSN: 0399-0559

Abstract

top
The paper addresses a multi-item, multi-plant lot-sizing problem with transfer costs and capacity constraints. The problem is reformulated according to a multi-commodity flow formalism, and decomposed, through Lagrangean relaxation, into a master facility location problem and a slave minimal cost multi-commodity flow problem. The decomposition framework gives rise in a natural way to designing a Lagrangean based heuristic. Numerical experiments showing the efficiency of the proposed approach are reported.

How to cite

top

Deleplanque, Samuel, Kedad-Sidhoum, Safia, and Quilliot, Alain. "Lagrangean Heuristic for a Multi-Plant Lot-Sizing Problem with Transfer and Storage Capacities." RAIRO - Operations Research - Recherche Opérationnelle 47.4 (2013): 429-443. <http://eudml.org/doc/275021>.

@article{Deleplanque2013,
abstract = {The paper addresses a multi-item, multi-plant lot-sizing problem with transfer costs and capacity constraints. The problem is reformulated according to a multi-commodity flow formalism, and decomposed, through Lagrangean relaxation, into a master facility location problem and a slave minimal cost multi-commodity flow problem. The decomposition framework gives rise in a natural way to designing a Lagrangean based heuristic. Numerical experiments showing the efficiency of the proposed approach are reported.},
author = {Deleplanque, Samuel, Kedad-Sidhoum, Safia, Quilliot, Alain},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {lot-sizing; multi-plant; storage and transfer capacity; facility location; multi-commodity flow; lagrangean relaxation; Lagrangean relaxation},
language = {eng},
number = {4},
pages = {429-443},
publisher = {EDP-Sciences},
title = {Lagrangean Heuristic for a Multi-Plant Lot-Sizing Problem with Transfer and Storage Capacities},
url = {http://eudml.org/doc/275021},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Deleplanque, Samuel
AU - Kedad-Sidhoum, Safia
AU - Quilliot, Alain
TI - Lagrangean Heuristic for a Multi-Plant Lot-Sizing Problem with Transfer and Storage Capacities
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 4
SP - 429
EP - 443
AB - The paper addresses a multi-item, multi-plant lot-sizing problem with transfer costs and capacity constraints. The problem is reformulated according to a multi-commodity flow formalism, and decomposed, through Lagrangean relaxation, into a master facility location problem and a slave minimal cost multi-commodity flow problem. The decomposition framework gives rise in a natural way to designing a Lagrangean based heuristic. Numerical experiments showing the efficiency of the proposed approach are reported.
LA - eng
KW - lot-sizing; multi-plant; storage and transfer capacity; facility location; multi-commodity flow; lagrangean relaxation; Lagrangean relaxation
UR - http://eudml.org/doc/275021
ER -

References

top
  1. [1] I. Barany, T.J. van Roy and L.A. Wolsey. Strong formulations for multi-item capacitated lot-sizing. Manag. Sci.30 (1984) 1255–1261. Zbl0601.90037MR834100
  2. [2] G. Bitran and H. Yanasse, Computational complexity of the capacitated lot size problem. Manag. Sci.28 (1982) 1174–1186. Zbl0502.90046MR688762
  3. [3] W. Chen and J. Thizy, Analysis of relaxations for the multi-item capacitated lot-sizing problem. Annal. Oper. Res.26 (1990) 29–72. Zbl0709.90030MR1087815
  4. [4] M. Florian and M. Klein, Deterministic production planning with concave costs and capacity constraints. Manag. Sci.18 (1971) 12–20. Zbl0273.90023MR307681
  5. [5] M. Florian, J. Lenstra and A.R. Kan, Deterministic production planning: algorithms and complexity. Manag. Sci.26 (1980) 669–679. Zbl0445.90025MR591292
  6. [6] R. Jans and Z. Degraeve, Modeling industrial lot sizing problems: a review. Int. J. Prod. Res.46 (2008) 1619–1643. Zbl1160.90407
  7. [7] J. Maes and L. van Wassenhove, Multi-item single-level capacitated lot-sizing heuristics: a general review. J. Oper. Res. Soc.11 (1988) 991–1004. Zbl0655.90018
  8. [8] M.C.V. Nascimento, M.G.C. Resende and F.M.B. Toledo, Grasp heuristic with path-relinking for the multi-plant capacitated lot sizing problem. Eur. J. Oper. Res.200 (2010) 1–17. Zbl1177.90348
  9. [9] M. Sambivasan and S. Yahya, A Lagrangean based heuristic for multi-plant, multi-item, multi-period capacited lot sizing problems with inter-plant transfers. Comput. Oper. Res.32 (2005) 537–552. Zbl1061.90038
  10. [10] G. Ghiani, F. Guerrero and F. Musmanno, The capacitated plant location problem with multiple facilities in the same site. Comput. Oper. Res. 29-13 (2002) 1903–12. Zbl1259.90059MR1910405
  11. [11] G. Cornuejols, G.L. Nemhauser and L.A. Wolsey, The uncapacited facility location problem. In Discrete location theory, edited by B. Mirchandani, R.L. Francis (1990) 119–171. Zbl0727.90043MR1066259
  12. [12] B. Mirchandani and R.L. Francis, Discrete location theory. Wiley, J. Sons (1990). Zbl0718.00021MR1066256
  13. [13] M.G. Resende and R.F. Werneck, A hybrid heuristic for the p-median problem. J. Heuristics10 (2004) 59–88. Zbl1069.68600
  14. [14] M. Minoux, Programmation Mathématique, Tome 1. Dunod Ed (1983). Zbl0546.90056
  15. [15] S. Wu and H. Golbasi, Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms. Comput. Optim. Appl. 28 (2004) 325–356. Zbl1084.90013MR2080006

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.