Most interesting discrete optimization problems are NP-hard and thus the
existence of algorithms that find optimal solutions efficiently is very
unlikely for these problems. One approach to encounter this is to design
efficient algorithms that find approximate solutions. In this thesis two NP-
hard interval scheduling problems are studied. In both the goal is to schedule
a set of intervals on given machines such that intervals scheduled on the same
machine do not overlap. Additionally, the machines have a capacity constraint
in one of the variants, while in the other one an interval can be restricted
to a subset of the machines. They fall into a class of problems called
separable assignment problems, for which a framework to obtain approximation
algorithms, whose guarantees depend on the problem for a single machine,
exists.
On the basis of this framework I will describe a local search approximation
algorithm and one using linear programming with randomized rounding for both
problems.