Reservation Strategies for Stochastic Jobs by Guillaume Aupy (Inria Bordeaux)

We are interested in scheduling stochastic jobs on a reservation-based
platform. Specifically, we consider jobs whose execution time follows a
known probability distribution. The platform is reservation-based,
meaning that the user has to request fixed-length time slots. The cost
depends on both the request duration and the actual execution time of
the job. A reservation strategy is a sequence of increasing-length
reservations, which are paid for until one of them allows the job to
successfully complete. The goal is to minimize the total expected cost
of the strategy. I will present different scheduling strategies and
properties of an optimal solution.