Cost-effectiveness of electricity energy efficiency programs

We analyze the cost-effectiveness of electric utility ratepayer-funded programs to promote demand-side management (DSM) and energy efficiency (EE) investments. We specify a model that relates electricity demand to previous EE DSM spending, energy prices, income, weather, and other demand factors. In contrast to previous studies, we allow EE DSM spending to have a potential longterm demand effect and explicitly address possible endogeneity in spending. We find that current period EE DSM expenditures reduce electricity demand and that this effect persists for a number of years. Our findings suggest that ratepayer funded DSM expenditures between 1992 and 2006 produced a central estimate of 0.9 percent savings in electricity consumption over that time period and a 1.8 percent savings over all years. These energy savings came at an expected average cost to utilities of roughly 5 cents per kWh saved when future savings are discounted at a 5 percent rate. Copyright © 2012 by the IAEE. All rights reserved.

Energy efficiency policies: A retrospective examination

We review literature on several types of energy efficiency policies: appliance standards, financial incentive programs, information and voluntary programs, and management of government energy use. For each, we provide a brief synopsis of the relevant programs, along with available existing estimates of energy savings, costs, and cost-effectiveness at a national level. The literature examining these estimates points to potential issues in determining the energy savings and costs, but recent evidence suggests that techniques for measuring both have improved. Taken together, the literature identifies up to four quads of energy savings annually from these programs - at least half of which is attributable to appliance standards and utility-based demand-side management, with possible additional energy savings from the U.S. Department of Energy's (DOE's) ENERGY STAR, Climate Challenge, and Section 1605b voluntary programs to reduce carbon dioxide (CO 2) emissions. Related reductions in CO 2 and criteria air pollutants may contribute an additional 10% to the value of energy savings above the price of energy itself. Copyright © 2006 by Annual Reviews. All rights reserved.

Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.