  Motivated by the need for social distancing during a pandemic, we consider an
approach to schedule the visitors of a facility. The algorithm takes input from
citizens and schedules the store's time-slots based on their importance to
visit the facility (e.g., a general store). Naturally, the formulation applies
to several similar problems. We consider the single slot and multiple slot
demands of the requests. The salient properties of our approach are: it (a)
ensures social distancing by ensuring a maximum population in a given time-slot
at the facility, (b) prioritizes individuals based on the users' importance of
the jobs, (c) maintains truthfulness of the reported importance by adding a
cooling-off period after their allocated time-slot, during which the individual
cannot re-access the same facility, (d) guarantees voluntary participation of
the citizens, and yet (e) is computationally tractable. We show that the
problem becomes NP-complete as soon as the multi-slot demands are indivisible
and provide a polynomial-time mechanism that is truthful, individually
rational, and approximately optimal. Experiments show that visitors with more
important jobs are allocated more preferred slots, which comes at the cost of a
longer delay to re-access the store. We show that it reduces the social
congestion significantly using users' visit data from a store. For the
multi-slot indivisible jobs, our approximately optimal mechanism performs well
in practice.
