MASSACHUSETTS INSTITUTE OF TECHNOLOGY
OPERATIONS RESEARCH CENTER
FALL 2004 SEMINAR SERIES

DATE

Thursday, December 2, 2004

LOCATION: Room E40-298           TIME: 4:15pm

Reception immediately following in the
Philip M. Morse Reading Room, E40-106

SPEAKER

Professor Robin Roundy
Operations Research and Industrial Engineering
Cornell University

TITLE

Improved Approximation Algorithms For the Joint Replenishment Problem

ABSTRACT

     We consider the joint replenishment problem (JRP) with a discrete-time, finite horizon and deterministic non-stationary demand: for each of N items and T time periods, we have a given demand that must be satisfied on time, and in each time period we can order any subset of items paying a joint fixed cost in addition to an individual fixed cost for each item ordered; we can also hold inventory while incurring an item-dependent linear holding cost; the goal is to find a policy that satisfies all demands on time and minimizes the overall fixed and holding cost.

     This classical deterministic inventory model is known to be NP-hard; many heuristics for finding optimal and near-optimal solutions were developed. We will show how LP-based techniques yield efficient approximation algorithms with constant performance guarantees significantly improving on previously known results. We give both LP rounding and primal-dual algorithms that build upon techniques recently applied to facility location problems. These methods have natural extensions to more general variants of the JRP and other inventory models.