PhD Defense Madelon de Kemp
On December 15th Madelon de Kemp will defend her PhD thesis entitled 'Performance bounds in stochastic scheduling problems'.
Madelon's promotors are Michel Mandjes and Neil Olver.
The PhD defense will take place in the Agnietenkapel (Oudezijds Voorburgwal 229 - 231, 1012 EZ Amsterdam) and will start at 15:00 hrs.
It can be followed online through livestream on the UvA YouTube channel.
Abstract
There exist various situations in which one wants to optimize something in a stochastic setting, giving rise to a stochastic optimization problem. In this thesis, we consider various stochastic optimization problems. For each of these problems, we study the performance of some simple policy by studying the approximation ratio, defined as the cost of the simple policy divided by the cost of the optimal policy. If we can prove an upper bound on the approximation ratio, this gives a performance guarantee for the policy under consideration.
One problem we consider is the appointment sequencing problem. A single server needs to make appointments with a number of patients, each with a given service time distribution. The arrival times of the patients need to be determined in order to minimize the cost, given as a weighted average of expected patient waiting time and expected server idle time. This problem can be split into two subproblems: the sequencing problem of determining the order in which the patients arrive, and the scheduling problem of determining the time between the arrivals of two consecutive patients once the order is set. We assess the performance of the smallest-variance-first (SVF) rule for the sequencing problem, which sequences patients in increasing order of the variance of their service time. We provide upper bounds for the approximation ratio, which is the cost of the SVF rule divided by the cost of the optimal sequence, under various assumptions.
You can read the thesis here.
