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.
Origine | Fichiers produits par l'(les) auteur(s) |
---|
Loading...