Valuing and optimizing scheduling of generation assets

• US 7,474,995 B2
• Filed: 01/02/2003
• Issued: 01/06/2009
• Est. Priority Date: 05/03/2002
• Status: Active Grant

• Current Assignee: Fidelity Information Services, LLC (Fidelity National Information Services Incorporated)
• Original Assignee: FIS Energy Systems, Inc. (Fidelity National Information Services Incorporated)
• Inventors: Manoliu, Mihaela, Skantze, Petter, Masiello, Ralph D.
• Primary Examiner(s): Borissov; Igor N
• Application Number:
  US10/336,541
• Publication Number:
  US 20040039622A1
• Time in Patent Office: 2,196 Days
• Field of Search: 705 7- 11, 705/412, 705/36.R, 705/37, 705/35, 705/400, 705/26, 705/27, 700286-291, 700/295, 700/297, 703/2, 703/3, 703/4, 706/925, 706/926
• US Class Current: 703/2
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 50/06 Energy or water supply
• CPC Class Codes: H02J 3/004 Generation forecast, e.g. methods or systems for forecasting future energy generation
• CPC Class Codes: H02J 3/008 involving trading of energy or energy transmission rights
• CPC Class Codes: Y02E 40/70 Smart grids as climate change mitigation technology in the energy generation sector
• CPC Class Codes: Y04S 10/50 Systems or methods supporting the power network operation or management, involving a certain degree of interaction with the load-side end user applications
• CPC Class Codes: Y04S 50/10 Energy trading, including energy flowing from end-user application to grid

Abstract

The present invention provides methods and systems for determining anticipated profit from facilities such as electrical power generation facilities, for determining values for assets based on profitability of facilities, and for determining optimal operational scheduling options for facilities. Methods and systems are provided which utilize a dynamic programming algorithm and a decision tree based model in which one or more operating constraints are implicitly modeled, facilitating computational tractability. Additionally, methods and systems are provided that utilize a dynamic programming algorithm and a decision tree based model that accounts for a combined effect of price paths with specified uncertainty as well as operational constraints. Furthermore, methods and systems are provided that address profitability, valuation, and scheduling in relation to a group, or portfolio, of facilities, accounting for liquidity factors as well as group, or global, constraints.

Claims

1. A method implemented on at least one computing system for facilitating scheduling of operation of a facility for at least a first time interval of a period of time, the method comprising:

using a processor, generating a decision tree based model accounting for a combined effect, on the scheduling of the operation of the facility, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility;

at least one specified level of uncertainty with regard to the at least one specified forward price path; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility;

applying a dynamic optimization algorithm to the decision tree based model to determine an optimal scheduling option for at least the first interval of time; and

,

storing in a memory optimal scheduling option information associated with the optimal scheduling option,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

,

mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

2. The method of claim 1, wherein one or more constraints of the at least one specified constraint are implicitly modeled.

3. A method implemented on at least one computing system for determining an anticipated profitability of operation of a facility over a period of time, the method comprising:

using a processor, generating a decision tree based model accounting for a combined effect, on scheduling of the operation of the facility over the period of time, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility;

at least one specified level of uncertainty with regard to the at least one specified forward price path; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility;

applying a dynamic optimization algorithm to the decision tree based model to determine the anticipated profitability over the period of time; and

,

storing in a memory anticipated profitability information associated with the anticipated profitability,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

,

mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

4. The method of claim 3, wherein one or more constraints of the at least one specified constraint are implicitly modeled.

5. The method of claim 3, comprising determining a value of an asset based on the anticipated profitability.

6. The method of claim 3, comprising generating a decision tree based model that can account for a contribution, to the combined effect, of a heat rate versus generation output function for the facility.

7. The method of claim 6, comprising generating a decision tree based model that can account for a contribution, to the combined effect, of a decreasing heat rate versus generation output function for the facility.

8. The method of claim 3, wherein applying a dynamic programming algorithm comprises using a dynamic programming algorithm that uses backward iteration through one or more decision trees of the decision tree based model.

9. The method of claim 8, wherein applying the dynamic programming algorithm comprises determining an optimal decision rule at each of one or more nodes of the decision tree based model, each node representing a time in the period as modeled, and each optimal decision rule representing an optimal dispatch option at each of the times as modeled.

10. The method of claim 9, wherein the facility is a generation facility, and wherein applying the dynamic programming algorithm comprises determining an optimal decision rule at each of one or more nodes of the decision tree based model, each optimal decision rule representing a dispatch option selected from ramping up a generation rate, ramping down a generation rate, and maintaining a steady generation rate.

11. The method of claim 10, wherein applying the dynamic programming algorithm comprises determining an optimal decision rule at each of one or more nodes of the decision tree based model, each optimal decision rule representing a dispatch option selected from ramping up a generation rate, ramping down a generation rate, and maintaining a steady generation rate, and, if the dispatch option is to ramp up the generation rate, determining an optimal ramp up rate, and, if the dispatch option is to ramp down the generation rate, determining an optimal ramp down rate.

12. The method of claim 10, wherein applying the dynamic programming algorithm comprises determining a profit value for each of one or more intervals between the nodes, the profit values for the intervals indicating, if positive, a profit associated with the interval, and, if negative, a loss associated with the interval.

13. The method of claim 12, wherein applying the dynamic programming algorithm comprises determining a profit value for the period, the profit value for the period indicating, if positive, a profit associated with the period, and, if negative, a loss associated with the period.

14. The method of claim 13, wherein applying the dynamic programming algorithm comprises determining the profit value for the period by adding together the profit values for the intervals.

15. The method of claim 14, wherein applying the dynamic programming algorithm comprises determining the specified dispatch options so as to maximize the profitability of the operation of the generation facility over the period of time.

16. The method of claim 13, comprising specifying a length of time represented by each of the intervals, and wherein a shorter length of time between each of the intervals corresponds with a greater precision of the decision tree based model.

17. The method of claim 13, wherein specifying the specified level of uncertainty comprises specifying at least one of a time-dependent drift, a time-dependent mean reversion rate, and a time-dependent volatility.

18. The method of claim 10, comprising representing ramped up, ramped down, and steady generation rates in the decision tree based model according to the recursive formulas:

ramp up decision;

Q_h+1=min{Q_h+R_Up,Q_Max}

ramp down decision;

Q_h+1=max{Q_h−

R_Down,Q_Min}

steady decision;

Q_h+1=Q_h

wherein Q_h+1 is a generation output for the facility at time interval h+1, Q_h is a generation output for the facility at time interval h, R_Up is a maximum ramp up generation output rate for the facility, R_Down is a maximum ramp down generation output rate for the facility, Q_Max is a maximum generation output rate for the facility, Q_Min is a minimum generation output rate for the facility when the facility is on, min {Q_h+R_Up,Q_Max} is a lesser of Q_h+R_Up and Q_Max, and max {Q_h−

R_Down, Q_Min} is a greater of Q_h+R_Up and Q_Max.

19. The method of claim 8, wherein generating the price tree based model comprises utilizing a flexible price tree based model.

20. The method of claim 8, wherein generating a price tree based model comprises generating a price trinomial tree based model, and wherein generating a state decision tree based model comprises generating a state trinomial tree based model.

21. The method of claim 8, wherein generating a decision tree based model comprises generating a decision tree based model that accounts for a contribution, to a combined effect on the optimization of the scheduling, of at least one specified forward price path, the at least one specified forward price path being based on a forecasted future price path for the at least one price of the at least one commodity over the period of time.

22. The method of claim 8, comprising explicitly modeling a first set of one or more of the at least one constraint by including a variable in one or more formulas of the decision tree based model to represent each constraint of the first set in terms of at least one of the at least one operating parameter, and comprising implicitly modeling a second set of one or more of the at least one constraint by altering a variable representing a constraint of the first set so as to approximate a contribution, to a combined effect, of each of the constraints of the second set.

23. The method of claim 8, wherein the at least one constraint comprises at least one operating constraint and at least one cost, and wherein generating a decision tree based model comprises generating a decision tree based model that accounts for a contribution, to a combined effect on the optimization of the scheduling, of the at least one operating constraint and the at least one cost.

24. The method of claim 8, wherein the facility is a generation facility, and wherein the at least one parameter consists of a generation output parameter and a runtime parameter, and wherein the state decision tree based model comprises one or more state decision trees in which each node is characterized by a value for the generation output parameter and a value for the runtime parameter, and wherein generating a state decision tree based model comprises generating a state decision tree based model in which the constraints are formulaically represented in terms of at least one of the generation output parameter and the runtime parameter.

25. The method of claim 24, wherein generating a decision tree based model comprises generating a decision tree based model accounting for a contribution, to a combined effect, of at least one specified constraint, the at least one specified constraint comprising a first set of constraints comprising at least one of a maximum output rate, a minimum output rate, a maximum ramp up rate, a maximum ramp down rate, a maximum ON run time, a maximum OFF run time, a startup cost, and a shutdown cost.

26. The method of claim 24, comprising explicitly modeling the constraints of the first set.

27. The method of claim 26, wherein generating a decision tree based model comprises generating a decision tree based model accounting for a contribution, to a combined effect, of at least one specified constraint, the at least one specified constraint comprising a second set of constraints comprising at least one of a maximum number of starts per a unit of time, a maximum number of ON/OFF cycles per a unit of time, and a minimum total ON time per a unit of time.

28. The method of claim 26, comprising implicitly modeling the constraints of the second set.

29. The method of claim 24, comprising, at each of the one or more nodes, calculating cost and revenue, and comprising defining cost and revenue according to the following formulas:

cost=TFC_h+(NFC_h*Q_h)+RC_h+FC_h

revenue=S_h^e*Q_h

wherein TFC_h=total fuel cost at time interval, NFC_h=non-fuel cost at time interval, Q_h=generation output at time interval, RC_h=run cost at time interval, FC_h=fixed cost, and S_h^e=spot price of power.

30. The method of claim 24, wherein the at least one parameter consists of a time parameter, a price parameter, a generation output parameter and a runtime parameter, and wherein each node in one or more trees of the price tree based model is characterized by a time value and a price value, and wherein merging the price tree based model and the state decision tree based model to generate the decision tree based model comprises generating the decision tree based model comprising one or more trees in which each node is characterized by a time value, a price value, a generation output value and a runtime value.

31. The method of claim 24, wherein the facility is a generation facility, and wherein the profitability of the operation of the facility at a given time is dependent at least in part on a spot price for a first commodity, the first commodity being based on that which is generated by the facility, and comprising defining the spot price for the commodity in accordance with the formula:

d ln S(t)=[α

(t)−

k(t)ln S(t)]dt+σ

(t)dW(t)

wherein α

(t) represents a time dependent drift function, k(t) represents time-dependent mean-reversion rate function, and σ

(t) represents a time-dependent volatility.

32. The method of claim 8, wherein applying the dynamic programming algorithm comprises applying a non-ruthless dynamic programming algorithm.

33. The method of claim 32, wherein the facility is a generation facility, and wherein applying a non-ruthless dynamic programming algorithm comprises applying a non-ruthless dynamic programming algorithm that can account for the contribution, to the combined effect, of any specified heat rate versus generation output function for the generation facility.

34. The method of claim 33, comprising defining total fuel cost TFC_h with the following formula:

TFC_h=HR(Q)*S_f*Q

wherein HR(Q)=average heat rate, S_f=spot price of fuel, and Q=generation output.

35. The method of claim 34, comprising determining the spot price for the first commodity in accordance with a futures price model for the first commodity in which a future price for the first commodity is determined in accordance with the formula:

dF(t,T)=F(t,T)σ

(t,T)dW(t)

wherein F(t,T) is futures price F as a function of time t and maturity time T, and wherein futures price instantaneous volatility σ

(t,T) is a function of time t and maturity T, and comprising defining the futures price instantaneous volatility σ

(t,T) in accordance with the formula;

36. The method of claim 8, comprising generating a price tree based model to model possible price paths over the period of time utilizing Monte Carlo simulation.

