Polynomial time algorithm for multi-level in series capacitated lot-sizing problems with constant batch size

Abstract : We consider a multi-level lot-sizing problem in a serial distribution network. Customers demands are to be satisfied at the last level of the network. At each level, units can be carried in stock, and the inventory is replenished from the upstream level using batch deliveries, where a fixed cost is incurred for each batch ordered. In addition, we also consider a limitation on the number of batches that can be ordered at any period. As far as we know, the status of this multi-level lot-sizing problem with batch deliveries and capacities on the size of the orders is open. Assuming stationary and identical batch sizes and capacities for all the levels, we derive some structural properties on the optimal policy, and propose a polynomial time algorithm based on a decomposition of the problem into induced connected components. Our algorithm is polynomial both in the length of the planning horizon and in the number of levels.
Type de document :
Communication dans un congrès
International Workshop on Lot Sizing 2016, Aug 2016, Hanovre, Germany. 2016
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.univ-lorraine.fr/hal-01522801
Contributeur : Guillaume Goisque <>
Soumis le : lundi 15 mai 2017 - 15:33:27
Dernière modification le : lundi 19 février 2018 - 17:02:02
Document(s) archivé(s) le : jeudi 17 août 2017 - 00:47:33

Fichier

IWLS 2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01522801, version 1

Collections

Citation

Guillaume Goisque, Christophe Rapine. Polynomial time algorithm for multi-level in series capacitated lot-sizing problems with constant batch size. International Workshop on Lot Sizing 2016, Aug 2016, Hanovre, Germany. 2016. 〈hal-01522801〉

Partager

Métriques

Consultations de la notice

33

Téléchargements de fichiers

57