Optimization Online


Decomposition-Based Approximation Algorithms for the One-Warehouse Multi-Retailer Problem with Concave Batch Order Costs

Weihong Hu (weihongh***at***gatech.edu)
Alejandro Toriello (atoriello***at***isye.gatech.edu)
Maged Dessouky (maged***at***usc.edu)

Abstract: We study the one-warehouse multi-retailer (OWMR) problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem into single-facility subproblems, then propose approximation algorithms by judiciously recombining the subproblem solutions. For piecewise linear concave batch order costs with a constant number of slopes we obtain a constant-factor approximation, while for general concave batch costs we propose an approximation within a logarithmic factor of optimality. We also extend some results to subadditive order and/or holding costs.

Keywords: one-warehouse multi-retailer, lot-sizing, decomposition heuristic

Category 1: Applications -- OR and Management Sciences (Supply Chain Management )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Category 3: Combinatorial Optimization (Approximation Algorithms )

Citation: H. Milton Stewart School of Industrial and Systems Engineering, August 2016

Download: [PDF]

Entry Submitted: 08/05/2016
Entry Accepted: 08/05/2016
Entry Last Modified: 02/24/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society