Optimization-Based Methods For Operations Scheduling PDF

Optimization-Based Methods for Operations
Scheduling
The operations scheduling problem in electric power systems is schedule of the thermal units is also influenced by pre-
to determine which generating units should be on-line and avail- ventative maintenance schedules, nuclear refueling sched-
able for generation at each hour and the associated nominal gen-
eration or dispatch. This paper describes the scope of the opera-
ules, or long-term fuel contractswhich involve making deci-
tions scheduling problem, presents mathematical formulations to sionson ayearlyor multi-yeartimeframe. Hydroscheduling
the problem, and surveys recent advances in optimization-based also, in general, involves a yearly or multi-year time frame
solution methods. It i s mainly concerned with the shorter term due to thelarge capacity of many hydro reservoirs. Many
aspects of the problem where the time horizon is of the order of a
hydro or pumped hydro reservoirs have daily or weekly
week. The unit commitment, short-term hydro scheduling, and
hydro-thermal coordination problems as well as solution methods cycles. Typically,the commitmentand generatingschedule
are emphasized. is output on an hourly basis.
Although yearly or multi-year factors influence opera-
I. lNTRODUCTlON tions scheduling, the schedules actually produced are often
useful for just several hours. This is becausethe scheduling
Operations scheduling in the electric power industry requires forecast of many stochastic quantities such as
concerns the scheduling of a utility's generating facilities. loads, hydro inflows, and unit availabilities. If theactual val-
By scheduling, we are concerned with deciding which gen- uesof thesequantitiesdiffer greatlyfrom theforecasts,then
erating units should be on-line (committed) and available it is economical to resolve the operations scheduling prob-
for generation, the units'associated nominal generation or lem. (lheoretically, a policytablecould begenerated giving
dispatch, and,for units that can burn multiplefuels, which the scheduledependingonvarious"statevariab1es"which
fuel to use. Most utilities have several sources of power define the past history of the system-a typical state vari-
including thermal plants (steam, gas turbines), hydro and able would include the reservoir storages and the avail-
pumped hydro plants, interchange with neighboring util- abilityof all the units. However, thisapproach is impractical
ities, dispersed generation (e.g., wind power or photovol- since the state space would be extremely large.)
taics), etc.In addition, many utilities use load management Since the determination of hourly hydro and thermal
to influence the load thereby affecting the amount of gen- schedules over a period of several years is unrealistic and,
eration required. asdescribed above, unnecessary, past approaches (e+., [19],
The scopeof theoperations schedulingproblem will vary [21], [MI, [71])have developed a hierarchical approach tothe
stronglyfrom utilitytoutilitydependingontheirmixofunits overall operations scheduling problem.A typical hierarchy
and particular operating constraints. i s shown in Fig. I . The Maintenance Scheduler solves for
The economic consequences of operations scheduling thetime forpreventive maintenanceof thegeneratingunits.
are very important. Since fuel cost is a major cost com- Typically, weekly schedules aregenerated over a period of
ponent, reducing the fuel cost by as little as 0.5 percent can one to three years. The Maintenance Scheduler coordi-
result in savings of millions of dollars per year for large util-
ities.
The time horizon ofoperations scheduling depends on LONG-TERM MAINTENANCE
a number of factors. Large steam units take several hours HYDRO SCHEDULER
SCHEDULER
to start u p and bring on-line. They also haveminimum up-
and down-time constraints and startup costs which require
that they be scheduled over a period of several days. The
SHORT-TERM
HYDRO
COMMITMENT
SCHEDULER
Manuscript received September 19,1986;revised August25,1987.
The authors are with Systems Control, Inc.,Palo Alto, CA 94304,
USA. Fig. 1. Typical hierarchy for overall operations scheduling
IEEE Log Number 8717880. problem.
0 1987 IEEE
0018-9219/87/12W1574$01.00
PROCEEDINGS OF THE IEEE, VOL. 75, NO. 12, DECEMBER 1987

1574Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.
nateswith thelong-Term HydroSchedulerwhich produces startup fuel costs are usually considered afunction of the
hydroschedulesoverthesametimeframe.Thisinsuresthat numberof hours theunit has been down at startup.
the hydro energy is available, as rlkeded, to replace units Startup costs can be written
down for maintenance. The long-term maintenance and
ST, = TS, * F, + (1 - exp (-Dj/ASj)) . BS; f; + MS, (3)
hydro schedules are inputs to the Unit Commitment and
Short-Term Hydro Schedulers. UnitCommitment pro- where TS, is the turbine startup energy (MBTU), D, is the
duces commitment and generationschedules for the ther- number of hours the unit has been down, ASj is the boiler
mal units while theShort-Term Hydro Scheduler produces cooldown coefficient, BSi is the boiler startupenergy, and
generation schedules for the hydro units. The combined MS; is the startup maintenance cost.
Unit Commitmentand Short-Term Hydro scheduling prob- Unit Constraints: The thermal units are subject to avari-
lemoften.referred to as the short-termhydro-thermal ety of unit constraints. Minimum up-times specify the min-
scheduling problem, produces hourly schedules over a imum time a unit must be up before it can be shut down;
period of several days. similarly, minimum down-times specify how long a unit
Modern energy management systems often include unit must bedown before itcan start up. Unitscan onlygenerate
commitment and, if appropriate, short-term hydro sched- between given limits. Also, many units have ramp rate limits
uling programs. These programs are run, at a minimum, which specify the amount aunit’s generation can increase
daily to schedule the generating units ofthe systems. Dif- or decrease in an hour. In addition tothese unit constraints,
ferences between actual and forecasted loads, hydro for selected hoursof thestudy period, units may be unavail-
inflows and/or unit availabilitywill requirethat the imple- able (due to planned maintenance or forced outages), or
mented schedules differ from theones generated by com- derated (reduced generating limits), or required to operate
puter programs. Largeerrors betweenforecasted and actual at prespecified generation levels.
datawill oftenrequire thatthe unit commitment and hydro Unit TypexThe thermal units are usually divided into the
scheduling programs be rerun several times during a day. following unit types: must-rununits,cyclingunits, and
Thispaperwill bemainlyconcernedwiththeshorterterm peakers. Must-run unitsarethose unitsthat must beon-line,
aspects of operations scheduling. Methods for unit com- if available, due to operating constraints, reliability require-
mitment and hydro scheduling will be described in detail; ments, or economic considerations. Cycling units are units
extensions to consider fuel constraints, losses, and trans- that can cycle on and off and are subject to minimum u p
mission constraintswill also be described. The hydro-ther- and down-time constraints. Both must-run and cycling units
mal coordination is presented in the hydro scheduling sec- are dispatched economically between theirminimum and
tion. The paper will concentrate on operations scheduling maximum limits. Peakers are units (usually gas turbines)
methods that have been developed into production pro- thatcanstartupquicklyandaretypicallynotsubjecttomin-
grams and which are based on optimization methods. imum up- or down-time constraints. Many utilities require
that peakers, when dispatched, operate at their uppergen-
II. UNIT COMMITMENT erating limit.
Plant Crew Constraints: Thermal plants may have limits
A. Problem Description on the number of units that can be started or shut down
The Unit Commitment Scheduler calculates the mini- in a given hour due to manpowerlimits.
mum cost hourly generation schedule ofthe thermal units Generation Requirement:The generation requirement,if
for a period of up to one week. The schedule is obtained we ignore losses and transmission constraints,can be writ-
considering many factors including: ten
unit operating constraints and costs G;(t) = GR(t) (4)
i
generation and reserve constraints
plantstartupconstraints. where CR(t), the generation requirement at time t , is the
load minusthe sum of net interchange, hydro generation,
Unit Costs: Generating costs typically include fuelcosts,
and other generation(includingcogeneration, net pumped
maintenancecosts, and startupcosts. Thefuel cost for gen-
storage generation, etc.). The effect of losses on the gen-
erating at G; megawatts for uniti can be represented bythe
eration requirement is described in Section Il-C.
equation
Spinning and Supplemental Reserve Requirements: Most
FC;(G;)= F; * Hi(G;) (1) utilities have a spinning reserve requirement which spec-
ifies the amount of on-line generation capacity, in addition
whereH;(G,)istheheatratecurvefortheunit(MBTUlh)and to what is needed to meet the generation requirement, in
f,is the unit’s fuelcost ($/MBTU).The heat rate curve is mod- order to meet random disturbancesto the system such as
eled differently by different utilities. Typical representa- the forced outage of a unit or unforeseen load changes.
tions use polynomial curves (up to fifth order)represent
or Many utilitiesalso have a supplemental reserve requlre-
the incremental heat rate curve as piecewise constant or
ment which specifies that amount of additionai reserve that
piecewise linear. The maintenance cost is typically repre- must be available to the system; however, the system has
sented in the form a longer time to provide this reserve than the spinning
MC,(G,)= BM, + /Mi . G; (2) reserve requirement. Off-line peakers are usually allowed
to contribute to supplemental reserve.
where BM; i s the base cost and /Mi is the incremental cost. The spinning reserve requirement can be written
The startup cost includes the cost of bringing the unit on-
line. Typical costs that are included are startup fuel costs, min (GSP, - Gj(t), SP,) 1 SPRES(t) (5)
on-line
startup maintenancecosts, and turbine startup energy. The units;
COHEN AND
Authorized licensed
SHERKAT: use limited to: Universidad
OPTIMIZATION-BASED METHODS
de La Salle.
FOR Downloaded August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.1575
on SCHEDULING
OPERATIONS
where GSP; is the capability
limit,
for the unit,
that can be w !J Y
supplied to spinning reserve and SP, is the maximum con-
tribution
spinning
to reserve for the unit. The supplemental 1.2.3 (1,1,1) o----,-,,oo, 0
reserve requirement is 2.3 (0.1.1) 0 \
units; peakersi
(6)
where GSU; is the capability limit of the unitthat can con-
tribute to supplemental reserve. The unit limits GSP, and
GSUiaredifferentiated becauseutilities havedifferent rules
for determining contributionsto the two reserve require-
0 (0,O.O)
ments. The limits SPRES(t) and SUR€S(t) may be afunction
ofthegeneration requirement, largestavailableuniton-line, TIME = T TIME= T + I
orsomeotherfactor.Anycontributionfrom hydro, pumped Fig. 2. Example dynamic programming
state space for three
hydro, other sources of generation, interchange, or load cycling units.
management, would besubtracted fromthespinning
reserve requirement of the thermal units. is
Unit Commitment Problem: The unit commitmentp r o b u(t + I) = u(t)+ v(t)
lem is then to minimize the production cost (sum of fuel,
startup, and maintenance costs) where U(t)= (U,(t),U,(t), U3(t))is a vector of commitments
and Y(t) = (Y,(t), Y,(t), Y3(t)) is avector of commitment
changes.
subject to the unitconstraints, and generation and reserve

requirements. U,{t) is the commitment decision variable
(it is 1 if unit iis on-line for the tth hour and0 otherwise),
andX;(t)isthecumulativeon-time(ifX;(t) > 0)orcumulative
and
uj(t)=
i 1,
0,
ifunit i is committed
otherwise
1, iftheunit is started up
off-time (if X,(t) c 0). at end of time t
0, ifthe status ofthe unit
6. Solution Methods Y;(t) =
is not changed
The unit commitment problemis a very large nonlinear
-1, iftheunit is shut down
mixed-integer programming problem. For a system of 100
at end of time t .
units, and a time horizonof oneweek, there are over 30 OOO
decision variables. At the present time, thereis no method For reasonswe will discuss, the unit
commitment prob-
that solves the unit commitment problem exactly for large lem requires an approximate forward dynamic program-
problems. ming approach. In this method, thefollowing iterative
Many methodshave been developed for solving the unit equation is solved:
commitment problem.An excellent survey of earlysolution
methods (through 1975), including heuristic methods, is
lfU(t), t) = min {/(g(U(t),Y(t - I)), t - 1)
Y
given in [271.The optimization-based methods for unit com-
mitment have been based on a number of approaches t) + sTc(Y(t - I))}
+ oc(u(t), (8)
including dynamic programming, Lagrangian relaxation, where
integer programming, branch and b w n d methods, and
Benders decomposition. These methods combine mathe-
Ut) ={ u,(n}the vector of commitments,
vt) = { Y ; ( t ) } the vectorshutdown,
of
matical programming approaches with certainapproxi- startup decisions,
mations and assumptions to make the problem tractable.
g(U(t),Y(t - 1)) the backward transition equation:
Dynamic programmingand Lagrangian relaxation have
been used extensively to develop production-grade unit U(t - 1) = U(t) - Y(t - 1)
commitment programs-these methods will therefore be
Wt), t) optimum cost from start totimetwhen
described in some detail; the other methods will then be ending in state U ,
described briefly.
Dynamic Programming: The dynamic
programming
oc(u(t),t) fuel
andmaintenance cost at time t
assuming each unit is in state U,(t),
approaches [Iq, [26], [30], [34], [35] have been around the STC(Y(t - 1) startup cost givendecision Y(t - 1).
longest. In these methods the state space consists of the
commitment status of all the cycling units. Since the com- The calculation of the fuel and maintenance cost OC(U(t),
mitment status of themust-run unitsis known, theydo not t) requires solving the economic dispatch problem since
have to be put into the state space.'Most methods treatthe the commitment U(t) is known. The economic dispatch
commitmentof the peakingunits as a special case as problem involvesminimizingthefueland maintenancecost
described later. subject to the unitgeneration limits and
the generation and
Fig. 2 shows the state space for the case of three cycling spinning reserve requirements. Economic dispatch meth-
units and some example transitions. The dynamic equation ods are discussed in the Appendix.
1576Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 18:50:21OF
PROCEEDINGS
atIEEE, UTCTHE
from IEEEVOL. NO. 12, DECEMBER
75, Restrictions
Xplore. apply. 1987
in (8) is straightforward. The
Solving the iterative equation M is related to thesum of the minimum upand down times
initial condition is and the timeconstant in thestartup cost calculation (a t y p
ical value of Mwould be 10). Including theaccumulated up
/(U,
To) = 0, for U = Uo and down time in thestate space is, therefore, unrealistic
even if we reducethe decision space using one of above- the
/(U, To) = a ~ , for all U # Uo
mentioned procedures. Instead, an approximate forward
where To i s the timeat the start of the study andUois the DPapproach is used wherebythe cumulative upldown time
actual state of the system corresponding to the unit status associated with each stateis calculated. This up/down time
at time To.Given / ( U t - 11, t - 1)at hour t - 1, for all states corresponds to the optimaltrajectory to this state. The DP
U(t - I), thecalculation of /(U(t),t)involves determiningthe will onlyallow transitionsY(t)that will notviolate any of the
fuel and maintenance cost OC(U(t),t) and then performing minimum u p and down-time constraints. To be precise, in
the minimization (8) in for all transitions to state U(t).Please calculatingwhich start-stopdecision Yisoptimumfor state
refer to [I] [,lll, [I21 for a more detailed discussion of U , in (8), wealso calculatethecumulative upand down time
dynamic programming. based on thecumulative up and down time of the previous
The state space (the number of different values of U at state (corresponding to the optimal trajectory to this state)
a given time) can be quite large. For a system having only and the decision Y. If the new cumulative up or down time
10 cycling units, the size of the state space is 2” which is does not satisfy the minimum up-or down-timeconstraint,
1024. Calculation of these many economic dispatches for then we assign an infinite cost to that transition.In this way,
168 h woulduse a large amount of computerresources. In the forwardDP solution willbe feasible. The cumulative up
reality, all these dispatches do not have to be evaluated and down times are also used in the startup cost calcula-
because someof these stateswill be infeasible (either they tions. It is important to note that thisis an approximate pro-
have insufficient generating capacity to meet the supple- cedure and it involves some loss of optimality.
mental reserve or the minimumgeneration of the on-line As mentioned earlier, some methods treat the dispatch
units exceeds the generation requirement). However, for of peakers as a special case. The rationale for this is that
typical systems, the number ofstates is still very large. For peakers have relatively small startup cost and generation
this reason, implementations of these methods make cer- capability and typically do not have any minimum u p or
tainapproximations which drasticallyreduce the state down-time restrictions. They, therefore, can be used for
space. One approximation [26] is to assume the units will short time periods to supply generation. Therefore, even
be committedand decommitted ina certain priority order. though their marginal cost may be much higher than a
This priority order is a functionof the units’operating and cycling unit, it may be more economical to use a peaker
startup cost. In this case, the units on-lineare completely because the cycling unit may supply much more energy
determined if one specifies the last unit to be committed than is required or may have to be on for a much longer
in the priorityorder. If there are 10 cycling units, then the period than is required. It, therefore, may be difficult to
maximum state spacewould be 11-obviously much smaller specify where to place the peakers in the priority ordering
than 1024. (this is especially true ofthose methods that require a strict
Users have noticed that this approachcan lead to loss of priority ordering). Hence,some methodsdispatchthe
optimality since the optimal use of the units may depend peakers separatelyfrom the cycling units. A separate prior-
on the relative size of the units (a large unit may be com- ity list is maintained of justthe peaking units. Referringto
mitted when only small a unit is needed) and on theeffect the formulation above, the state U(t) justcontains the
of startup cost (it may be best to use a unit with large startup cycling units.Then when evaluatingthe operating cost OC
cost all the time in one case and not at all in another). There- corresponding to a given state, it is determined ifpeakers
fore,other approaches have been developed. These are necessary to meet the generation or reserve require-
approaches still depend on a priority ardering. A typical ments. If so, these peakers arecommitted according to the
approach [%I, [35] determines some nominal Commitment, priority order until the generation and reserve require-
for each hour, which is determined to be good-choices ments are met. Peakers will also be committed if they will
that have been used are 1)the minimum numberof units, reduce the operatingcost.
in the priorityordering, needed to meet the reserve con- LagrangianRelaxation:TheLagrangian Relaxation a p
straints and 2) the result of the above priority list optimi- proaches [231, [291, [31], I331 nofe that the unit commitment
zation. A set of units, in the priority list, about the nominal problem can be written in terms of 1) a cost function that
commitment are then chosen for optimization-the units is the sum of terms each involving a single unit, 2) a set of
below (higher priority) that set are assumed to be com- constraints involving a single unit, and 3) a set of coupling
mitted while the units above that set are assumed to be off. constraints (the generation and reserve requirements), one
If this set contains 5 units, then thestate space sizeis 2’or for each hour in the study period, involving all the units.
32which is a reasonable number. Other methodsforchoos- Formally, we can write the unit commitment problem as
ing the set of units to consider, each hour, are described follows:
in[x]. minimize C C lj(ci(t),
ui(t))
Up until nowwe have ignored the time-dependent nature t I (9)
of the startup costs and the minimum u p and down-time
constraints. To include these constraints and costs in an subject to the unit constraints
optimal manner in theDP approach, we would have to also Li(Gi, U ; ) I0 (10)
include theaccumulated up and down timeof the units in
the state space. Therefore, instead of a state spaceof 21° for for all units i f where G; = (Gi(l), * , Ci(T))and Ui =
the 10 unit cases we would have a state spaceof MIowhere (Ui(l), * ,U,(T));and thecoupling generation and reserve
COHENANDSHERKATOPTIMIZATION-BASEDMETHODS FOR OPERATIONSSCHEDULING 1577

Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.
constraints where G:W, U:(t) are the solution to the relaxed problem
with multipliers y,(t). That is, the derivative of the Lagran-
gian corresponding to a change in y , ( t ) is equal to the dif-
ference betweenthe requirement andthe value of the left-
for all times t and requirements n. Everett [4]showed that hand side of the constraint evaluated at the solution of the
an approximate solution to this problem can be obtained relaxed problem. The subgradient method to update y,(t)
by adjoining the couplingconstraints onto the cost using is
Lagrange multipliers. The resulting "relaxed" problem is to
minimize the so-called Lagrangian
where y i ( t ) is the kthupdate ofy,(t) and ak is a step length

subject to the unit constraints (IO),where y,(t) are the mul- given by
tipliers associatedwith the nth requirementfor timet. Since
-the cost function can be written as a sum of terms each
ak = l/(c + d * k) (16)
involvingonlyoneunit,andeachoftheconstraintsinvolves where c and dare constants. Different constants would be
one unit, this problem can be solved by a sequence of prob- given for the different requirements. Other forms of a'
lems each involving a single unit. could be used as long as ak -+ 0 as k 03 and +
Describing the Lagrangian relaxation method requires 0)
answering the following questions: 1) how dowe find the C ak -+ m.

