Integrating facility location and production planning
-
We consider a metric uncapacitated facility location
problem where we must assign each customer to a facility and meet
the demand of the customer in future time periods through production
and inventory decisions at the facility. We show that the problem,
in general, is as hard to approximate as the set-cover problem and
focus on approximation algorithms for special cases of the problem.
These special cases come in two forms: (i) specialize the
production and inventory cost structure and (ii) specialize the
demand pattern of the customers. In the former, we offer reductions
to variants of the metric uncapacitated facility location problem
that have been previously studied. The latter gives rise to a class
of metric uncapacitated facility location problems where the
facility cost function is a concave function in the amount of demand
assigned to the facility. We develop a greedy algorithm for this
problem with an approximation guarantee of 1.61. We then use the
greedy algorithm together with the idea of cost-scaling to provide
an algorithm for this class of problems with an approximation
guarantee of 1.52.