Result: Real-time scheduling with a budget

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 budgeted real-time scheduling (BRS). Indeed, the special case where the budget is unbounded is the well-known real-time scheduling problem. The second problem that we consider is 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 this real-time scheduling problem have important applications, in vehicle scheduling, linear combinatorial auctions, and Quality-of-Service 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 + ε)-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 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.