Unrelated Machine Scheduling in Different Information Models

Abstract

Unrelated machines are an abstraction of many scheduling environments appearing in practical applications, where every job may be processed at a different speed on every machine. We study different optimization problems for scheduling unrelated machines in three categories of information models, which determine the amount of information of an instance an algorithm has access to. First, we consider the offline model, where all information about the instance are known to an algorithm. We show a new connection between minimizing the makespan on unrelated machines and the closely related Santa Claus problem regarding their polynomial-time approximability. Second, we consider the online model, where an algorithm has to schedule jobs over time while coping with uncertainty about the instance. In particular, we consider non-clairvoyant scheduling, where an algorithm has no knowledge about a job's processing requirements until it completes. We prove close-to-optimal competitive ratios for this problem on unrelated machines and for even more general scheduling environments using an elegant and natural allocation rule from economics. Finally, in the third part of this thesis, we study the learning-augmented information model. In this recently emerging framework, an algorithm is given access to a potentially erroneous prediction, which potentially give an algorithm additional information to output a better solution. We present new prediction models for various scheduling problems, and design and analyze learning-augmented algorithms.