Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/hal-01522801
Contributor : Guillaume Goisque <>
Submitted on : Monday, May 15, 2017 - 3:33:27 PM
Last modification on : Monday, February 19, 2018 - 5:02:02 PM
Long-term archiving on: : Thursday, August 17, 2017 - 12:47:33 AM

File

IWLS 2016.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-01522801⟩

Share

Metrics

Record views

52

Files downloads

72