A cutting plane algorithm for robust scheduling problems in medicine

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