We consider a variant of the classic real-time schedul-
ing problem, which has natural applications in cloud
computing. The input consists of a set of jobs, and an
integer parameter k 1. Each job is associated with a
processing time, a release time, a due-date and a posi-
tive weight. The goal is to feasibly schedule a subset of
the jobs of maximum total weight on a single machine,
such that each of the jobs is preempted at most k times.
Our theoretical results for the real-time k-bounded
preemptive scheduling problem include hardness proofs,
as well as algorithms for subclasses of instances, for
which we derive constant-ratio performance guarantees.
We bridge the gap between theory and practice through
a comprehensive experimental study, in which we also
test the performance of several heuristics for general
instances on multiple parallel machines. We use in
the experiments a linear programming relaxation to
upper bound the optimal solution for a given instance.
Our results show that while k-bounded preemptive
scheduling is hard to solve already on highly restricted
instances, simple priority-based heuristics yield almost
optimal schedules for realistic inputs and arbitrary
values of k.