Suppose that we are given a set of jobs, where each job has a
processing time, a non-negative weight, and a set of possible
time intervals in which it can be processed.
In addition, each job has a processing cost.
Our goal is to schedule a feasible subset of the jobs on a single machine,
such that the total weight is maximized, and the cost of the schedule
is within a given budget.
We refer to this problem as {\em budgeted real-time scheduling (BRS)}.
Indeed, the special case where the budget is {\em unbounded} is the
well-known real-time scheduling problem.
The second problem that we consider is
{\em budgeted real-time scheduling with overlaps (BRSO)}, in which
several jobs may be processed simultaneously, and the goal is to maximize
the time in which the machine is utilized.
Our two variants of the
real-time scheduling problem have important applications, in
vehicle scheduling, linear combinatorial auctions
and QoS management for Internet connections.
These problems are the focus of this paper.

Both BRS and BRSO are strongly NP-hard,
even with unbounded budget.
Our main results are $(2+\eps)$-approximation algorithms
for these problems.
This ratio coincides with the best known approximation factor
for the (unbudgeted) real-time scheduling problem, and is slightly
weaker than the best known approximation factor of $e/(e-1)$ for
the (unbudgeted) real-time scheduling with overlaps, presented
in this paper. We show that
better ratios (or simpler approximation algorithms) can be derived
for some special cases,
including instances with unit-costs and the budgeted
{\em job interval selection problem (JISP)}.
Budgeted JISP is shown to be APX-hard even when overlaps are allowed
and with unbounded budget.
Finally, our results can be extended to instances with multiple machines.