2, and otherwise can be solved via b-matching techniques. When jobs are arbitrary in length and can be preempted, but have a single feasible interval, we also show that a large class of algorithms is 5-approximate. We also empirically compare algorithms within this class with the incumbent greedy algorithm due to Wolsey; the latter algorithm is widely implemented in practice. This comparison is cast within a framework general enough to capture other canonical covering problems, most notably Capacitated Set Cover. In particular, we design a heuristic LPO that essentially complements Wolsey's algorithm and propose optimizations to both approaches. At a high level, our findings solidly establish LPO as a competitive, if not superior, alternative to Wolsey's algorithm, with respect to both solution quality and number of subroutine calls made. Finally, this thesis makes theoretical headway on the well-studied busy time problem. The key assumption that sets this apart from the aforementioned active time problem is that under the busy time model, the system has access to an unlimited number of identical batch machines. For non-preemptive jobs of arbitrary length, we give a 3-approximation that leverages important insights for the special case where the instance consists of interval jobs. When preemption is permitted, we give an exact algorithm for unbounded B; this result yields a simple 2-approximation for bounded B.">
[go: up one dir, main page]
Repository logo
 

Energy-Aware Batch Scheduling

Thumbnail Image

Files

Chang_washington_0250E_12346.pdf (627.28 KB)

Date

2013-11-14

Authors

Chang, Jessica

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

The subject of this thesis concerns algorithmic aspects of energy-related trends in computation. Within recent years, the computationally heaviest jobs are executed over massive corpora residing at data centers, whose energy profiles differ from those of standard desktops, and whose power consumption translates into an operational budget on the order of millions of dollars. Designing schedules to optimize notions of power consumption is sometimes at odds with standard techniques prevalent in the classical scheduling theory, which has traditionally focused on objectives capturing the interests of the scheduler (e.g., makespan) or of individual jobs (e.g., flow time). Thus, we study a fairly simple model of energy usage: the active time scheduling model. Formally, we are interested in scheduling a set of n jobs, each with release time, deadline and processing requirement, on a system comprised of a single batch machine, with batch parameter B. (The machine can be working on up to B jobs at the same time.) The cost of a schedule is simply the amount of time that the system, i.e., the machine, is working. This is akin to the magnitude of the schedule's projection onto the time axis. The underlying assumption is that the cost for the machine to be active is roughly the same, regardless of whether it is working on only one job or operating at full capacity. We give a fast algorithm for the basic case in which jobs are unit length and time is slotted. When time is not slotted, the problem still admits a polynomial-time solution, albeit of higher time complexity, via dynamic programming techniques. On the other hand, when time is slotted, but jobs may have multiple feasible intervals, the problem is NP-hard for B > 2, and otherwise can be solved via b-matching techniques. When jobs are arbitrary in length and can be preempted, but have a single feasible interval, we also show that a large class of algorithms is 5-approximate. We also empirically compare algorithms within this class with the incumbent greedy algorithm due to Wolsey; the latter algorithm is widely implemented in practice. This comparison is cast within a framework general enough to capture other canonical covering problems, most notably Capacitated Set Cover. In particular, we design a heuristic LPO that essentially complements Wolsey's algorithm and propose optimizations to both approaches. At a high level, our findings solidly establish LPO as a competitive, if not superior, alternative to Wolsey's algorithm, with respect to both solution quality and number of subroutine calls made. Finally, this thesis makes theoretical headway on the well-studied busy time problem. The key assumption that sets this apart from the aforementioned active time problem is that under the busy time model, the system has access to an unlimited number of identical batch machines. For non-preemptive jobs of arbitrary length, we give a 3-approximation that leverages important insights for the special case where the instance consists of interval jobs. When preemption is permitted, we give an exact algorithm for unbounded B; this result yields a simple 2-approximation for bounded B.

Description

Thesis (Ph.D.)--University of Washington, 2013

Keywords

algorithms; scheduling

Citation

URI

http://hdl.handle.net/1773/24131

DOI

Collections

Computer science and engineering