Approximation Algorithms for Scheduling with Class Constraints Using Integer Linear Programming

Alexandra Lassota

September 7, 2021, 12:20 in S6


In this talk, I will present Integer Linear Programming (ILP) based methods (n-fold ILPs, configuration ILPs) to solve variants of the makespan minimization problem from scheduling: We develop approximation schemes for class constraint scheduling. Here, the jobs are divided into classes and each machine can only process jobs from a limited number of classes.

Alexandra Lassota has obtained her PhD from University of Kiel under the supervision of Klaus Jansen, and is currently a postdoc in the group of Friedrich Eisenbrand at EPFL. She focuses on integer programming and scheduling, both from the perspective of algorithms as well as lower bounds.