BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/977
DTSTAMP:20230914T125945Z
SUMMARY:Asymptotically Optimal Threshold Policies for Appointment Schedulin
 g and Stochastic Knapsacks.
DESCRIPTION:Speaker: Harsha Honnappa (School of Industrial Engineering\nPur
 due University\nWest Lafayette\nIN 47907\, USA)\n\nAbstract: \nAbstract : 
 We study an appointment scheduling (AS) problem where a finite pool of job
 s must be scheduled at a single server queue over a finite fixed time hori
 zon. Jobs once scheduled may not show up (or ‘no show’) with fixed pro
 bability\, and will take a random amount of time in the server. The AS pro
 blem seeks an arrangement of the jobs over the finite horizon such that th
 e 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 impleme
 nted. In this work\, we prove by construction the existence of an asymptot
 ically 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 heav
 y-traffic. We also quantify the ’stochasticity gap’ of using the heuri
 stic policies against the best offline/oracle policy where all the stochas
 ticity is unveiled ahead of time. We also demonstrate an equivalence betwe
 en the AS problem and dynamic and stochastic knapsack problems (KP). In th
 e 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 cumulati
 ve reward. This is joint work with Mor Armony (NYU) and Rami Atar (Technio
 n).\n \n
URL:https://www.tcs.tifr.res.in/web/events/977
DTSTART;TZID=Asia/Kolkata:20190725T160000
DTEND;TZID=Asia/Kolkata:20190725T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR