Tata Institute of Fundamental Research
Asymptotically Optimal Threshold Policies for Appointment Scheduling and Stochastic Knapsacks.
STCS Seminar
Speaker:
Harsha Honnappa (School of Industrial Engineering
Purdue University
West Lafayette
IN 47907, USA)
Organiser:
Sandeep K Juneja
Date:
Thursday, 25 Jul 2019, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Harsha Honnappa (School of Industrial Engineering Purdue University West Lafayette IN 47907, USA) |
| Organiser: | Sandeep K Juneja |
| Date: | Thursday, 25 Jul 2019, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).