NASA Technical Memorandum 103149

Electric Power Scheduling: A Distributed

Problem-Solving Approach

Pamela A. Mellor and James L. Dolce

Lewis Research Center

Cleveland, Ohio

Joseph C. Krupp

Decision Science Applications, Inc.

Arlington, Virginia

A OISTrCTjUTFC P_CnLCM-b!)lViN_j Appnc}&C H

(NASA) 'J _ C_£l ng_

Prepared for the

25th Intersociety Energy Conversion Engineering Conference

cosponsored by the AIChE, SAE, ACS, AIAA, ASME, and IEEE

Reno, Nevada, August 12-17, 1990

Electric Power Scheduling: A Distributed Problem-Solving Approach

Pamela A. Mellor and ]ames L. Dolce

National Aeronautics and Space Administration

Lewis Research Center

Cleveland, Ohio 44135

Joseph C. Krupp

Decision Science Applications,

1110 Glebe Road

Arlington, Virginia 22201

[no .

O

I

g_3

Abstract

Space Station Freedom's power system, along with

the spacecraft's other subsystems, needs to carefully

conserve its resources and yet strive to maximize

overall Station productivity. Due to Freedom's distributed design, each subsystem must work cooperatively within the Station community. There is a

need for a scheduling tool which will preserve this distributed structure, allow each subsystem the latitude

to satisfy its own constraints, and preserve individual value systems while maintaining Station-wide integrity. The value-driven free-market economic model

is such a tool.

1 Resource Allocation

1.1 The Need for Load Scheduling

Many similarities between Space Station Freedom's

power system and terrestrial power utilities are apparent. Both systems incorporate generation, storage

(usually a pumped water reservoir for the terrestrial--

batteries for us), transmission lines, circuit breakers,

and power consumers. Both systems rely heavily on

human decision-making for safe, economic operation.

But, the strategy that controls the operation of the

two systems is fundamentally different. This difference arises at the power supply.

In terrestrial utilities, ample generation is usually

available for the demanded loading; when it is not,

power is purchased from the grid. The control strategy is to modulate generation capacity to match the

demand's changes. Any shortage is covered by interchange with the grid. Every effort is made to meet

the consumers' demands by managing the injection of

power into the transmission network, controlling the

loads themselves is reserved for extreme failures when

there is no acceptable alternative.

Freedom has no tie-line to a neighboring utility. The

control strategy is to maximize solar energy conversion with energy utilization controlled by adding and

deleting loads from the system. This in turn requires

that the load demand be as determinate as possible so

that each watt can be allocated. Although this procedure maximizes payload productivity, it generates an

extremely difficult scheduling problem [1].

Scheduling the electrical energy among the consumers is a resource allocation problem and would

seem amenable to a host of mature operations research

algorithms. However, Space Station Freedom's design is evolving as a confederation of separate agents

(life support, communication, propulsion, payload 1,

etc.), each with a responsibility to perform a unique

function. Structuring the electrical resource allocation

problem as a constrained maximization of some objective function oversimplifies the interactions with the

rest of the infrastructure. The real issue is to maximize the collective welfare of the various functional

agents. This implies bargaining among the power requesters and the power management agent to produce

equitable allocations [2].

We note that managing the electrical loads is no different than managing loads applied to any subsystem

aboard the station. If Space Station Freedom is to operate coherently as a confederacy of separate agents,

some of the agents will necessarily have the authority

to determine the behavior of others. For the present,

who directs whom is contentious. We propose to define roles and responsibilities for participation in a dis-
tributed bargaining transaction that will yield a productive allocation of Freedom's resources through load

scheduling.

1.2 A Cooperative Approach

1.2.1 The Project Management Paradigm

There is a strong parallel between managing the automatic operation of Freedom and managing complex

projects involving human beings. The conventional

wisdom for the latter uses a systems management approach to control and coordinate a project's activities. This contemporary theory of organization management uses a project manager to coordinate the entire operation. This manager's legitimate authority

is based on participation and persuasion with the independent agents and is not based upon the unilateral exercising of power. In this context, the decisions

are made by the individual functional agents and the

overall success depends upon the integration of these

decisions. The project manager basically monitors the

interfaces, mediates conflicts, and negotiates equitable

trade-offs among the various agents [3]. The basic

behavioral recommendation in this philosophy is to

establish cooperative alliances both among the individual agents and between an agent and the project

manager. This conceptual framework for cooperative

and hegemonic relationships is the basis of our proposal for automating the cooperative problem-solving

among the Electric Power System, its consumers, and

the the station's operations manager.

1.2.2 The Paradigm Applied

The various agents for Space Station Freedom can be

organized into three categories: 1.) the operations

management agent--OMS 1, 2.) resource managing

agents--those which supply basic resources throughout the station, and 3.) resource requesting agents--

those who plan to use the resources to perform other

functions. Under the project management concept,

each agent is allowed to make all the decisions about

controlling any of the activities under his purview. Resource requesting agents .will plan activities according

to what is considered an acceptable discharge of their

responsibilities. This action will request resources to

be supplied by the resource managing agents who organize to support the desired activities.

Conflicts arise when more resources are requested

than can be supplied. Rather than have the operations management agent decide directly which tasks

1OMS--the Space Station Freedom's Operating Management System--performs the automated coordination of syst_rr_

and payloads

will be performed and which will be curtailed, the resource managing agent with the conflicts should negotiate with the resource requesting agents to develop

mutually acceptable allocations. The idea is to increase the span of control of the individual agents

and to reduce the number of layers in the management hierarchy [3]. The elimination of intermediate

hierarchies and direct micro-management should simplify automating resource allocation. Of course, to do

all this, the participants will need some knowledge of

what constitutes good and bad operation from the operations management agent's point of view, and the

operations management agent will have to be concerned with issues of equity among the participants.

This conceptualization requires:

1. A two-level hierarchy. Decision-making agents organized by function who either plan what is to

be done or who manage the required resources

constitute the bottom level. An operations management agent who integrates the decisions and

resolves deadlocks constitutes the top level.

. Explicit value systems. Decision-making agents

use cardinal measures of preference for trade-offs

among different resource consumption tasks to

maximize station productivity and to preserve equity among the resource requesting agents.

. Local constraints. Resource supplying agents

schedule demands using only the constraints in

their own subsystem. Resource requesting agents

plan activities that do not violate any of their operating constraints.

In this type of operation, the resource requesting

agents plan activities that require resources. The operations management agent polls the requestors and

compiles integrated resource utilization schedules and

sends them to the resource suppliers. In general, resource allocation is constrained by the amount of resource available at any instant, the time at which a

resource is needed, and the priority of the need itself.

Choosing a schedule of events that satisfies constraints

implies the ability to use a value system to make the

selections. The value system used rates these decisions according to their impacts upon overall station

operation as well as preserves equity for the participants. These equity notions and preferences for overall station operation are determined by the operation

management agent and communicated to resource requestors who eliminate resource conflicts by using this

preference structure to revise their requests.

We use a free-market concept to organize the cooperative bidding for resources and to coordinate the
RESOURCE

PROFILES

FREE-MARKET

COORDINATOR

TRIAL

PRICES

SUPPLIERS CONSUMERS

POWER

PAYLOADS

THERMAL

LIFE SUPPORT

ETC.

HOUSEKEEPING

LOADS

Figure 1: Free-Market Transaction Cycle

convergence upon an equitable allocation. Using a free

market for the exchange of goods and services provides

a natural and easily comprehended environment for

experimenting with supply and demand.

1.2.3 Free-Market Economic Model

The transactions among our functional agents are coordinated with the familiar concept of a free-market

economy. Shown in Figure 1, the operations management agent, the OMS, acts as a free-market coordinator to mediate conflicts and to provide a top-level

value system. The resource management agents--the

suppliers, are concerned with maximizing the use of

their resource without violating any of their operating constraints. The resource requesting agents--the

consumers, are concerned with generating sets of preferred operating profiles for their desired tasks. Each

of these participants coordinates his actions as if operating in a free-market economy. The free-market

coordinator sets initial trial prices for all the resources

over the planning horizon. The consumers then generate their preferred usage profiles incorporating their

own value systems, the top-level priorities and the resource costs. The suppliers, using their system-level

constraints, evaluate the resource profiles and set fair

prices for each resource throughout the planning horizon. This exchange continues until the fair prices

quoted for each resource equal the trial prices used by

the consumers. This partitioning of constraints and

value systems preserves the notion that each agent is

most interested in and most knowledgeable about his

own part of station operation. An additional advantage of this approach is that it solves one of the most

difficult scheduling problems, inter-system scheduling

requests. Realistically, most consumers will demand

several resources for each operation (any request for

power will contain the hidden request for heat rejection). Most resource schedulers generate solutions for

a single resource and hope to partition the problem

among different schedulers. To us the cooperative approach is more appealing.
2 A Value-Driven Approach

2.1 Generalized Lagrange Multipliers

The theory behind the free-market economic approach

is the Generalized Lagrange Multiplier technique [4].

Everett showed that Lagrange multipliers can be used

to solve maximization problems with many variables

without any restrictions on continuity or differentiability of the function being maximized [5]. While traditional Lagrange multipliers deal with equality constraints and handle inequality constraints with slack

variables, Everett's GLM techniques do not use slack

variables. The goal of GLM is "maximization" rather

than the location of "stationary points" as with traditional Lagrange multipliers. The following is a simplified discussion rather than a rigorous mathematical

description. For such information refer to [5] and [6].

Our approach is to perform an unconstrained maximization of the following Lagrangian:

L(z) -" _i E [Vivljzij - E At¢txlj

• j k

where:

V_ = overall value of the i*h project

vii = relative value of the j,h mode of the i th

project

xq = 1 if project i is performed in mode j

z_j = 0 otherwise

and subject to the constraint

S] -<

i i

where ¢_(zlj) = the amount of resource consumed by mode j of project i

and C_ = the total amount of resource k

available

The I_ values are determined by the operations

management agent--the OMS, and are used to incorporate top-level, station-wide preferences among the

various projects. The vq are the preferences determined by the consumers for each operating option that

they might choose to have scheduled. The key to solving this problem is choosing the Lagrange multiplier.

Instead of solving sets of simultaneous equations to

find Ak at a stationary point, we choose an initial value

for each Ak. This choice corresponds to the trim prices

set by the free-market coordinator. Finding the maximum of the Lagrangian using these assigned values

for A_ will optimize some problem. The issues are to

find what problem was optimized and to adjust ,_k to

optimize the problem at hand. Finding a maximum requires that the objective function be concave" around

the solution point or else the algorithm will skip solutions [5]. Fortunately, most real-world problems either

have an objective function that is concave or can be

made concave in the area of interest.

Our application of the GLM technique follows the

transaction cycle depicted in Figure 1. The consumers

evaluate their options using the trial prices, Ak. They

will choose the option with the greatest overall value

(Yivo -_.k AtCk). The free-market coordinator aggregates each consumer's profile by resource, i.e. all the

power requests over the planning horizon are added

together, all the thermal, etc. These aggregated resource profiles are then sent to the resource suppliers.

The suppliers have their own system level constraints that must not be violated• Some of these

are hard constraints, constraints that must be met

or there is no feasible solution. The total amount of

power available is a hard constraint. Some are soft

constraints, constraints that may be violated, reducing payoff but not producing an infeasible solution.

An optimum battery charging profile that preserves

battery life is a soft constraint. For hard constraints,

the resource demands would be added over the planning horizon; and if there were an excess, the fair

price would be lowered--Ak would decrease. Correspondingly if there were a shortage of a resource, the

fair price--and Ak, would be increased. Most power

system constraints will be soft constraints dependent

upon time-varying factors. Soft constraints are evaluated using penalty functions (Section 2.2). With either type of constraint, the resource suppliers generate

a set of fair prices over the planning horizon.

The fair prices for each resource return to the freemarket coordinator who uses them to modify his next

set of trial prices. He compares the fair price and

the trial price at each time interval and adjusts his

trial price proportionally and according to the sign

of the difference. Since the objective function is concave around the solution point, such an incremental

adjustment of Ak will avoid large oscillations during

convergence.

Another important consideration for optimization

techniques is their ability to handle large problems

without suffering from combinatorial explosion. The

separability of the Lagreingians makes the GLM technique's solution time vary proportional to pqlog(q),

where p is the number of variables and q is the number

of constraints, whereas, standard linear and non-linear

2A function is concave at a point if all values of the function

are less than the values of a line tangent to the function at that

point.
COST'

80

70

60

50

40

30

20

10

0 I

2O

I

30 40 50 60 70 80 90 100

% BATTERY CHARGE

Figure 2: Cost Function

techniques vary porportional to p2q [4]. For large applications such as Space Station Freedom, this is an

important advantage.

2.2 Penalty Function

For soft constraints we modify the Lagraagian in Section 2.1. Instead of having resources that are strictly

available or unavailable, we have resources whose price

increases with scarcity and decreases with abundance.

We control the usage of such a resource with a penalty

function so that we avoid operating at extreme supply

levels. This leads to the following equation:

L(x) = _-_Vivijxij )- Pj(y)dy

3

where yj(z)= _-']_iC/(zi)

YJ (z)--the amount of resource j used

The penalty function, P)(y), is a non-linear function. Integrating PJ(Y) over resource consumption Yi

generates a cost function such as shown in Figure 2

for battery charge. This cost function is used to generate the fair price quoted to consumers--prices which

will coerce the consumers into changing their preferred

project profiles.

Each soft constraint will be represented by its own

penalty function and cost function. Figure 2 depicts

percent of battery charge as the constrained resource.

For this particular case, there are appropriate intervals

where the battery state-of-charge is known and can be

compared to desired values. At the end of the orbit's

sunlight portion the battery should be fully charged.

To determine the cost of power for a given sunlight

portion, the energy demand is calculated and used to

determine the battery state of charge. The cost function supplies a fair price for power usage during that

sunlight portion. Correspondingly, at the end of the

orbit's eclipse portion the battery depth of discharge

should not exceed 35%. After calculating the energy

demand over the eclipse portion and determining the

battery depth of discharge, the cost function will supply a fair price for power for that eclipse portion.

2.3 Value Functions

For this scheduling algorithm to satisfactorily allocate resources among consumers, the values Vi and vii

must simulate the human managers' preferences for
choicesamongalternatives.Aspreviouslydiscussed,

the station-widevalues(V/)arepassedto the consumersandusedin theirdeliberations.Thestationwideimportanceof anoptioncanbemadeafunction

of timeandusedto represent urgency.

Projectmanagershavetwobasictypesofcriteriafor

judgingwhentoscheduleaproject;therelativeimportance of that project and the urgency of project completion. The relative importance would most likely be

a numericM value, whereas the urgency would be more

like a rate. The value function might be represented

mathematically as follows:

V(t) = V0. e°'

where V0 represents the importance factor and a represents the urgency factor.

The placement of a project in the schedule would

depend on both its importance and relative urgency

for the time periods in question. The value function

could be used to indicate the urgency of continuing a

relatively low-importance experiment that is very near

the completion of a several day operation. The concept of urgency being applicable for specific time periods in an orbit or mission is something intuitahly

obvious but not necessarily easy to implement. In

the GLM technique additional equations representing

time-dependent value functions do not complicate the

solution because of the separabilty of the Lagrangians.

Each consumer will still evaluate his project's options,

choosing the one with the greatest overall value, only

his method of calculating that value will include timedependent factors rather than a single value for the

entire project.

22nd Intersociety Energy Conversion Engineering

Conference, AIAA 1,499-508 (1987).

