Asymptotically Optimal Threshold Policies for Appointment Scheduling and Stochastic Knapsacks.

Abstract : We study an appointment scheduling (AS) problem where a finite pool of jobs must be scheduled at a single server queue over a finite fixed time horizon. Jobs once scheduled may not show up (or ‘no show’) with fixed probability, and will take a random amount of time in the server. The AS problem seeks an arrangement of the jobs over the finite horizon such that the cumulative wait times of jobs that turn up are balanced against overage costs.  In general, the AS integer program is quite hard to solve, and we seek non-adaptive optimal threshold policies that can be easily implemented. In this work, we prove by construction the existence of an asymptotically optimal sequence of heuristic policies as the number of jobs/items increases to infinity, both in a fluid and diffusion scale. In fact, our policy shows that asymptotically it is optimal to keep the system in heavy-traffic. We also quantify the ’stochasticity gap’ of using the heuristic policies against the best offline/oracle policy where all the stochasticity is unveiled ahead of time. We also demonstrate an equivalence between the AS problem and dynamic and stochastic knapsack problems (KP). In the latter, items of random sizes are presented (one after another) over a finite time horizon to a decision-maker who seeks to pack a fixed capacity ‘knapsack’ with a minimal number of items while maximizing a cumulative reward. This is joint work with Mor Armony (NYU) and Rami Atar (Technion).