From bender Fri Dec 2 16:23:30 2005 Received: from [130.245.14.30] (sbrtjohnson [130.245.14.30]) by sbcs.cs.sunysb.edu (8.12.3/8.12.11) with ESMTP id jB2LNKGg025803 for ; Fri, 2 Dec 2005 16:23:20 -0500 (EST) Message-ID: <4390BB47.6080607@cs.sunysb.edu> Date: Fri, 02 Dec 2005 16:23:19 -0500 From: Rob Johnson User-Agent: Debian Thunderbird 1.0.2 (X11/20050602) X-Accept-Language: en-us, en MIME-Version: 1.0 To: algorithms-list@cs.sunysb.edu Subject: Inchoate problems from the electrical grid Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 5800 Status: RO Here's the write-up of today's theory reading group. All mistakes are my own. The scheduling problem we discussed at length is at the end. Best, Rob Steve Skiena led a brainstorming session to discover algorithmic problems that arise from the current infrastructure for distributing electricity in the United States. With George Hart as our expert consultant on all things electrical, we learned that - there are O(hundreds) of large power plants in the U.S. - there are many more micro-plants (e.g. solar cells on residential homes) - power lines fall into 3 main categories: big, medium, and small. Big lines may traverse hundreds of miles. - electric power is not routed like packets. Instead, the power plants generate a potential difference (i.e. like water at the top of a hill), and it flows to locations in the grid that have lower potential. - electrical power is dissipated (as heat, presumably) as it travels over power lines. George estimates that 10% of electrical power is lost in transmission. - each power line has a max capacity before it melts. - power generators have a fixed operating cost and a startup cost that must be paid every time they are started. - power companies have good models of demand over time. - power companies try to design their grids to be stable in the event of one failure (e.g. downed major power line). Stability requires not only that the graph be connected, but that no line is used to transmit more power than it can support. We attempted to explore several questions: - is the grid planar? - When is it economical to add a new, direct power line to reduce transmission losses between a power plant and a consumer site? - What is the reliability of a given power grid? i.e. how many lines can be simultaneously cut such that all power sinks can still get power and no power line is overloaded? There's a theorem, provided by Estie Arkin: Definition: Given a graph G with source vertices s_1, ..., s_k, sinks t_1, .., t_l, and edge capacities c_ij for all pairs of vertices, define the net demand of a subset of vertices S as the total demand over all sinks in S that cannot be satisfied by sources in S (and only uses edges between vertices in S). Theorem: There exists a power distribution plan that satisfies all demand iff there does not exist a set S \subset V such that the total capacity of edges entering S exceeds the net demand of S. Can we extend this to efficiently determine the minimum number of lines that need to be cut to render the graph unable to meet all the power demand? - We observed that if power demand increases in Florida, it may be most economical to meet it by activating a plant in Oregon. This could occur if a plant in Chicago was currently supplying power to the Midwest. When the Oregon plant comes online, the Chicago plant's power can now go to Florida. Current power scheduling is performed on a regional basis (e.g. the Northeast). Are they doing an optimal scheduling per region? Could efficiency be improved by scheduling at a national level? ******************** The scheduling problem ********************* The longest discussion centered around the problem of scheduling the power generators. We abstracted the problem thusly: We have n power generators, each with a capacity c_i, a startup cost s_i, and a running cost r_i. Job i arrives at time t_i, has duration d_i, and load v_i. Our job is to schedule generators such that we can meet the job demand at all times while minimizing costs. Since electricity is fungible, we can simply treat the jobs as a function f(t) specifying the total power demand at time t. From now on, we assume that we know f(t) in advance (i.e. this is an offline scheduling problem). For convenience, let o_i = s_i/r_i, i.e. starting up generator i has the same cost running generator i for o_i seconds. First case: all the generators are identical, i.e. they have the same capacity, c, startup cost, s, running cost, r, and overhead, o. In this case, we may assume the generators have capacity 1, and we can replace f(t) by ceiling(f(t)). A greedy algorithm suffices: start with all generators off for each time t where f changes (in chronological order) if f increases beyond the number of generators currently running startup more generators to cover demand if f decreases from b to a let m = max(f(x)) where x \in (t, t+o) shut down all but m generators Proof (sketch): Suppose the optimal scheduling differs from the scheduling given by the above algorithm. Then there must be some first point, t, where it differs. First, we can argue that f changes at time t, or the optimal schedule wouldn't be optimal. Next, we can argue that if the optimal schedule runs fewer generators than our schedule at time t, it could reduce its overall cost by leaving some generators on. Similarly, if it runs more generators, then it could save money by turning some off. Second case: the generators only differ in their startup costs. The algorithm is very similar: start with all generators off for each time t where f changes (in chronological order) if f increases beyond the number of generators currently running startup generators, in order of increasing s_i, to cover demand if f decreases for each running generator i, in order of increasing s_i if max_{x \in (t, t+o_i)} (f(x)) < # currently running generators shut down generator i Proof (sketch): very similar to previous proof. Third case: the generators only differ in their running costs. The original algorithm suffices, as long as we prioritize machines by their running costs. The more general versions of the problem are still open (to us). Best, Rob