k=l
multipliers y,(t) so that the solution to therelaxed problem
is near the optimum, 2) how close to the optimum is the
solution, and 3)how dowesolve the relaxed problem?Ever- Lauer et a/. [29]use a different approach to minimizing
ett [4]and dualitytheory [A, [IO]give us insight to the first the dual function that uses second derivative information.
two questions. Everett shows that if we solve this relaxed Different authorsuse variations of the above Lagrangian
problem, with any sets of multipliers y,(t), and the right- methods to ensure that the generation andreserve require-
hand side evaluates to R:(t); that is, ments are met and that the algorithms converge to near
optimal solutions. These variations include replacing the
spinning and supplemental reserve requirements by con-
straints that just involvethe units' upper limits, and using
where G:(n and U : ( t ) are the solution, then G:(t), is u:(n modifications to the subgradient formulas. Please refer to
the optimum solutionof the original problem with REQ,(t) [23], [?9], for[31]details of these methods.
replaced by R,*(t). Therefore, if we could find y,(t) so that The single unit relaxed problem i s to minimize
the resultingR,*(t)were equal to REQ,(t) we would achieve
our objective. Unfortunately, this cannotalways be done.
Duality theory has shown that for nonconvex problems [li(ci(t),u m - m ( t ) R,,,(GA~),u,(t))] (17)
there will typically be a "duality gap" between the cost subject to the unit limits
obtained by solving the relaxed problem and the optimum
cost for the original problem.Since the commitmentdeci- GL, I C,(t) I CU,, if U,(t) = 1 (181
sion variables U i ( t )are discrete, the unit commitment
prob
G;(t) = 0, if U , ( t ) = 0 (19)
lem is nonconvex. The duality gap, however, has been
shown [29]to go to zero as the problem size gets bigger. and the minimum u p and down-time constraints
For large problems, the dualitygap is less than 0.5 percent
~91.
U,(t) = 1, if 1 I X,(t) < MNUP, (20)
Duality theoryalso gives us some information on how to U,(t) = 0, if -MNDN, < X,(t) 5 -1 (21)
change the multipliers m ( t ) so that the solution to the
relaxed problem is near the optimumsolution. Let D(y,,(t)) where X,(t) is the cumulative up time if X,(t) > 0 and the
be the value of theLagrangian at the solutionto therelaxed cumulative down time ifX i ( t ) < 0. MNUP, and MNDN, are
problem, then good values of the multipliers m ( t ) can be the unit's minimum up and down times, respectively. X,(t)
obtained by maximizing D(y,(t)) for all positive y,(t). Basi- can be relatedto U j ( t )bythe followingdifference equation:
cally, two approaches have been used to maximize the dual r
function D( ). The first [IO], [23], [31]involves using the

subgradient method. This is a generalization, for nondif-
ferentiable functions, of the gradient or steepest descent
method ( D is, in general, nondifferentiable). First note that
thesubgradientofD()withrespecttooneofthemultipliers if X,(t) 5 1, U,(r) = 0.
y,(t) is
(22)
This formulation leads naturallytoadynamic programming
solution approach. The state variables are just X,(t). The
number of required upstates is MNUP, and the number of
1578
Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 at 18:50:21 O
PROCEEDINGS F THE
UTC from IEEEVOL.
IEEE, 75, Restrictions
Xplore. NO. 12, DECEMBER
apply. 1967
required down states is max(MNDNj, COOLi)whereCOOLi on the branch-and-bound tree. Three methods appear in
is the time required for a unit to cool down
completely so the literature. Dillon eta/. [25] and Pang eta/. [42] formulate
that the startup cost i s independent of down time for down the unit commitment problem as a linear mixed-integer
times greater than COOL,.The allowed state transitions are programming problem and then use standard integer pro-
shown in Fig. 3. Classical dynamic programming can now gramming algorithms to solve for the commitmentsched-
be used to solve the single unit problem. ule. In this approachthe cost function and constraints are
written as linear functions of the generation and commit-
ment decision variables. The commitment decision vari-
UP 3 ables aremodeled as having the values 0 and 1correspond-
2
STATES ing to a unit beingoff or on at a given time.The relaxation
I
-1
corresponding to the topnode of the decision treeallows
-2 all the commitment decisionvariables to take on any value
DOWN -3 in the interval[0,I]. Each descendant of a node corresponds
STATES -4
-5
to restricting some of the commitment decisions to 0 and
-6 1. The problem at any node of the treeis a linear program-
-7 ming problem whichcan be solved using a modern linear
-8
programming package. Dillon et a/. [25] describe several
TIME =T TIME = T* I
problemapproximations and extensions tothe basic
Fig. 3. State transitions for single-unit dynamic program- branch-and-boundalgorithm thatwereneeded to make the
ming [27.
solution approach tractable for this problem.
Cohen and Yoshimura [24] formulate the problem as a
Other Solution Approaches: Several authors have used nonlinearmixed-integerprogramproblem. They define
branch-and-bound methodsto solve the unit commitment start and stop intervals foreach unit which limits the hours
problem. Branch-and-bound is a technique tosolve a dis- a unit can start up or shut down for each day. At the top
crete variable problem by solving a sequence of simpler node thestart and stop intervals for the units are the entire
problems derivedfrom the originalproblem. The searchi s day. The successorsof this node restrictthe start and stop
organized via a branch-and-bound tree. The top node on intervalsforoneunittobeasubsetoftheday.Thenextleve1
the tree is a relaxation ofthe problem(typically the integer of nodes restricts the start and stop intervals for the first
constraints are replaced by interval constraints) thatis rel- unit further.This restriction continues until,at the bottom
atively easy to solve. The successorsof the top node are a set of nodes, the start and stop intervals each consist of a
set of problems (also relaxations of the original problem) single hour. They use an economic dispatch algorithm to
each having a disjoint solutionspace; the unionof the solu- obtain lowerboundson the solution corresponding to each
tion spaces of these successors is the solutionspace of the node. Since each day is considered separately, they have
top node problem. Each of these ,nodes is also separated to use a heuristic approachto couple theschedules for sev-
into a set of problems with disjoint solutionspaces having eral days. They do not discuss how they would deal with
the property that the union of the solution spaces is the the case where the units start and stop more thanonce in
solution space of the parent node. This process is repeated a day.
until the solutionspace for the endnodes of the tree con- Lauer et a/. [29] as well as Mucstadt and Koenig [33] pro-
sists of an enumeration of all the discrete variables. Since pose using branch-and-boundalongwith Lagrangian relax-
the solution space of the parent node is a relaxation of all ation to reduce the “duality gap” in the Lagrangian relax-
the successor nodes, the optimum solution of the parent ation approach. This isa natural approach since maximizing
(assuminga minimization problem) must be lower thanthe the dual function D( ) with respect to nonnegative y J t ) is
solution ofany of the successors. Therefore, the optimum a lowerbound onthe solutionto the original problem. The
solution of the parent (or a lower bound on that solution) branch-and-bound treeis formed, at each level, by restrict-
is a lower bound on any descendant node. The basic idea ing some of the commitment decision variables to be 0 or
of branch-and-boundis that if, at anytime in the procedure, 1.
one obtains a solution the of problemat a node (or a lower Recently, Habibollahzadeh and Bubenko [28] havedevel-
bound on the solution) thatis greater than aknown feasible oped a methodbased on Benders decomposition. Benders
solution to the original problem, then all feasible solutions decompositionrequiresthattheunitcommitmentproblem
corresponding to descendants of that node are known to be formulated as a mixed-integer linear programming prob-
be nonoptimal. It, therefore, is unnecessary to evaluate lem. Bendersdecomposition is a way to decompose the unit
these descendant nodes. Defining the branch-and-bound commitment problem into master a problem involving only
method requires defining 1) the problems in the branch- thediscrete commitment variables and a subproblem
and-bound tree, 2) the methodof solving each problem in involving the continuous generation variables. The sub-
the tree, and 3) the method of searching the tree. The problem corresponds to the economic dispatch problem
branch-and-boundtree is completelydescribed if one witha givencommitment. The marginal costs(system
defines the problemcorresponding to the topnode of the lambda), for each hour, from the subproblem are used to
tree and the method ofobtaining the successors of any node constrain the allowed commitmentsin themaster problem
(thismethod is called the separationrule). More back- (this master problem can be decomposed into a sequence
ground onthe branch-and-bound method i s given in [6] and of problems each involving a single unit). The masterprob-
[I 31. lem provides commitments to theeconomic dispatch prob-
Branch-and-bound can be used with any optimization lem. The master problem and the economic dispatch sub-
approach for solving the problems corresponding to a node problem are solved iteratively until the solutionconverges.
COHENANDSHERKAT:OPTIMIZATION-BASEDMETHODSFOROPERATIONSSCHEDULING 1579
More details on Benders decomposition can be found in lation is to useafirst-order Taylor expansion of theloss term
PI,
[IO], [281, and [67l.
C. Extensions to Unit Commitment

Multi-Area Constraints: Many utilities and power pools (25)
have limits on the power flow between regions of theirsys- where Gf are the generations at which thepenalty factors
tem or limits on the power flow between their system and are calculated. Combining this equation with (23) gives
neighboring systems. Each region may also have separate
spinning or supplemental reserve constraints.
The solution procedures that have been used to incor-
porate multi-area constraints have been based onthe
dynamic programming solutionmethod. The solution pro-
cedure has been to determine a set of units, in each area,
to consider for commitment/decommitment at each hour. or
These units are chosen so that the reserve requirements
GJPF; = GR*
and transmission constraints will be satisfied. A subset of I
the units from all areas is then used for the dynamic pro-
where GR* is the right-hand side of (26).
gramming procedure (using all combinations of unitsmay
Thepenaltyfactorforagivenunitisgoingtobeafunction
require too much computation time).Two methods have
of the specific power flow solution at the optimum dis-
been used to determine the generations and costs asso-
patch, however, it does not change that much for small
ciated with a set of units. Pang et a / . [34] essentially model
changes in load. It i s standard practice to store different sets
the transmission constraints as linear flow constraints (i.e.,
of penalty factors to be used by the unit commitment for
the Kirchhoff’s voltage law is ignored). The resulting con-
different conditions of the system (e.g., load, amount of
strained economic dispatch problem is solved by a heu-
impotdexport, unit availabilities) at each hour.
ristic method; however, nonlinear programming methods
Ramp Limits: Many unitshave limits on the amount their
such as the reduced gradient method or transshipment
generation can change in an hour. The allowed generations
methods [8], [IO] can also be used. VanMeeteren eta/. 1321
in the next hour can be a function of the unit’s current gen-
use a similar approach to that in [34], however, instead of
eration, the number of hours a unit has been on-line, and
ignoring thevoltage constraints, they use a dc power flow
whether the unit‘s generationis increasing or decreasing.
model to relate line flows and bus injections. The coeffi-
Ramp limits are difficult to beconsidered optimally if one
cients of thedc power flow model are set by a power flow
is also going to consider spinning reserve constraints of the
program.
form (5)and losses as in (27).The approachesto ramp limits
Losses: Line losses havebeen ignored so far in thepaper.
in the literature have been limited to the economic dispatch
They canbe quite important in determining the economic
problem where the unit commitments are assumedknown
dispatch. Ifweadd losses, then thegeneration requirement
(see [22], [36], and [41]).These papers also do notconsider
equation, at a given hour, becomes
problems where allthree constraints are present.
c
I
c; = L +
LOSS (23) To the authors’ knowledge, the ramp rate constraints are
usually included in a heuristic manner. This is done by using
where L is the load and LOSS is the losses. Applying the the results of the economic dispatch in one hour to limit
necessaryconditionofoptimality(with/(G,)thethermalcost the generation in the following hour. isIteasy to show that
function for unit i ) gives the following equation that the this approach is suboptimal [36]. Some dynamic program-
optimal generations Gi must satisfy for generations between ming based programsalso have logicwhich insures,foreach
their minimum and maximum limits: hour, that thereis enough ramping capabilityin theon-line
units plus the units being started or shut down tomeet the
change in the load. This is a necessarycondition butit only
solves part of the problem.Proper consideration of ramp-
ing timits i s an important open problem in unit commit-
= X/PF, (24)
ment.
where PF, is the penalty factor for uniti[ I 7 and X is the sys- Fuel Constraints: Many utilities have fuel supply con-
tem lambda resulting from the economic dispatch. The straints that affect the commitment of units. The type of
penalty factor is a measure of how close the unit is to the constraints are varied. Someutilities have gas supplies that
load center. This i s the equation thatis typically used in the are limited or which have take-or-payrequirements. Other
economic dispatch algorithm (see the Appendix). fuelscan belimited due to supply problems, limited storage
Many unit commitment programs use the penalty factors facilities,orother reasons.Theconstraints maybeflowcon-
in calculating theeconomicdispatch but do not include the straints, which can be translated into hourlyconstraints for
loss terms in the generation requirement equation(4).This unit commitment, or they can be constraints for usage over
leads to an inconsistency between the economic dispatch several hours, days, weeks, or months. If some fuels are
problem and thesolution approach. Including losses constrained over a period longer thana week, then a long-
explicitly would require incorporating a load flow whichis term fuel dispatch problem [42], [a], [45] must be solved
not computationally feasible for large problems. One to allocate the long-term contracts to the unit commitment
method of incorporating losses into the problem formu- study period.
1580 PROCEEDINGS OF THEIEEE, VOL. 75, NO. 12,DECEMBER 1987

Adding fuel constraints severely complicates the unit and time-dependent startup costs. Further research is,
commitment problem. For example, a unit that would be therefore, required to determine if this is a viable method
committed for all hours in theabsence of fuel constraints for a range of unit commitment problems.
would havetohave itscommitment limitedif tight fuelcon- Future advances in unit commitment will come in two
straintsare present. For dual-fuel units, several factors areas. First, it is important to findmethods thatcan obtain
influence the dispatch including thecosts fuelof bothfuels schedules that are very close to optimum. The availability
and how the heat rate depends on the fuelused. of cheaper and faster computers shouldmakethis possible.
The optimization methods applied to this problem fall Theother challenge in unit commitment is to include more
into two classes: aspects of the generating system in the formulation. This
includesfindingbetter ways to handle ramp rate con-
methods thatdecompose the problem into a unit com- straints, multi-area constraints, and fuel constraints as well
mitment problemand a fuel dispatch problem that are asspecial unit types suchas dual-boiler unitsandcombined
very weakly coupled [32], [43]; cycle units.
integrated approaches to solving the problem [23].
The decomposition methods can solve fuel dispatch prob- Ill. SHORT-TERM
HYDROSCHEDULING
lems that are quite general involving multiple sources of A. Problem Description
fuel each of which can supply multiple units; however,
decoupling the fuel dispatch from the unit commitment The problem of short-term hydro schedulingis to deter-
problem can lead to commitments thatare farfrom optimal. mine the optimum hourlygeneration (MW) production of
The integrated approach is limited as to the types and num- hydro unitsand, in most applications, other quantitiessuch
bers of fuel constraints that it can consider efficiently but as water flows through generating stations, reservoir
itcan beexpectedtogivecommitmentsthataremuchcloser releases, and storage levels. The objective of short-term
to the optimum. hydro scheduling is to maximize the ”value” of electrical
energy production from hydro, over a scheduling period
of up toone week. The scheduling resolution is typically
D. Summary
1 h; shorter (half-hour) or longer (multiple-hours) resolu-
Dynamic programming was the earliest optimization- tions may also be used.
based method to be appliedto the unit commitment prob- The “value” of hydro energy takes on different forms
lem. It is used extensively throughout the world. Ithas the depending on thecharacteristics of the hydrosystem, and
advantage of being able to solve problems of a variety of the type and mix of generation resources. For an all-hydro
sizes and to be easily modified to modelcharacteristics of or predominantly hydro system, the objective function is
specific utilities. It i s relatively easy to add constraints that typically to maximize the overall hydro energy production
affect operations at anhour (such as area constraints) since or tomaximize the overall efficiency of the system. The lat-
these constraints mainly affect the economic dispatch ter may bedefined asthe ratioof the totalactual gross hydro
problem and solution method.It is more difficult to include energy output to the total potential energy contained in the
constraints that affect a single unit’s operation over time. water discharged through the turbines.For a system with
Thedisadvantages of the dynamic programming areits sales and purchases,the objective function can include the
requirement to limit the commitments considered at any net cost of sales and purchases. The forecasted load and
hour and its suboptimal treatment of minimum up- and other generation requirements are considered as a mini-
down-time constraints and time-dependent startup costs. mum requirement to be satisfied for each time increment
These disadvantages can lead to suboptimal schedules. of the study period.
Lagrangianrelaxation isalso being used regularly by some In a hydro-thermal system, short-term hydro scheduling
utilities. I t s utilization in production unit commitment pro- i s done as part of hydro-thermal coordination. The hydro-
grams i s much morerecent than thedynamic programming thermal coordination problemrequires the solution for the
methods. It is much more beneficial for utilities with large thermal unit commitments and generation dispatch as well
numbers of unitssince the degree of suboptimality (in rel- as the hydro schedules. The objective i s typically to min-
ative terms) goes to zero as the numberof units increases. imize thermalproduction cost subject to meeting the load
It also hasthe advantage of being easily modified to model and other generation requirements. The physical and oper-
characteristics of specific utilities. It is relativelyeasy toadd ational characteristics of the hydroand thermalproduction
unit constraints (such as fuel constraints over the study) system are modeled, as well as other operatingconstraints
since theseconstraints mainlyaffect thesingle unit dynamic (e.g., limits on area interchange). Hydro-thermal coordi-
programming problem(see Section1143). The disadvantage nation is a more complex anddifficult problemthan hydro
of Lagrangian relaxation is its inherent suboptimality. scheduling for a purely or predominantly hydro system.
Theauthorsarenotfamiliarwithanyutilitiesthatareusing Almost all of the existingpractical methods for solving the
branch-and-bound or Benders decomposition to obtain hydro-thermal coordination problemare basedon decom-
commitment schedules on a regular basis.Branch-and- position methods involving the unit commitment and hydro
bound methods have only been demonstrated on prob- scheduling subproblems. The overall problem solution is
lems with relatively few units over a short study period. obtained bycoordinating between the solutionof the unit
Benders decomposition has just recently been applied to commitment and hydro scheduling subproblems. The
unitcommitment. It hasthedisadvantageof requiringalin- coordination procedure depends on the decomposition
ear problem formulation.Also, the problem formulation in method used. In some applications, the hydro scheduling
[28] did not directly model minimum up and down times subproblem may be formulated as a short-term hydro-ther-
COHEN AND S H E R K A T OPTIMIZATION-BASED METHODS FOR OPERATIONS SCHEDULING 1581

mal dispatch problem with both thermal and hydro deci- function of reservoir storage content, the hydro unitgen-
sion variables present as part of a single
optimization prob- eration model(28a), (28b) canbe represented as a function
lem. This is the case, for example, when area interchange of the reservoir discharge and storage variables (i.e., the
or minimum generation requirements are present. adjacent upstream, and, when applicable, the downstream
Sincethe state (water content) ofthe reservoirsat the end storage variables). Thus, for example, when no tailwater
of the scheduling period affects future operation, the short- effects are present, (28a) can be written as
term hydro scheduling problem usually includes a target
value for the reservoirs’ contents at the end of the study
PHi(t) = k - g(u;(t),X A t ) , x , ( t + 1)) (29)
period. As an alternative to modeling thereservoir final tar- +
where xi@) and x ; ( t 1) are the storage variables for the
gets as hard constraints, the objective function may be upstream reservoir representingthe storage content at the
appended by aterminal hydrocost which is a function of beginning of time periodrand t +
1, respectively.
the reservoir terminal contents. The target reservoir con- In general, hydro units do not have commitment con-
tentsor the reservoir terminal cost function is usually straints in terms of minimum up or down times as do ther-
obtained from ahigher level (mediumor long-term) hydro mal units. Also, there are usually no costs modeled forhydro
scheduling optimization [71].The terminal hydro cost may unit startup or shutdown.However, in order to discourage
also be modeled as a penalty cost for target deviations. frequent startups and shut-downs and unnecessary plant
In thefollowing, we describe the hydroscheduling prob- output variations, penalty cost terms can be added to the
lem (or subproblem)in terms of the hydrogeneration and objective function to discourage such phenomena. Some
flow models andother constraints normally present as part hydro plants may have a limitation onthe rate of change
of
the
problem formulation. Solution
methods are in plant output (MW) which is due to the physics of the
addressed in Section Ill-B. hydraulic system. The maximum rate of change (increase
Hydro Unit Generation Characteristics;The electrical or decrease) in plant output may be a function of head and
output (MW)of a hydro unitis a function of the water flow other plant loading conditions. One of the most common
throughtheturbine and the net head (thedifference features of hydrogenerating or pumping unitsis their dis-
between the station forebayelevation, and the station tail- creteoperatingcharacteristics which is either dueto
water, or afterbay elevation). In some cases, it may also be restricted loading bands, or due to operating efficiencies
a function of the hydro unit loading combination in the at discrete output levels.
power station. Different models have been used to char- Since the number of hydro units is usually much greater
acterize hydro unitgeneration characteristics as a function than the number of hydroplants, in theshort-term hydro
of flow,head, and other variables. Some investigators have scheduling .optimization problem, hydro generation is
used simple models which ignore head dependence and modeled at the plant levelin order to reduce problem size
nonlinearities. A number ofreferences on the hydro sched- and solution times. In practice, actual unit schedules are
uling problem included in the Reference Section of this normally obtained from a very-short-term (every 5 min)
paper (in particular[471) contain typicalcurves which have hydro economic dispatchoptimization whichuses the gen-
been used to model unit generation characteristics. eration models at the unit level and the prevailing hydro
A general form of the modelis given by conditions.Thevery-short-termproblem reoptimizes hydro
unit generation subjectto hydro plant targets calculated by
PH; = k f(Ui, HNi) (28a) the short-term (hourly) optimization problem.
PMlN; (HN,) IPH; I PMAX; (HN;) (28b) The equivalent hydro plant model for the short-term
problem can be obtainedin several ways. One approachis
where PH; is the hydro unit M W output, uiis the turbine to generate, for each head value, an “optimum” plant gen-
discharge rate (e.g., in cubicmeters per second), and HNi eration curve which is a function of total plantdischarge.
is the net head calculated as the difference between the This requires the solution of a series of hydro economic
station forebay and the station afterbay elevation. k is an dispatch subproblems forthe units within a plant, in order
appropriate unit conversion factor, and i designatesthe unit to generate the plant generation curve in a point-wiseman-
index (theperiod index t has-been omitted for thesake of ner. The objective is to maximize plant generation (or aver-
simplicity). In calculating the net head HN;, some models age output efficiency) subjectto unitoperating character-
also account for head loss which is modeled as a function istics and plantflow constraints. The optimization problem
of theturbine discharge u;,and, in some cases, alsoa func- includes discrete variables due to the unitdiscrete oper-
tion of the hydro unit loading combination (that is, a func- ating characteristics.
tion of which hydro unitsare on-line within thestation). In practice, however, most of the methods for deter-
The minimum and maximum stationflows, and thusthe mining the hydro plant model are more approximate in
minimum (PMIN,) and maximum (PMAX,) unit electrical nature. Typically, these methods sum up the unit capacities
output limits, can be headdependent. For this reason, the within theplant and represent the plant generation (input/
unit M W limits in (28b) are stated as a function of the net output) characteristics by aform similar to the unit char-
head. Furthermore, theremay be hydro turbineoperating acteristics. Forbidden unit operatingregions are often
restrictions which are modeled as forbidden M W operating neglected, as is the dependence ofhydro unit efficiencyon
regions (bands) i n the range between the unit’s lower and the hydro unit loadingcombination. These methods may
upper M W limits. Pumping units havecharacteristicswhich be justifiedif, as earlier stated, the actual hydro unitsched-
are similar to hydro generating units, with the exception ules are obtained from avery-short-term (e+, every I m i n )
that while pumping, they increase load by their M W con- unit-level optimization problem.
sumption. Water Flow Balance Equations: The water flow balance
Since reservoir elevationcan be expressed as a nonlinear equations describethe conservation of flowsat the nodes
1582 PROCEEDINGS OF THE IEEE, VOL. 75, NO. 12, DECEMBER 1987
inthehydrosystem.Thesenodesmaybeofthestorage(i.e., where HR,and TR,designatethe setof hydroplants(because
reservoir) or nonstorage (i.e., simple hydro junction)type. of modeling at the plant level) and thermal units contrib-
The general form of the water balance equations is given uting toreserve type r, RH, and RT, represent the function
by used for evaluating the contribution of a hydro plant and
thermal unit, respectively, to reserve type r, and RES,(t) is
Xi(t + 1) = x ; ( t ) + Wi(t) the reserve type r requirement for time period t. The spe-
+ c U j ( t - Tj,) cific form of the functions RH, and RT, is dependent on the
/Eli type of reserve being modeled. A linear form is obviously
most desirable from a solution method standpoint. HCw-
ever, as described in Section 11-A, for thermal units, the
model for spinningreserve is nonlinear dueto the limit on
a unit's maximum reserve contribution.
Hydro plantreserve contribution is calculated as the dif-
where xi(t)is the storage content of node i (reservoir i ) at
ference between a plant capability limit (usually defined as
the beginning of period t, wi(t)is the sum of all natural
a function of the type of reserve being modeled) and the
inflows into nodei during periodt, u,(t) is the controlled
plant generation. In most cases, however, the maximum
flow along flow branch m, sk is the spilled flow along flow
reserve that can be suppliedby a hydro plant is limited due
branch & .I
and j index sets corresponding to thecon-
Miare
to the physics of the hydraulic system and characteristics
trolled flows into and out of nodei,respectively, and Ni and
of the turbine. For this reason, a maximum permissible
Kj are index sets correspondingto the spilled flowsinto and
reserve canbe assigned to the hydro plant. This maximum
out of node i,respectively. Ti is the water travel time for
reserve may be a function of head and the rate of change
branchj. There are limits on the storage and flow variables
in plant loading. Therefore, RH, may have to be modeled
given by
as a nonlinear function. This further complicatesthe prob-
& ( t ) IXj(t) 5 FjCt) (31a) lem and theauthorsare not awareof any existing short-term
hourly hydromodel which includes such nonlinear models.
&(t) 5 u,(t) 5 U,(t) (31b) Othersystem Consfraints:A number of other constraints
sk(f) 2 0. (31~) may be modeled for the hydro scheduling problem. Area
interchange constraintis one of the more important ones.
For a nodewith nostorage content, thewater flow equation It is used to model network transmission capacity limita-
is simplified in that the storage content variable xi(t)does tions. It is usually modeledas a constrainton thenet inter-
not appear in the equation. In practice, a reservoir with change of each areawith therest of the system (i.e., in terms
downstreamgeneration has asingleimmediate down- of limits on the difference between area total generation
stream plant; thus there is only a singlecontrolled outflow and load).
(and spillage) in thewater balanceequation. The set of water Hydro Scheduling Problem: For the hydro scheduling
balanceequations (30)form a linearset of constraints which problem, the general form of the objective function is
haveanetworkflowstructure.Asdescribedlater,thisstruc-
ture is exploited in many of the short-term hydro sched- I= 7 L,(PH(O) + b! (47)) (35)
uling algorithms to achieve fast solution times.
Generation and Reserve Constraints: For a purely hydro where
system, the generation constraint may be stated in terms
of a minimum generation requirement given by
PH(t) =
I
PH;(t), t = 1, - * * ,7
PH(t) B D(t) (32) with PHj(t) given by(29). L, represents the value of the hydro
energy production for period t. $ is the function repre-
where senting the value placed on the terminal reservoir contents.
PH(t) = PHi(t) In a purelyor predominantly hydro system, the problemis
I
to maximize] subjectto the hydro generation and flow con-
is the total hydro generation for period t. straints (28)-(32). In a hydro-thermal system, L, represents
The generation constraint in a hydro-thermal system is the value of the hydro energy which is determined based
of the form on the replaced thermal production cost for period t. In
either case, reserve and area constraints mayalso be
PH(Q + PT(t) = D(t) (33)
included.
where PH(t)and PT(t) represent the total hydro and thermal When the only coupling constraint between the hydro
generation (MW), respectively, and at)
is the load, for and thermal subsystems is through the load (total gener-
period t, including losses. Lossesare either modeledas con- ation) constraint equation (33), then it is possible, by means
stant or as a linear function of generation (see Section II- of a thermal pre-dispatch, to represent L, as a function of
C). the total hydro generation PH(t). If, however, other con-
Different types of reserve constraints may be modeled straints (e.&, reserve constraints of the form (M), or area
depending on the system requirements. Area and system interchange constraints)which couple the hydroand ther-
spinning,supplemental, emergency, orother types of mal subsystemsare present, then boththermal and hydro
reserve requirements lead to constraints of thegeneral
form decision variables and constraintsare explicitly present in
(written here for a hydro-thermalsystem) the problem formulation.In this case, the thermal cost C,
which i s a function of the thermal generation variables,
replaces L, in theobjective function. For the remainder of
COHENAND S H E R M T OPTIMIZATION-BASEDMETHODS FOR OPERATIONSSCHEDULING 1583

this paper, we assume that the objective function for the ods. More emphasis is put on describing nonlinear pro-
hydro scheduling problem has theform given i n (35). grammingapproaches based on reduced-gradient-type
methods, since they have been used to solve large-scale
B. Solution
practical
Methods hydro
problems.
scheduling
Dynamic ProgrammingMethods: Dynamic programming
The basic hydro scheduling problem has been formu-
(DP) methods were among the earliest methods applied to
lated as the followinglarge-scaleoptimization problem (this
the hydro-thermal scheduling problem [46], [ a ] , [61], and
formulation is primarily suited for a nonlinear program-
have continued tobe used [52], [55], [56], [74], [75]. With the
ming solution method).
exception ofmodeling water flow delays, DP hasthe advan-
min F(x, u) (36) tage that it can directly handle nonconvex, nonlinear, and
subject to even discrete characteristics present in the hydro and ther-
mal models. Since DP methodscan accommodate complex
Ax+Bu+Cs=w (37) models andare sometimes easier to implement (compared
X S X S X (384 to large-scale linear and nonlinear programmingmethods),
they are ideally suited for hydro systems with few hydro
-
u 5 u S ax) (38b) storage plants. Application of DP for scheduling a large
pumped storage plant is described in [52].This paper models
s r o (3&)
many characteristics ofthe plant including: discrete pump
where x is the state vector corresponding to thereservoir ing loads, discretegenerating regions, generating limitsand
storage content variables, u is the control vector corre- cycle efficiency as a function of head, andfinally, an objec-
sponding to the water flow variables, and s is the vector cor- tive function whichis dependent on the thermalunit com-
responding to water spillage. The negative of the function mitment and thus not necessarily convex.
F being minimized represents the total value of hydro For hydro systems with more than two or three storage
energygeneratedin the system overthe entire study period. plants, direct application ofDP is impractical due to exces-
TheformofthefunctionF,andthetermsitcontains,depend sive computationtimes and thewell-known curse of dimen-
on the original objective function being maximized (e.& sionality. Successive approximation methods [56], [61], 1741
hydro energy production), or minimized(e.& thermal pro- are usedto convert the solution of the original DP problem
duction cost), and as stated earlier, may include a terminal which involvesa highdimensional statespace, into a
cost term which is a function of the state of the reservoirs sequence of problems with lower dimensional state space
at the end ofthe short-term period.Since hydro plant energy (usually involvinga single reservoir).These methods con-
production is a function of plant discharge and net head verge monotonically to a local optimum which is depen-
(which, in turn, is afunction of reservoirstorage contents), dent an the initial starting solution.These methods, how-
F is, therefore, a function of bothx and u. The function F ever, are not ideally suited for hydro systems with many
is in general not convex (although it may nearly be so), and coupled storage plants [19].Linear and nonlinear program-
thus onecan only expect a localoptimum (F may not even ming methods are, therefore, superior to dynamic pro-
be differentiable). The objective function is also generally gramming methods for these kinds of systems and gen-
not separable.This is because, for most problems, the func- erally for hydro systems with more than three (orat most
tion L, in (35) is a function of the total hydro energy pro- four) reservoirs.
duction PH(t). Linear and Nonlinear Programming Methods: Linear and
The water flow balance equations (30), and the bounds nonlinear programming methods have been widely used
on reservoir storage contents andwater flow variables (31), for solving the short- (and medium-) term hydro-thermal
form the linear.set of constraints in (37) and the lower and schedulingproblem. Linear programming (LP) methods
requirethat either linear models bused (i.e., ignoring non-
upperboundsonthevectorsx,ufsin(38).In(38b),forhydro
plants with headdependentgeneration charactetistics, the
upper bound onplant discharge is a nonlinear function of
linearities), or that the objective Ll
ction and constraints
be linearized about anominal operating point, or that the
head, and thus the corresponding reservoir storage vari- nonlinearities be modeled using piecewise-linear, convex
ables. Other constraints(e.g., areainterchange, reserve) can approximations (e.& [72], [73]). Most nonlinear program-
also be added to the above problem formulation, but for ming methods applied to the hydro scheduling problem
the purpose of discussing basic solution methods these solve an, optimization problem witha nonlinear objective
constraints wili notbe presentlyconsidered. Also note that function (which may include some or all of the nonlinear
the above mathematical modeldoes not address hydro unit constraints addedto the original objective function as pen-
commitment which may require the modeling of hydro alty terms) and a largeset of linear constraints.
generation efficiency as a function of the configuration One of the earlier applications of nonlinear program-
(number) of hydro units online. Nor does it consider the ming methods tothehydro scheduling problem was
modeling of discrete gaps in hydro unit MW operating reported i n [SI . approach uses the flowbalance equa-
The
range, and hydro unitdiscrete loading level considerations tions (37) (spillage is not explititlymodeled in [SI) to elim-
due to unit efficiency characteristics. inate the reservoir releases and obtain a problem withan
Different optimization methods have been reported in objective entirely in terms of the reservoir storage vari-
the literature for solving the short-term hydro scheduling ables. All of the remaining constraints,with the exception
problem. Comprehensivesurveys are presented in [63]and of simple bounds on the reservoir storage variables, are
[a]. These methods include dynamic programming, linear appended to the objective function as penalty terms. The
and nonlinearprogramming, and decomposition-based resulting problem is then solved by a conjugate gradient
methods. Inthefollowingwewill brieflyreviewthesemeth- type method [14]. However, in [@I, it was later shown that
1584 PROCEEDINGS OF THE IEEE, VOL. 75, NO. 12, DECEMBER 1987
reduction of the flow equations in the state space of the Hanscom et a/. [5fl as well as Lafond [60] reduce the prob-
reservoir storage variables leads to a solution witha slower lem in terms of the release variables and apply a gradient
convergence rate than if the problem were reduced in the projection method[18]. This approach has led toa solution
control space (i.e., with respect to the release variables). method with superior convergence rate, at least for thetest
This fact is shown through eigenvalue analysis of the Hes- problems considered in [60], and with core requirements
sian of a typical hydro scheduling objective functionwith comparable to a reduced-gradient-type algorithm.
respect to therelease and storage variables. Many variations exist in thepractical implementation of
Reduced-gradient-type methods constitute a basic the basic reduced-gradient-type method in terms of
approach for solving the hydro scheduling problem for- approaches for handlingnonbasic variables at bounds and
mulated in (36)-(38). For simplicity, assuming a fixed upper the definition offeasible search directions. In [15], in addi-
bound for the release vector u, and no explicit modeling tion to the basic and nonbasic variables, a third type of
of the spillagevector (the spillageand releasevariables may variable called superbasics is defined. These variables can
sometimes be combined in the form aofsingle variable as lie between their bounds. Their introduction is motivated
done in [49] or [67J then the problem (36)-(38)can be by the fact that the solution to a nonlinear optimization
restated as problem does not necessarily lie at a vertex of the linear
constraints set. The details of thecorresponding algorithm
min F(x, u) (39)
and its implementation are described in [15]. A number of
subject to investigators in the hydroscheduling area ([50], [62]) have
used this approach.
Ax+Bu=w (40)
NetworkMethods: In the hydro scheduling problem for-
gsxsji a) (41 mulated in (39)-(41), the linear set of constraints (40) r e p
- resents a network withnodes corresponding to hydro facil-
u s u s u .
- (41b) ities such as reservoirs, hydro-junctions (diversionpoints),
A reduced-gradient-type method partitions, at each itera- and hydro-plants, and arcs corresponding to flows on riv-
tion, the current feasible point (x, u) into a set of m basic ers, canals, pipes, and hydro conduits.Each column of the
variables(strict1ywithin their bounds)whoseassociated set node-arc incidence matrix [A B] (corresponding to the set
of independent columns M form a basis of [A B], and a set of constraints in (40))characterizing the hydro network has
of n - m nonbasic variables ( n is the total dimension of x exactly two nonzero entries, one beinga +I and the other
and u combined) associated with the remainingset of col- a -1. The graph of the hydro network can be displayed by
umns N in [A 4. meansof a labeled drawing in terms of its nodes (reservoirs,
Partitioning [A s] by the set of basic and nonbasic col- hydro-plants, hydro-junctions) and directed arcs (flows on
umns (M and N, respectively) and denoting the vector of rivers, canals, etc.). Most recent applications of linear and
basic variablesby y and the vector of nonbasic variables by nonlinear programming methods for the hydro scheduling
z, where problem reported by other investigators ([53], [54], [59], [62],
[64], [69], [73], [76]) have exploited the underlying network
y = M-' w - M-' N Z structure associated with the hydro constraints to develop
then (39)-(41) can be restated as computationally efficient optimization algorithms.
An example of a hydro network with three reservoirs,
min f(M-' w - M-' N z,z) b f(z) (42) three hydro-plants, and two hydro-junctions is shown in
subject to Fig. 4(a). The graph of this hydro network is shown in Fig.
4(b) for a length of two time periods. In this example, there
y ~ M - ' w - M - ' N z s y
- (434 is a delay of one time periodin water flow from reservoir
- 3(node3)to hydro-plant3(node6).In Fig.4(b),a"fictitious"
gszsz. (43b)
sink nodes is defined whichabsorbs the sum of all hydro-
Let Vf(z)denote thereduced gradient ofF with respect to plant and spillage flows, over all time periods, flowing to
z. When the projection -Vf(z) of onto thecone of feasible their final destinations. Note that for this example hydro
directions defined by the set of active bounds in (43b) is network, it is not necessaryto specifically define nodes for
nonzero, then a "better" (i.e., smaller cost) feasible point plants 1 or 2 (corresponding to flows u1 and u 2 ) .A node is,
can be found by movingalong this direction. In so doing, however, required forhydro-plant 3 (node 6) to model the
if a basic variable hits one of its bounds, it must become flow delay between the upstream reservoir and the hydro-
nonbasic through an appropriate basis change. This pro- plant.
cess is repeated until the optimumis found. The hydro scheduling problem is, therefore, a network
Assuming that from one point on, in each iteration of the flow problem with a nonlinear objectivefunction. For such
above method nobasic variable hits a bound (i.e., no basis problems, network optimization methods are computa-
change), then thesubset of theeigenvalues of thereduced tionally superior to other methods. On test problems, at
Hessian of f with respect to z, corresponding to the set of least anorder of magnitude, and u p taofactor of morethan
active bounds at the solution point, govern the conver- 25, in solution time difference i s reported [3] between using
gence rate of the above procedure. Since the reduced a nonlinear network flow optimizationpackage and a gen-
Hessians of f w i t h respect to different subsets of nonbasic eral optimization package [16].Even when non-network
variables may have very different sets of eigenvalues, the constraints such as generation and area constraints are
rateof convergenceof the method can depend on thebases present in the hydroscheduling problem formulation,net-
used in theabove iterative process.Thisfact has been inves- work flow methods are stilt computationally superior t o
tigated in detail in [60]. To improve problem conditioning, other methods.
Authorized
COHENANDSHERKATlicensed use limited to: Universidad
OPTIMIZATION-BASED METHODS de La Salle. Downloaded on
FOR OPERATIONS August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.
SCHEDULING 1585
P : Reservoir
9cv : Hydro-Plant
-
---
S : Sink node.
: Arcs in the spanning tree.
: Arcs out of the rpanning
tree.
1586 PROCEEDINGS
Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 OF from
at 18:50:21 UTC THE IEEE VOL. 75,
IEEE, Xplore. NO. 12, DECEMBER
Restrictions apply. 1987
The concept of a spanning tree is key to network opti- mulation in[59] includes a general nonlinear objective for
mization algorithms. A tree is a connected acyclic graph, maximizing the value of hydro energy production subject
ormoresimplystated,agraphinwhichapathcanbeformed to mostly linear constraints.A set of nonlinear constraints,
between any two distinct pair of nodes and in which no representing forced spill conditions, is appended to the
cycles (loops) exist. A spanning tree for network
a is a tree objective function using the exact penalty method[8]. Only
which has all the nodes contained in its graph. The span- a small part ofthe constraint set (corresponding to a piece-
ningtreefortheexamplehydronetworkof Fig4a)isshown wise-linear model representing the maximum hydro-plant
in Fig. 4b). flow as a function of head) has a non-network structure. A
The concept of a spanning tree is important because it two-step methodi s used. In the first step, a relaxed version
can beshownthatforagraphcorrespondingtothenetwork of the original problem is solved where the non-network
node-arc incidence matrix, thereexistsaspanningtree such linear constraintsare omitted and the nonlinear objective
that its arcs correspond to a maximal set of linearly inde- is approximated by a linear function. An efficient primal
pendent columns in the node-arc incidence matrix. Thus simplex algorithm [9] is used to solve the network flow opti-
a basis has a graph-theoretic characterization and is defined mization problem. The solution to the relaxed problem is
intermsofaspanningtreeoftheassociatednetworkgraph. then used as the starting point for solving the nonlinear
A reduced-gradient-typemethod, as described earlier, programming problemin thesecond step, usingtheMlNOS
requires changes of bases which affect the columns of the [I61 optimization package. Thelinear set of constraintsare
basis matrix (or equivalently, i t s corresponding spanning handled inMlN0Susingsparsitytechniques.Thisapproach
tree). For network problems, calculations in each iteration can use available optimization software (inthe case of [59],
of a reduced-gradient-type algorithminvolving a basis the network optimizationcode NETFLO [9],and thegeneral
matrix, or its inverse, arecarried out via labelingoperations optimization package MINOS [16]) to solve the large-scale
on the graph of the networkand the associated spanning hydro scheduling problem.
tree. Efficient computational techniques and algorithms
using compact data structures are used for network opti-
C. Hydro-Thermal Coordination
mization. The interested reader is referred to [9] and [69] for
more details. The hydro-thermal coordination problemsolves for both
Theconstraints in theshort-term hydro scheduling prob- the thermalunit commitments and generation dispatch and
lem are often not of the purely network type. Non-network the hydro schedules. It is, therefore, a more complex prob-
side constraints may include the minimum hydro gener- lem than eitherthe thermal unit commitment or the hydro
ation constraint (see (32)), area constraints, hydro reserve scheduling problem considered alone. Existing methods
constraints, and head-dependent flow limits. In the hydro- for hydro-thermalcoordination decompose the problemat
thermalschedulingproblem,non-networkconstraints the outset into two subproblems: hydro-thermal sched-
include thegeneration constraint(33), and may alsoconsist uling with known unit commitment, and thermal unit com-
of reserve constraints (34), and area interchangecon- mitment. Coordination between thetwo subproblems
straints. depends on the overall solution method.
The non-network constraints are often linearized, or Heuristicdecomposition schemes[50],[52],[53],[55],
piecewise linearized, such that the feasible region is decompose the hydro-thermal coordination problem into
bounded by a convex polytope. The resulting set of non- hydro and thermal subproblems. The hydro scheduling
network side constraints, added to the hydro scheduling function uses the thermal cost function where the thermal
problem given in (39)-(41), are of the form generation requirement is the load minus the generation
supplied by the hydro system. The thermal subproblem
Cu+Dusr. (44)
solves the standard unit commitment problemwhere the
Different approacheshave been used for handling non- hydro generation and hydro reserve contributions are sub-
network side constraints of the form given in (44). One tracted from the load and reserve requirements. These
approach is based on using a specializationofnetwork schemes iterate between the two subproblems until the
algorithms. This approach partitionsthe basis for the set of solutions converge. The decomposition scheme [50] is
constraints (40)and (441, such that a portion of the
basis cor- basedon separating the hydroandthermal schedulingsub-
responds to a spanning tree associated with the network problems and coordinating the two through updating the
part ofthe constraints. The calculations involving this por- hydro cost function and the thermal generation require-
tion of the basis are carried out using the labeling opera- ment as each subproblem is solved iteratively. Brannlund
tions and efficient computational techniques of network et a/. [50] use a fast heuristic solution method for the ther-
algorithms. Detailsof thisapproach are described in [9] and mal subproblem which uses priority lists. A reduced gra-
its application to the hydro scheduling problem is reported dient algorithm [I41 which exploits the network structure
by a number ofinvestigators, including Brannlund eta/.[50] of the constraints is used for the hydro scheduling. Non-
and Ea and Monti [%I. network side constraints associated with transmission lim-
A number of otherapproaches have been used for han- itations are handled by special partitioning techniques[9].
dling non-network side constraints.Dembo [3]uses a Lagrangian relaxation methodshave alsobeen appliedto
Lagrangian relaxation algorithmforthe linear network solving the hydro-thermal coordination problem[54], [70].
problem with linear side constraints. The price vector is In [54], the generation and reserve constraints are the cou-
definedforthesideconstraintswhichareaugmentedtothe pling constraints which are adjoined onto thecost to form
objective functiontoformthe Lagrangian. Another the Lagrangian. Thethermal unit commitmentsubproblem
approach is the onereported in [59].The problem for- is solved using Lagrangian relaxation (describedin Section
COHENANDSHERKAT
Authorized OPTIMIZATION-BASED
licensed METHODS
use limited to: Universidad FOR Downloaded
de La Salle. OPERATIONS August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.1587
onSCHEDULING
I I ofthis paper).The hydro schedulingsubproblem is unit commitment, and coordinatethe twosubproblems by
decomposed in terms of independent valleys and solved means of a hydro cost function and thermal generation
using network flow linear programming techniques. Due requirements, have been more widely used than other
to the nonuniqueness property of the solution, which is decomposition methods. This weak coupling of the hydro
inherent in the linear hydro optimizationsubproblem for- scheduling and unit cornmitmerlt subproblemsworks well
mulation, a pelnalty term for deviation of the current solu- in most cases. There are areas where tight coordination is
tion from the solution obtained in thelast iteration is added beneficial for certain utilities.
For example, the fast ramping
to the hydro subproblem objectivefunction. According to capability of hydro unitscan be used to compensate for the
the authors in 1:54],this approach is effective for alleviating relativelyslow rampingof manythermal units.Also, utilities
convergence problems in the Lagrangian relaxation with area constraints may be able to coordinate the hydro
scheme, since it tends to prevent oscillations between two and thermal generation toproducemore economical
successive hydro optimizationsubproblem solutions(and, schedules. Therefore, development of better hydro-ther-
consequently, in thevaluesof the shadow pricesin between mal coordination methods is an important research area.
iterations). Applications of Lagrangian relaxation, Benders decompo-
Other decomposition methodshave alsobeen proposed sition, and other methods to real hydro-thermal systems are
for solving hydro scheduling and hydro-thermal coordi- slowly emerging;however, more experience with these
nation problems[28], [66],[67. Pereiraand Pinto [66] use the methods for real systemsis needed before evaluating their
Benders,decomposition method to coordinate the medium- success.
and short-term scheduling problemswhich are formulated
as one problem.The medium-term formulation models the
IV. CONCLUSIONS
constraints asslociated with hydrostorage at a weekly time
frame. The short-term formulationmodels the hourlygen- This paper has summarized the state of theart of short-
eration requirement, generation limits, and limits on the term operations scheduling. Algorithms have been
active plower fllows(the latter is evaluated based on thedc described forsolvingtheunitcommitmentandhydro
load flow model). The coupling between short and medium scheduling problems as well as methods for solving the
term is through plant generation targets determined by combined hydro-thermal scheduling problem.In the sum-
the mediumterm, which imposes constraints on theshort- mary sections to the unit commitment and hydro sched-
term scheduler;. Pereira and Pinto [66] use Dantzig-Wolfe uling sections of this paper, we have described some areas
decomposition to solve theshort-termhourly dispatch requiring attention.
problem. The overall method is applied to a predominantly As far as the general operations scheduling problem is
hydro system with reasonably good solutiontimes. In [28], concerned, there are also a number of deficiencies. One
the Benders method is used to decompose the problem into very important area is the scheduling of interchange. Most
a master problem involving the thermal unit commitment, utilities haveextensivetransactions with other utilities.The
and asubproblem involvinghydro-thermal scheduling(dis- methods to schedule transactions or evaluate potential
patch) with a fixed unit commitment. transactions being used are very ad hoc. This i s because
transactions often have a wide variety of constraints such
C. Summary as take-or-pay or energy limitations. Anotherarea that has
not been integrated very well into the short-term sched-
During thelast ten years, large-scale optimization meth- uling problemis load management. This includes the con-
ods have been applied for solving the short-term hydro
trol of residential appliances and industrial interruptible
scheduling and hydro-thermal coordination problems. Lin- loads.
ear and nonlinear programming methodswhich exploit the
Another research issueis the treatment of uncertainty in
network structure of the problem have been used for prac-
short-termscheduling ([37 contains several shortnote
tical applications. These methods are computationally effi- reports on this topic). The reserveconstraint is included to
cient, and at th'e present time, form thestate of the art for provide reserve in case of an unscheduled unit outage or
short-term hydro scheduling problems. Implementation of errors in the loadforecast; however,modeling the unit out-
methods that can effectively handle non-networkside con- age and repair distributions indetail may result in cost sav-
straints andcomputational experience with these methods
ings. (Somemethods that incorporate outage rates arepre-
applied to re<al-world problems need to be further sented in [24] and [25].)It is evident thatsystems with energy
addressed. Another areawhich can be improved i s the area
storage, such as hydro and pumped hydro systems, may
of modeling. Almost all of theexisting optimization models
benefitgreatlyfromconsidering unitoutage ratesand hydro
for short-term scheduling eitherneglect, or approximate, inflow uncertainty. Stored energy used early in thesched-
the hydro unit discrete operating characteristics, or the uling period, when outages are not considered, possibly
dependence of efficiency on unit loading combination should be held in reserve to provide energy in thecase of
within the hydro plant. Similarly, the limits on hydro
reserve a forced outage later in the period[20].
contribution may not be correctly modeled. We suspect
that in practice, these problems are either dealt with by
using heuristic methods outside of the main optimization APPENDIX
loop, or, that theyare accounted for in the very-short-term ECONOMIC DISPATCH
time frame by a hydro economic dispatch model.
Hydro-thermal coordination has been solved by decom- The calculation of the fueland maintenance cost OC(u(r),
position methods. Heuristic methods which decompose t ) involves solving the economic dispatch since the com-
the problem into hydro-thermal scheduling and thermal mitment u(r)i s known. The economic dispatch problem
1588 PROCEEDINGS
Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 OF THE
at 18:50:21 UTC fromIEEE,
IEEEVOL.
Xplore. NO. 12, DECEMBER
75, Restrictions apply. 1987
involves minimizing the fueland maintenance cost programming methods such as the reduced gradient
method [il,[IO] can also be used.
c I;(G,(t)) = c FC,(G,(t)) + MC,(G,(t)) (AI )
subject totheunit generation limits, the generation REFERENCES

requirement (4), and the spinning reserve requirement (5). General
Several methods have been used tal solve this problem. If
R. E. Bellman and S. E. Dreyfus, Applied Dynamic Program-
we ignore the spinning reserve reqluirement,then themost ming. Princeton, NJ: Princeton Univ. Press,1957.
widely used method i s the equal incremental cost method. J. F. Benders, ”Partitioningprocedurefor solving mixed-
This method uses the first-order necessary condition of variables programming problems,”Numer. Math.,vol.4,1962.
optimality which requires that the marginal cost of gen- R. S. Dembo, “Theperformance ofNLPNET, a large-scale non-
eration of all units, not at their limits, must be equal; that linear network optimizer,” presented at the NETFLOW’83
Coni., Pisa, Italy, Mar. 1983.
is, G,(t) must solve H. E. Everett, ”Generalized Lagrange multiplier method for
solving problemsofoptimumallocationof resources,”
d l ,(GI(r))ldGi = Wt). (A2)
Operat. Res., vol. 11, pp. 399-417, May-June 1963.
This leadsto the following methodsolution. of Let GEN (X(t)) L. R. Ford andD. R. Fulkerson, Flowsin Networks. Princeton,
NJ: Princeton Univ. Press,1962.
be the resulting generation when all unitsare dispatched R. 5. Garfinkel and G. L. Nemhauser, lnteger Programming.
according to (A2). If (A2) is satisfied for generation outside New York, NY: Wiley, 1972.
a unit’s generating limits, then the unit’s generation is set A. M. Geoffrion, “Duality in nonlinear programming: A sim-
to theclosest bound. The optimum generation is then found plified applications-oriented approach,” Western Manage-
ment Sci. lnst. workingpaper no.150, UCLA, LosAngeles, CA,
by solving
Aug. 1969.
CEN (X(t)) = CR(t). (A3) P. E. Gill and W. Murray, Practical Optimization. New York,
NY: Academic Press, 1981.
This is a straightforward root-finding problem that can be J. L. Kennington, and R. V. Helgason, Algorithmsfor Network
Programming.NewYork,NY:Wiley, 1980.
solved by the bisection algorithm. L. S. Lasdon, Optimization for LargeScaleSystems. New
Wood [38] has extended this procedure to dispatch to York, NY: MacMillan, 1970.
meet thespinning reserve constraint. Theabove equal R. E. Larson and J. I. Casti, Principles of Dynamic Program-
incremental cost method is solved first ignoring the spin- ming.NewYork, NY: Marcel Dekker, 1978.
ning reserve constraint. If the resulting dispatch does not R. E. Larson, “A survey of dynamic programming computa-
tional procedures,” /€E€ Trans. Automat. Contr., vol. AC-12,
satisfy the spinning reserve then the following procedure pp. 767-774, Dec. 1967.
is used to reallocate generations to provide more spinning E. I. Lawler and D. E. Wood, ”Branch-and-bound methods: A
reserve: survey,” Operat. Res., vol. 14, pp. 699-719,1966.
1) First consider those units that can pic’k u p reserve by D. G. Luenberger, lntroduction to Linear and Nonlinear Pro-
gramming. Reading, MA: Addison-Wesley, 1973, pp. 247-254.
lowering generation (these are units whose reserve con-
B. A. Murtagh and M. A. Saunders, “Large-scalelinearlycon-
tribution is less than their maximum allowedcontribution). strained optimization,” Mathematical Programming, vol. 14,
Let G€N1bethegeneration fromthese units after the initial pp. 41-72, 1978.
dispatch. Redispatch these units, using the incremental cost -, “MINOS 5.0 user’s guide,” Tech. Rep. SOL 83-20, Stan-
method, so that their generation sums to CElVl - DEL where ford Univ., Stanford, CA, Dec. 1983.
A. J. Wood and B. F. Wollenberg, Power Generationandcon-
DEL is the additional spinning reserve required. trol. New York,NY:Wiley,1984.
2) Now consider those units whose generations can be G. Zoutendijk, Mathematical Programming Methods.
increased without affectingreserve. These areunits whose Amsterdam, The Netherlands: North-Holland, 1976.
reserve contribution is at the maximum alltowed value. Let
GEN2 be the generation from these units after the initial
dispatch. Redispatch these units,usingthe equal in- Integration
cremental cost method, so that their generation sums to [I91 A. I. Cohen et dl., “Research and development of a unified
GEN2 + DEL. For this dispatch, the unit upper limits are approach tooperations scheduling under uncertainty,” Final
modified to GSP, - SPi. Rep.,DOE Contract DEACOI-79-ET-29243,Systems Control,
Inc., Palo Alto, CA, Oct. 1982.
If these steps can be carried out successfully, then the
[20] A.P.MeliopoulosandJ.Vilhjalmsson,”Optimalcoordinating
resulting generations will satisfy the spinningreserve con- policies of pumped hydrostorage plants in the presence of
straints. uncertainty,” /E€€ Trans. Power App. Syst., vol. PAS-101, pp.
Linear programming methods [IO], [40] can also be used 1536-1544, June 1982.
to solve for theeconomic dispatch. To uselinear program- [21] F. J. Reesand R. E. Larson, “Computer aided dispatching with
multiple types of generation,” /€E€ Trans. Power App. Syst.,
ming, the heat rate function must be represented as a piece- VOI.PAS-90, pp. 891-899, 1971.
wise-1inearfunction.The spinning reserve requirement can
be represented by the following set of linear inequalities:
Unit Commitment
c R,(t) 2 SPRES (t)
I
(A41
[22] P. P. J. van den Bosch, “Optimal dynamic dispatch owing to
spinning-reserve and power-rate limits,” paper 85 M W 086-
R,(t) 5 SP, (A5) 4, presented atthe IEEE/PES 1985Winter Meeting,New York,
NY, Feb. 1985.
R,(t) + G;(t) 5 GSP; (A61 [23] A. I. Cohen and S. H. Wan, ”A method for solving the fuel
constrained unit commitment problem,” I€€€Trans.Power
where R,(r) i s the contribution of unit
ito spinning reserve Syst., VOI.PWRS-2, pp. 608-614, Aug. 1987.
(the other variables are defined inSection 11-A). Nonlinear [24] A. I. Cohen and M. Yoshimura, “A branch-and-bound algo-
COHEN AND SHERKAT:

Authorized OPTIMIZATION-BASED
licensed METHODS
use limited to: Universidad FOR Downloaded
de La Salle. on SCHEDULING
OPERATIONS August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.1589
rithm for unit commitment,” /E€€ Trans. PowerApp. Syst, vol. dro Scheduling
PAS-102, pp. 444-451, Feb. 1983.
T. S. Dillon et a/., “Integer programming approach to the L.T.Anstineand R. J. Ringlee,”Susquehanna river short-range
problem of optimalunit commitment with probabilistic hydro-thermal coordination,” A/€€Trans. Pt. 111 (PowerApp.
reserve determination,” paper F 78265-1, presented at the Syst.), pp. 185-191, Apr. 1963.
IEEElPES 1978 Winter Meeting, New York, NY, Jan. 1978. N. V. Arvantidis and J. Rosing, “Composite representation of
J.M. Goodrich, B. N. Kendall, and C . D. Nagel, “Useof inter- a multireservoir hydroelectric power system,” /E€€ Trans.
active programs in daily dispatchoperations,” in Proc. Amer- Power App. Syst., vol. PAS-89, no. 2, Feb. 1970.
ican Power Conf., vol. 36,1974. B. Bernholtz and L. J. Graham, “Hydrothermal economic
J. Gruhl, F. Schweppe, and M. Ruane, “Unit commitment scheduling, Part II. Extension ofthe basic theory,“Al€€ Trans.
scheduling of electric power systems,” in L. H. Fink and K. Pt. ///(PowerApp. Syst.), vol. 80, pp. 1089-1096,1%1 (Feb. 1962
Carlson, Eds., System hgineering for Power: Status and Pros- section).
pects. Henniker, N.H.,1975. V. Bissonnette, L. Lafond,and G . Cote,“A hydro-thermal
H. Habibollahzadeh and J. A. Bubenko, “Application of scheduling model for the Hydro-Quebec production sys-
decomposition techniquesto short-term operation planning tem,” Proc. Power lndustry Computer Applications,San Fran-
of hydrothermal powersystem,” / E € € Trans. Power Syst.,vol. cisco, CA, May 1985.
PWRS-1, pp. 41-47, Feb. 1986. H. Brannlund,J.A. Bubenko, D. Sjelvgren,and N.Anderson,
G. S. Lauer et a/., “Solution of large scale optimal unit com- “Optimal short term operation planning of a large hydro-
mitment problems,” /€€€ Trans. Power App. Syst., vol. PAS- thermal power system based on a nonlinear network flow
101, pp. 79-%, Jan. 1982. concept,” presented at the IEEE Power Engineering Society
P. C . Lowery,”Generating unit commitment by dynamic pro- 1986 Winter Meeting, New York, Feb. 1986.
gramming,” /€€€ Trans. PowerApp. Syst., vol. PAS-85, pp. 422- M. F. Carvalho and S. Soares, “An efficient hydro thermal
426, May 1966. scheduling algorithm,” presented at the IEEE Power Engi-
A. Merlin and P. Sandrin, “A new method for unit commit- neering Society 1986 Summer Meeting, MexicoCity, Mexico,
ment at Electricite de France,” /€€€ Trans. Power App. Syst., July 1986.
vol. PAS-102, pp. 1218-1225, May 1983. A. I. Cohen and S. H. Wan, ”An algorithm for scheduling a
M. P. Van Meeteren eta/., “Extensive unit commitment func- large pumped storage plant,” I € € € Trans. Power App. Syst.,
tion includingfuel allocationand security area constraints,” vol. PAS-104, no. 8, Aug. 1985.
presentedat the PICA-85 Conf., San Francisco, CA, May 1985. R. A. Duncan, G . E. Seymore, and D. L. Streiffert, “Optimal
J.A. Mucstadtand S. A. Koenig, “An application of Lagrangian hydrothermal coordination for multiple reservoir river sys-
relaxation to scheduling in powergenerating systems,” tems,” /€€E Trans. Power App. Syst., vol. PAS-104, no. 5, May
Operat Res., vol. 25, pp. 387-403, May-June 1977. 1985.
C.K.Pang, G . B. Sheble,and F. Albuyeh,“Evaluation of K. Ea and M. Monti, “Daily operational planning of theEDF
dynamic programming methods and multiple area represen- plant mix-Proposal for anew method,” Proc. Powerlndustry
tation for thermal unit commitments,” /€€E Trans. PowerApp. Computer Applications, San Francisco, CA, 1985.
Syst., vol. PAS-100, pp. 1212-7218, Mar. 1981. L. Engles, R. E. Larson, J. Peschon,and K. N. Stanton,”Dynamic
C. K. Pang and M. C. Chen, “Optimal short-term thermalunit programmingapplied tohydro and thermalgeneration
commitment,” I€€€Trans. Power App. Syst., vol. PAS-95, pp. scheduling,” IEEE Tutorial Course Text,76CH1107-2-PWR,
1336-1346, July-Aug. 1976. IEEE, New York, NY, 1976.
D. W. Ross and S. Kim, “Dynamic economic dispatch of gen- J. E. Giles and W. 0. Wunderlich, “Weekly multipurpose
eration,” / € € E Trans. Power App. Syst., vol. PAS-%, no. 6, pp. planning model for TVA reservoir system,“]. WaterResources
2060-2080,1980. Planning and Management Division (ASCE), vol. 107, no. WR2,
R. P. Schulte, ”Problems associated with unit commitment pp. 495-511, Oct. 1981.
in uncertainty,”paper85 WM 0334, presentedatthe IEEVPES M. A. Hanscom, L. Lafond, L. Lasdon, and G . Pronovost,
1985 Winter Meeting, New York, NY, Feb. 3-8, 1985. “Modeling and resolution of the medium termenergy gen-
W. L. Snyder, Jr., eta/., “Dynamic programming approachto eration planning problem forlarge a hydroelectric system,”
unit commitment,” paper86WM 0%-2, presentedat the I E E U Manag. Sci., vol. 26, no. 7, pp. 659-668, July 1980.
PES 1986 Winter Meeting, New York, NY, Feb. 2-7,1986. R. H. Hicks, C. R. Cagnon, S. L. S. Jacoby, and J. S. Kowalik,
F. E. Villaseca and B. Fardanesh, ”Fast thermal generation “Large scale nonlinear optimizationof energy capability for
rescheduling,” /€€€ Trans. Power Syst., vol. PWRS-2, pp. 65- thepacificnorthwesthydroelectric system,” / E € € Trans.
71, Feb. 1987. Power App. Syst., vol. PAS-93, no. 5, Sept. 1974.
J. G . Waight, F. Albuyeh, and A. Bose, “Scheduling of gen- Y. lkura and G. Gross, “Efficient large-scale hydro system
eration and reserve margin using dynamic and linear pro- scheduling with forced spill conditions,” I€€€Trans. Power
gramming,” /€€€ Trans. Power App. Syst., vol. PAS-100, May App. Syst., VOI. PAS-103, pp. 3502-3521, Dec. 1984.
1981. L. Lafond, “On the deterministic production planning of a
W. G . Wood, “Spinning reserve constrained staticand hydroelectric system,” Ph.D. dissertation, Dep. Operations
dynamic economic dispatch,” /E€€ Trans. Power App. Syst., Res., Stanford Univ., Stanford, CA, Dec. 1981.
vol. PAS-101, pp. 381-388, Feb. 1982. R. E. Larson and W. C . Keckler, “Applications of dynamic pro-
gramming to the controlof water resource systems,” Auto-
matica. vol. 5. DD. 15-26.1969 (New York. NY: Peraamon).
[62]T. M. ’Lekane; ‘“Short-termscheduling’ofmulcreservoir
Fuel scheduling hydroelectric power systems,” in Proc. o f PSCC (Lausanne,
[42] C. K. Pang eta/., “Pool daily fuel scheduling,” EPRl Rep. EL- Switzerland), pp. 375-383,1981.
1659, Electric Power Research Institute, Palo Alto, CA, Feb. [63] D.P. Loucks, J. R. Stedinger, and D. A. Haith, WaterResources
1981. Systems Planningand Analysis. Englewood Cliffs, NJ: Pren-
[43] A. B. R. Kumar etaL,“Fuel resource scheduling, Part Ill-The tice Hall, 1981.
short-term problem,” /E€€ Trans. Power App.Syst., vol. PAS- [64] A. Merlin, B. Lauzanne, J. F. Maunus, J.Auge, and M. Ziglioli,
103, pp. 1556-1561, July 1984. ”Optimization of shortterm schedulingof EDF hydraulicval-
[44] C . E. Seymore et a/., ”Long-term, midterm, and short-term leys with coupling constraints: The Ovide model,” in Proc.
fuel scheduling,” EPRl Rep. EL-2630, Electric PowerResearch PSCC (Lausanne, Switzerland),pp. 345-354,1981.
Institute, Palo Alto, CA,Jan. 1983. [65] R. Nieva, A. Inda, and J. Frausto, “CHT A digital computer
[45] S. Vemuri eta/.,”Fuel resource scheduling-implementation package for solving short term hydro-thermal coordination
in SWEPCO energy management system,” presented at the and unit commitment problems,“ Proc. Powerlndustry Com-
1985 PICA Conf., San Francisco, CA, May 1985. puter Applications,San Francisco, CA, May 1985.
1590Authorized licensed use limited to: Universidad de La Salle. Downloaded on August 17,2020 at 18:50:21OF
PROCEEDINGS THE
UTC from VOL.
IEEE,IEEE 75, Restrictions
Xplore. NO. 12,DECEMBER
apply. 1987
M. V. F. Pereiraand L. M. V. G . Pinto,“Decomposition Arthur I.Cohen (Member, IEEE) received the
approach to the economic dispatch of hydro-thermal sys- B.S. and MS. degrees in electricalengi-
tems,” /€E€ Trans. Power App. Syst., vol. PAS-101, Oct. 1982. neering from Cornell University, Ithaca, NY,
M. V. F. Pereira et a/., ”Application of decomposition tech- and the Ph.D. degree from the University
niques to themid- and short-termschedulingofhydro- of California, Berkeley.
thermal systems,” Proc. Power Industry Computer Applica- He isaSenior Principal Consultant at Sys-
tions, Houston, TX, June 1983 tems Control, Inc., Palo Alto, CA. He has
R. E. Rosenthal, ”The status of optimization models for the developed optimization methods for avari-
operation of multireservoir systems with stochastic inflows ety of real-world problems, including the
and nonseparable benefits,” Res. Rep. 75, Tennessee Water design of electrical distribution networks,
Resources Res. Cen., The Univ. of Tennessee, May 1980. thescheduling of thermal and pumped
-, “A nonlinear network flow algorithm for maximization hydro plants, and the development of automobile controls. He
of benefits in a hydroelectric powersystem,” Oper. Res., vol. received the WilliamBendix Automotive Electronics Award forhis
29, no. 4, July-Aug. 1981. work in developing controls for cold engine operation. His current
J. J. Shaw eta/., “Optimal scheduling of large hydrothermal interests are in developing methods for scheduling load manage-
power systems,” I€€€ Trans. Power App. Syst., vol. PAS-104, ment and interchange transactions.
pp. 286-294, Feb. 1985. Dr. Cohen is a member of the Power Engineering Society.
V. R. Sherkat, R. Campo, K. Moslehi and E. 0. Lo, “Stochastic
long-termhydrothermaloptimizationforamultireservoir
system,” /E€€ Trans. Power App. Syst., vol. PAS-104, no. 8, Aug.
1985.
V. R. Sherkat, K. Moslehi, E. D. Lo, G . Sanchez, and J. Diaz, Vahd R. Sherkat (Member, IEEE) received
“Modular and flexible software for medium-and short-term theB.S.,M.S.,andPh.D.degrees,allinelec-
hydro-thermal scheduling,” presented at the 1987 Power trical engineering, in 1973, 1975, and 1978,
Industry Computer Applications Conf., Montreal, Que., Can- respectively, from Cornell University, Ith-
ada, May 1987. aca, NY.
D. Sjelvgren and T. S. Dillon, “Optimal operations planning He has been employed at Systems Con-
in a large hydro-thermal power system,” I€€€ Trans. Power trol, Inc., Palo Alto, CA,
for nearly ten years,
App. Syst., vol. PAS-102, no. 11, Nov. 1983. and is presently managing agroup working
W. J. Trott and W. W-G. Yeh, “Optimization of multiple res- on applications of optimization methods to
ervoir systems,” /. Hydraulics Division(ASCE), Oct. 1973. power systems network and operations
F. A. Viramontes and H. B. Hamilton, “Scheduling of hydro scheduling and planning problems. In the
electric storage plants using dynamic programming,”paper past he had worked in the areas of power system dynamic mod-
77 CH1195-2-PWR, presented at the IEEE/PES Summer Meet- eling and stability analysis. His current interestsare in developing
ing, Mexico City, Mexico, July 17-22, 1977. methods for operations planningin large hydro-thermal systems,
F. Wakamori, K. Morita, and T. Sugiyama, “Layered network and in developing software for power system scheduling and net-
model approach to optimal daily hydro scheduling,” /€€E work optimization applications.
Trans. PowerApp. Syst., vol. PAS-101, Sept. 1982. Dr. Sherkat is a member of the Power Engineering Society.
COHENANDSHERKAT:licensed
Authorized OPTIMIZATION-BASED METHODSFOR
use limited to: Universidad deOPERATIONS SCHEDULING
La Salle. Downloaded on August 17,2020 at 18:50:21 UTC from IEEE Xplore. Restrictions apply.1591

Optimization-Based Methods For Operations Scheduling PDF

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Optimization-Based Methods For Operations Scheduling PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Optimization-Based Methods For Operations Scheduling PDF

Uploaded by

Copyright:

Available Formats

Optimization-Based Methods for Operations

PROCEEDINGS OF THE IEEE, VOL. 75, NO. 12, DECEMBER 1987

subject to the unitconstraints, and generation and reserve

COHENANDSHERKATOPTIMIZATION-BASEDMETHODS FOR OPERATIONSSCHEDULING 1577

where y i ( t ) is the kthupdate ofy,(t) and ak is a step length

Describing the Lagrangian relaxation method requires 0)

answering the following questions: 1) how dowe find the C ak -+ m.

function D( ). The first [IO], [23], [31]involves using the

C. Extensions to Unit Commitment

1580 PROCEEDINGS OF THEIEEE, VOL. 75, NO. 12,DECEMBER 1987

COHEN AND S H E R K A T OPTIMIZATION-BASED METHODS FOR OPERATIONS SCHEDULING 1581

COHENAND S H E R M T OPTIMIZATION-BASEDMETHODS FOR OPERATIONSSCHEDULING 1583

subject totheunit generation limits, the generation REFERENCES

COHEN AND SHERKAT:

You might also like