##### Abstract

Scheduling problems are central in combinatorial optimization, and there exists a huge

literature describing both problems and algorithms. Master surgery scheduling (MSS),

where one must assign surgery teams in hospitals to different rooms at different times,

is a specialization of the assignment problem, which can be solved using mixed integer

programming (MIP).

If not all parameters to an optimization problem are known beforehand, we may

use robust optimization to find solutions which are both feasible and good, even if the

parameters are not as expected. In particular, we assume such parameters to vary

in a given set of possible ”realizations”. The more realistic assumptions, the better

solutions.

In this thesis we model MSS with the aim of minimizing the expected queue lengths

in hospitals. The model is made robust by considering the demand to be uncertain, but

belonging to a simple polytope. It can be modeled as a bilevel program. The master

program looks for feasible schedules minimizing queue lengths, while the slave program

looks for feasible demands maximizing queue lenghts.

In order to solve this bilevel program, we use an iterative cutting plane approach.

We find a solution with the best possible behaviour for the worst case parameters, by

splitting the problem in two. In particular, we implemented the so-called ”implementor/

adversary” scheme (I-A), recently proposed by Bienstock in the context of portfolio

optimization (see [7, 8]). The implementor finds an optimum schedule with respect to

a restricted set of feasible parameter vectors. The adversary finds a new vector (not

included in the restricted set) which maximizes queues with respect to the current

schedule. The new vector is included in the restricted set and the method is iterated.

When the adversary is not able to find a new parameter realization which is worsening

the value of the current schedule, we are finished. In our experiments on realistic

instances we need at most a few hundred of iteration before convergence is reached.

For comparison, we also make a non-robust model of MSS as a reference solution,

where we only consider a single demand vector.

Testing shows that I-A is indeed a very effective algorithm, solving large problem

instances in reasonable time. Moreover, the solutions were in general found to be

considerably better than the non-robust reference solution, even in cases where the

demand did not belong to the polytope we assumed. The algorithm also gives us good

intermediate solutions with provable bounds on optimality, which can be used even if

convergence is not reached.

We believe I-A both offers more flexibility and yields better results compared to the

other robust approaches, when applied to the right problems, MSS only being one of

these.