Polynomial time algorithm for multi-level in series capacitated lot-sizing problems with constant batch size - Université de Lorraine
Communication Dans Un Congrès Année : 2016

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

Résumé

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.
Fichier principal
Vignette du fichier
IWLS 2016.pdf (134.4 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01522801 , version 1 (15-05-2017)

Identifiants

  • HAL Id : hal-01522801 , version 1

Citer

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. ⟨hal-01522801⟩
52 Consultations
67 Téléchargements

Partager

More