1. Prove that the decision version of the multiprocessor scheduling problem is
NP-complete. (Cf., page 11 of my slides.)

2. Consider the online version of the multiprocessor scheduling problem.
Show that Graham's greedy algorithm is (2 - 1/m)-competitive also if release
times are allowed. (Cf., Exercise 12.1.)

3. Consider the online version of the multiprocessor scheduling problem. For
the related machines model, show that the post-greedy algorithm is
\Theta(\log_2 m)-competitive. (Cf., Exercise 12.2.)

4. Consider the online version of the multiprocessor scheduling problem. For
the unrelated machines model, show that the post-greedy algorithm is exactly
N-competitive. (Cf., Exercise 12.4.)

5. Exercise 12.10 on bin packing.