It is well known that for preemptive scheduling on uniform
machines there exist polynomial time exact algorithms,
whereas for non-preemptive scheduling there are probably no such algorithms.
However, it is not clear how many preemptions (in total, or 
per job) suffice in order to guarantee an optimal polynomial 
time algorithm. 
In this paper we investigate exactly this hardness gap, 
formalized as two variants of the classic preemptive scheduling problem.
In {\em generalized multiprocessor scheduling (GMS)},
we have {\em job-wise} or {\em total} bound on the number of preemptions
throughout a feasible schedule.
We need to find a schedule that satisfies the preemption
constraints, such that the maximum job completion time is 
minimized. In {\em minimum preemptions scheduling (MPS)},
the only feasible schedules are preemptive schedules with 
smallest possible makespan.
The goal is to find a feasible schedule that minimizes
the overall number of preemptions.
Both problems are NP-hard, even for two machines and zero preemptions.

For GMS, we develop {\em polynomial time approximation schemes},
distinguishing between the cases where the number of machines 
is {\em fixed}, or given as part of the input. 
For MPS, we derive matching lower and upper bounds 
on the number of preemptions required by {\em any} optimal schedule.