In this paper, we present RED-BL (Relocate Energy Demand to Better Locations), a framework to minimize the electricity cost for operating data center networks over consecutive intervals of fixed duration. Within each interval, RED-BL provides a mapping of workload to a set of geographically distributed data centers. To this end, RED-BL uses the geographical and temporal variations in electricity prices as exhibited by electrical energy markets. In addition, we incorporate the transition costs associated with a change in workload mapping from one interval to the next, over a planning window comprising multiple such intervals. This results in a sequence of workload mappings that is optimal over the entire planning window, even though the workload mapping in a given interval may not be locally optimal. Our evaluation of RED-BL uses electricity prices from the US markets and workload traces from live Internet applications with millions of users. We find that RED-BL can reduce the electric bill by as much as 45% compared to the case when the workload is uniformly distributed. When compared to existing workload relocation solutions, for a wide range of data center deployment sizes, RED-BL achieves electricity cost savings that are 8.28% higher, on average. This seemingly modest reduction can save millions of dollars for the operators. The cost of this saving is an inexpensive computation at the start of each planning window. © 2014 Elsevier B.V. All rights reserved.