D.: Approximation Algorithms for Scheduling with Reservations

We study the problem of non-preemptively scheduling n indepen-dent sequential jobs on a system of m identical parallel machines in the presence of reservations, where m is constant. This setting is prac-tically relevant because for various reasons, some machines may not be available during specified time intervals. The objective is to minimize the makespan Cmax, which is the maximum completion time. The general case of the problem is inapproximable unless P = NP; hence, we study a suitable strongly NP-hard restriction, namely the case where at least one machine is always available. For this setting we contribute approximation schemes, complemented by inapproxima-bility results. The approach is based on algorithms for multiple subse