Department of
Applied
Mathematics

Fixed-parameter algorithms for scheduling problems

Matthias Mnich

Abstract

We study a broad class of scheduling problems with respect to their fixed-parameter tractability. To this end, we identify parameters inherent to these problems, to in time exponential only in these parameters derive optimal schedules that minimize the makespan, weighted flow time, or other objectives, even in the general setting of job-dependent cost functions. In particular, we manage to control the amount of input complexity stemming from numeric input values such as job processing times, which is often a core bottleneck in the design of fixed-parameter algorithms.