Show simple item record

Combinatorial Algorithms for the Active Time and Busy Time Problems

dc.contributor.advisorKhuller, Samiren_US
dc.contributor.authorKumar, Saurabhen_US
dc.description.abstractIn this thesis, we consider the problem of scheduling jobs in such a way that we minimize the energy consumption of the machines they are scheduled on. Job scheduling itself has a long and rich history in computer science both from theoretical and applied perspectives. A multitude of different objectives to optimize have been considered such as weighted completion time, penalties for missed deadlines, etc. However, traditional objective functions such as these do not capture or model the energy consumption of the machines these jobs run on. Energy consumption is an important facet of job scheduling to consider not only because of its relationship with the financial costs of scheduling (such as those related to cooling and the cost of powering the machines) but also due to its impact on the environment. This is especially true in the context of data centers as more and more processing is pushed to the cloud. We study two problems related to these issues - the active time problem and the busy time problem. First, we give a purely combinatorial algorithm for the active time problem which matches its best known approximation ratio (the existing algorithm is based on a rather involved LP rounding scheme). Second, we describe a local search based heuristic for the problem and also consider an experimental evaluation of these algorithms on artificially generated data. Finally, we describe two very simple algorithms which match the current best upper bounds for the busy time problem when all job lengths are equal.en_US
dc.titleCombinatorial Algorithms for the Active Time and Busy Time Problemsen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledApproximation Algorithmsen_US
dc.subject.pquncontrolledJob Schedulingen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record