Multi-Item capacitated lot-Sizing problem with setup times and shortage costs : Polyhedral results.
Approche polyédrale pour un problème de lot-sizing à capacité finie avec temps de setup et coûts de ruptures.
Résumé
We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem can be modelled as a mixed integer program and it is NP-hard. In this paper, we propose some classes of valid inequalities based on a generalization of Miller et al. (2003) results. We study the polyhedral structure of the convex hull of this model which help us to prove that these inequalities induce facets of the convex hull under certain conditions.
Commentaires : Merci de me transmettre 5 rapports recherche.
On s'intéresse au problème de lot-sizing à capacité finie avec temps de setup et coûts de ruptures rencontrés dans de nombreuses applications industrielles. La particularité du modèle est que les demandes ne peuvent pas être reportées en cas de capacité insuffisante, elles sont donc partiellement ou totalement perdues. Le problème est NP-difficile. Nous présentons dans ce papier une caractérisation d'inégalités valides pour le problème formulé comme un problème linéaire mixte entier, basée sur une généralisation des travaux de Miller et al. (2003). On prouve que ces inégalités induisent des facettes du polyèdre des solutions sous certaines hypothèses.
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...