[2] J. L. Dolce and K. A. Faymon, "Automating the

U. S. Space Station's Electrical Power System,"

in Optical Engineering, 25(11), 1181-1185 (Nov.

1986).

[3] D. I. Cleland and W. R. King, Systems Analysis and Project Management, McGraw-Hill, New

York (1975).

[4] G. Pugh, "A Value-Driven Electric Power Scheduler," DSA Report 977, (July 21, 1989).

[5] H. Everett, "Generalized Lagrange Multiplier

Method for Solving Problems of Optimum Allocation of Resources," in Operations Research, 11(3),

399-417 (May-June 1963).

[6] G. Pugh, "Lagrange Multipliers and the Optimal

Allocation of Defense Resources," in Operations

Research, 12(4), 543-567 (July-August 1964)

3 Goals

A design prototype will be available in the summer of

1990. This prototype, using a 386 machine, OS/2 and

Presentation Manager, will depict these concepts for

Freedom's electric power system and a few representative consumers. We will use this prototype to solicit

evaluations of our approach from the Space Station

Freedom community. Our long term goal is to incorporate a more detailed version of this software into

the Space Station Power System Test-bed. This testbed work will provide a foundation for Space Station

Freedom's operation as a distributed yet cooperating

collection of entities.

References

[1] J. L. Dolce, "An integrated approach to space station power system autonomous control," in Proc.
National Aeronaulics and Report Documentation Page

Space Admintstration

1. Report No. 2. Government Accession No, 3. Recipient's Catalog No.

NASA TM- 103149

5. Report Date 4. Title and Subtitle

Electric Power Scheduling: A Distributed Problem-Solving Approach

7. Author(s)

Pamela A. Mellor, James L. Dolce, and Joseph C. Krupp

9. Performing Organization Name and Address

National Aeronautics and Space Administration

Lewis Research Center

Cleveland, Ohio 44135-3191

12. Sponsoring Agency Name and Address

National Aeronautics and Space Administration

Washington, D.C. 20546-0001

6. Performing Organization Code

8. Performing Organization Report No.

E-5503

10. Work Unit No.

488-51-03

' 11. Contract or Grant No.

13. Type of Report and Period Covered

Technical Memorandum

14. Sponsoring Agency Code

15. Supplementary Notes

Prepared for the 25th Intersociely Energy Conversion Engineering Conference cosponsored by the AIChE, SAE,

ACS, AIAA, ASME, and IEEE, Rend, Nevada, August 12-17, 1990. Pamela A. Mellor and James L. Dolce,

NASA Lewis Research Center. Joseph C. Krupp, Decision Science Applications, Inc., 1110 Glebe Road,

Arlington, Virginia 22201.

16. Abstract

Space Station Freedom's power system, along with the spacecraft's other subsystems, needs to carefully conserve

its resources and yet strive to maximize overall Station productivity. Due to Freedom's distributed design, each

subsystem must work cooperatively within the Station community. There is a need for a scheduling tool which

will preserve this distributed structure, allow each subsystem the latitude to satisfy its own constraints, and

preserve individual value systems while maintaining Station-wide integrity. The value-driven free-market

economic model is such a tool.

17. Key Words (Suggested by Author(s))

Scheduling

Planning

Resource allocation

18. Distribution Statement

Unclassified- Unlimited

Subject Category 63

19. Security Classif. (of this report) 20. Security Classif. (of this page) 21. No. of pages 22. Price*

Unclassified Unclassified 8 A02

NASAFORM1626OCT86 * For sale by the National Technical Information Service, Springfield, Virginia 22161


National Aeronautics and

Space Administration

Lewis Research Center

Cleveland, Ohio 44135

Official Buslnell=

Penalty for Private Use $300

FOURTH CLASS MAIL

ADDRESS CORRECTION REQUESTED

IIIIII

P()slage and F_es Pa_d

Nat (_)Ral A_r()rTatJhr:A _:lr_

Spar:e t_dr'r_n_s!rat )r7

T'qASA 451

IW_,SA