We study the problem of allocating doctors to primary health centers. 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. We use a minmax regret approach to solve the problem. We present solution techniques using local search and 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.