Energy-optimal schedules of real-time jobs with hard deadlines



Journal Title

Journal ISSN

Volume Title


Texas A&M University


In this thesis, we develop algorithms that make optimal use of frequency scaling to schedule jobs with real??time requirements. Dynamic voltage scaling is a technique used to reduce energy consumption in wide variety of systems. Reducing supply voltage results in a lower processor clock speed since the supply voltage has a proportional dependency on the clock speed of the processing system. In hard real??time systems, unduly reducing the speed of processor could result in jobs missing their deadlines. The voltage scaling in such systems should therefore take into consideration the deadline of jobs. This thesis will address two questions: First, given a set of discrete frequency levels, we determine an energy-optimal sched- ule of a given set of real-time jobs. We model the problem as a network flow graph and use linear programming to solve the problem. The schedule can be used on processors with discrete frequencies (like Transmeta Efficeon Processor and AMD Turion 64 Processor). Second, given a set of real??time jobs, we determine a set of optimal frequency levels which minimizes the energy consumption while meeting all the timing con- straints. This can be used to model variable-capacity facilities in operations re- search, where the capacity of the facility can be controlled at a cost.