Approximation of Multiobjective Optimization Problems, Scheduling Games, and Decision Support in Physician Scheduling

Vendredi 11 mai 2018, 14h, C 108

Clemens Thielen, University of Kaiserslautern

This talk presents the results of three recently published articles from the areas of multiobjective optimization, algorithmic game theory, and personnel scheduling.

In the first part of the talk, we present a general, polynomial-time approximation method for biobjective minimization problems. This method yields approximations of the Pareto set as well as of the associated budget-constrained problem for every biobjective minimization problem for which the corresponding weighted sum scalarization can be approximated in polynomial time.

In the second part of the talk, we consider a game theoretical model of multistage interval scheduling problems in which each job consists of exactly one task (interval) for each of t stages (machines). In the game theoretical model, the machine of each stage is controlled by a different selfish player who wants to maximize her total profit, where the profit for scheduling the task of a job is a fraction of the weight of the job that is determined by the set of players that also schedule their corresponding task of this job. We provide criteria for the existence of pure Nash equilibria and prove bounds on the Price of Anarchy and the Price of Stability for different social welfare functions.

The third part of the talks presents an integer programming model for the generation of duty rosters for physicians at a large department of orthopedics and trauma surgery that is used in practice since January 2016. Besides the specific constraints that need to be respected and the resulting model, we additionally present a decision support component for the handling of unpredictable disruptions (caused, e.g., by absence of physicians due to illness) and evaluate the generated duty rosters from a practical perspective.