Modern computer systems distribute computation among several machines, so
as to speed up the execution of programs. Yet, setup and communication costs,
as well as parallelism constraints, bound the number of machines that can
share the execution of a given application, and the number of machines by
which it can be processed {\em simultaneously}.
We study the resulting scheduling problem, stated as follows. Given a set
of $n$ jobs and $m$ uniform machines, assign the jobs to the machines
subject to parallelism and machine allotment constraints, such that
the overall completion time of the schedule (or {\em makespan}) is minimized.
Indeed, the {\em multiprocessor scheduling problem} (where each job can
be processed by a {\em single} machine) is a special case of our problem;
thus, our problem is strongly NP-hard.
We present a $(1+ \alpha)$-approximation algorithm for this problem,
where $\alpha \in (0,1]$ depends on the minimal number of machine allotments
and the minimal parallelism allowed for any job. Also, we show that when
the maximal number of machines that can share the execution of a job is
some fixed constant, our problem has a {\em polynomial time approximation
scheme}; for other special cases we give optimal polynomial time algorithms.
Finally, through the relation of our problem to the classic {\em
preemptive} scheduling problem on multiple machines, we shed some fresh
light on what is known in scheduling folklore as the {\em power of
preemption}.