37. A computer usable storage medium storing program code which, when executed by a computer, causes the computer to execute a computerized method for facilitating scheduling of operation of a facility for at least a first time interval of a period of time, the method comprising:

using a processor, generating a decision tree based model accounting for a combined effect, on the scheduling of the operation of the facility, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility;

at least one specified level of uncertainty with regard to the at least one specified forward price path, said at least one specified level of uncertainty comprising a level of reversion rate and a level of volatility; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility;

applying a dynamic optimization algorithm to the decision tree based model to determine an optimal scheduling option for at least the first interval of time; and

,

storing optimal scheduling option information associated with the optimal scheduling option in a memory,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

,

mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

38. The computer usable medium of claim 37, wherein at least one of the one or more specified constraints are implicitly modeled.

39. A computer usable storage medium storing program code which, when executed by a computer, causes the computer to execute a computerized method for determining an anticipated profitability of operation of a facility over a period of time, the method comprising:

using a processor, generating a decision tree based model accounting for a combined effect, on scheduling of the operation of the facility over the period of time, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility;

at least one specified level of uncertainty with regard to the at least one specified forward price path; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility;

applying a dynamic optimization algorithm to the decision tree based model to determine the anticipated profitability over the period of time; and

storing in a memory anticipated profitability information associated with the anticipated profitability,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

, mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

40. The computer usable medium of claim 39, wherein one or more constraints of the at least one specified constraint are implicitly modeled.

41. A computerized system for facilitating scheduling of operation of a facility for at least a first time interval of a period of time, the system comprising:

a processor;

memory communicatively coupled with the processor, the memory comprising instructions executable by the processor for performing the following;

generating a decision tree based model accounting for a combined effect, on the scheduling of the operation of the facility, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility;

at least one specified level of uncertainty with regard to the at least one specified forward price path; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility;

applying a dynamic optimization algorithm to the decision tree based model to determine an optimal scheduling option for at least the first interval of time; and

storing in a memory optimal scheduling option information associated with the optimal scheduling option,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises the following;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

,

mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

42. The system of claim 41, wherein one or more constraints of the at least one specified constraint are implicitly modeled.

43. A computerized system for determining an anticipated profitability of operation of a facility over a period of time, the system comprising:

a processor;

memory communicatively coupled with the processor, the memory comprising instructions executable by the processor for performing the folling;

generating a decision tree based model accounting for a combined effect, on scheduling of the operation of the facility, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility;

at least one specified level of uncertainty with regard to the at least one specified forward price path; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility; and

applying a dynamic optimization algorithm to the decision tree based model to determine the anticipated profitability over the period of time,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises the following;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

,

mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

44. The system of claim 43, wherein one or more constraints of the at least one specified constraint are implicitly modeled.

45. A computerized system for facilitating scheduling of operation of a facility for at least a first time interval of a period of time, the system comprising:

a processor; and

memory accessible by the processor;

wherein the processor is programmed for;

generating a decision tree based model accounting for a combined effect, on optimization of the scheduling of the operation of the facility, of;

at least one specified forward price path, over the period of time, including at least one price of at least one commodity associated with operation of the facility, the at least one specified forward price path being determined from information stored in the memory;

at least one specified level of uncertainty with regard to the at least one specified forward price path, the at least one specified level of uncertainty being determined from information stored in the memory; and

,

at least one specified constraint associated with at least a first state of at least one state of at least one operating parameter associated with the operation of the facility, the at least one specified constraint being determined from information stored in the memory; and

applying a dynamic optimization algorithm to the decision tree based model to determine an optimal scheduling option for at least the first interval of time,

wherein generating a decision tree based model accounting for a combined effect on the scheduling of the facility comprises;

generating, based on the specified forward price path and the at least one specified level of uncertainty, a price tree based model to model possible price paths over the period of time;

generating a state decision tree based model to model possible operating parameter states over the period of time; and

,

mathematically merging the price tree based model and the state decision tree based model to generate the decision tree based model.

46. The system of claim 45, wherein one or more constraints of the at least one specified constraint are implicitly modeled.