Performance bounds in stochastic scheduling problems

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.