This dissertation, "Energy Efficient Online Deadline Scheduling" by 麥健心, Kin-sum, Mak, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled \Energy Ecient Online Deadline Scheduling" Submitted by Mak Kin Sum for the degree of Master of Philosophy at The University of Hong Kong in September 2007 Processor scheduling is a classical optimization problem. The perfor- mances of scheduling algorithms have direct impacts on the performance of computer systems. And as the proliferation of mobile devices, en- ergy usage has become an important performance measure of processor scheduling. In this thesis, we focus on online setting of scheduling prob- lems, in which the information of a job is known only on or after the job is released. We study 3 online scheduling problems, namely Energy Ef- cient Deadline Scheduling, Bounded Energy Eciency Scheduling and Randomized Algorithm for Bounded Energy Ecient Scheduling. In Energy Ecient Deadline Scheduling, we consider the case where a processor can vary its speed from 0 to T. The objective of the opti- mal schedule is to maximize its throughput and then minimize its total energy usage subject to that throughput. Previous work has focused on completing all jobs with minimum energy on a unbounded speed proces- sor. We present an online algorithm which is the rst online algorithm which works in a more realistic setting, where the speed of the processor is bounded by T and the system may be overloaded, which means theremay be no schedule that can complete all the jobs. This algorithm is proved to be constant competitive on both throughput and energy. The result is also extended to the case where jobs are assigned with dierent values. Existing work on scheduling with energy concern has focused on minimizing the energy for completing all jobs or achieving maximum throughput. That is, energy usage is a secondary concern when com- pared to throughput and the schedules targeted may be very poor in energy eciency. In Bounded Energy Eciency Scheduling, we attempt to put energy eciency as the primary concern and study how to maxi- mize throughput subject to a user-dened threshold of energy eciency. We rst show that all deterministic online algorithms have a competitive ratio at least, where is the max-min ratio of job size. Nevertheless, allowing the online algorithm to have a slightly poorer energy eciency leads to constant (i.e., independent of ) competitive online algorithm. Finally we consider a special case where no jobs are "demanding" and give a deterministic online algorithm with constant competitive ratio for this case. Finally we consider Randomized Algorithm for Bounded Energy Ef- ciency Scheduling. We rst improved the result of the randomized algorithm proposed by Goldman et al [19] which Goldman showed it is competitive in xed speed processor with non-preemptive setting. We further proved it is also competitive in preemptive setting. Later we show how to adapt and modify the randomized algorithm so that itovercome the lower bound barrier in the scheduling problem Bounded Energy Eciency Scheduling. We show the algorithm is O(log) in both preemptive and non-preemptive settings. (449 words) DOI: 10.5353/th_b3955827 Subjects: Computer schedulingComputer algorithms