The performance of a real-time computer system is determined by the effectiveness of scheduling of jobs to meet their deadlines. However, many scheduling problems in the on-line setting have been proven to be NP-complete. In other words, it is computationally infeasible to find optimal schedules for many cases. The situation is further complicated by the fact that scheduling algorithms are on-line in nature, i.e., they do not have advance knowledge about the jobs until they are released. As expected, many scheduling problems do not admit on-line algorithms with optimal or reasonably good performance guarantee. A natural approach towards better performance guarantee is to allow on-line schedulers to have more resources (such as faster processors or extra processors). Intuitively, the additional resources compensate on-line schedulers for the lack of future information. Notice that most scheduling problems remain non-trivial even if a large amount of additional resources are available.

In this thesis, we revisit several classical deadline scheduling problems that aim at maximizing the total work or value of jobs that can be completed by their deadlines. We consider different settings, including uniprocessor and multiprocessor scheduling, and jobs with the same or different relative importance. We show new upper bounds and lower bounds on the effectiveness of using additional resources to provide better performance guarantee. Our results allow system administrators to compare and assess various scheduling algorithms and decide the resource requirement for their systems.