This paper supersedes the work presented in WP.No.2014-02-06. We study the problem of allocating
doctors to primary health centers (PHC). We model the problem as a multi-period uncapacitated facility
location problem under uncertainty. The problem is unconventional in that the uncertainty is in the
number and period of availability of doctors. This work aims to determine the sequence of opening facil-
ities (assigning doctors to the PHC) over multiple periods so as to cover the maximum demand. We use
a minmax regret approach to solve the problem under uncertainty. We present solution techniques using
tabu search and compare our solutions with optimal solutions obtained using commercial solvers. We see that one of our tabu search algorithms is faster and yields optimal solutions in the problems we tested on.