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.