الگوریتم زمان بندی تولید برق با استفاده از برنامه ریزی پویا

Power generation scheduling is a constrained optimization problem whose solution determines the set of generating units, among those owned by the electric utility, that should be connected to the grid at any hourly interval over a period of time, lasting from a day to a week, such that an objective function–usually, cost of operation–, is minimized. The actual power generation allocated to each committed unit is typically determined by an economic dispatch to meet the actual system load demand that may deviate from the forecasted one. Dynamic programming is considered an effective solution technique in power systems, not only because scheduling is naturally a sequential decision process, but also because formulation of the unit commitment problem results in a non-linear, non-convex, time dependent, and mix-integer problem that is not easily amenable to other solution techniques. Although dynamic programming-based solution algorithms provide optimal commitment schedules, execution time and memory requirements are affected by the “curse of dimensionality,” that is by the number of unit combinations to be considered in the solution process. In dynamic programming-based power scheduling algorithms, thousands of hourly economic dispatches must be performed to consider every possible unit combination over all the stages of the optimization interval. If the unit commitment problem is constrained to observe a minimum system spinning reserve and an economic dispatch of a combination of units does not comply with this requirement, necessary and sufficient conditions have been established to guarantee that the dispatch of these units will meet the constraint. However, these conditions can only be checked for feasibility after a dispatch is performed. In this paper, we present necessary and sufficient conditions for the feasibility of unit combinations that can be checked off-line — that is, before the start of the unit commitment algorithm, and thus before any economic dispatches are performed, thereby rendering a very efficient unit scheduling algorithm in terms of computer memory and execution time. Moreover, these feasibility conditions are independent of the problem formulation and thus can easily be applied to other unit commitment algorithms. Examples are provided to illustrate the efficiency attainable by the implementation of these conditions.

The objective of the unit commitment problem is to determine the set of generating units, among those owned by an electric utility that should be connected to the power grid on an hourly basis to supply the demand at minimum operating cost over the scheduling horizon [1] and [2]. This optimization problem is constrained by the unit characteristics and other operation limitations. Since the objective of the unit commitment is to determine a cyclic schedule that will meet the system constraints at minimum cost, the economic operation of a power system may be formulated as a dynamic optimization problem. The problem is dynamic in the sense that decisions to startup and/or shutdown units at any stage cannot be made without considering the states of the system at some other stages. Many mathematical programming techniques have been proposed to solve the unit commitment problem [3], [4], [5], [6] and [7]. Dynamic programming is the only one that always yields a globally optimal solution because it can operate upon nonlinear, non-convex, integer and otherwise non-differentiable functions not amenable to other optimization techniques. Although dynamic programming-based solution algorithms provide optimal commitment schedules [8], execution time and memory requirements are affected by the “curse of dimensionality,” that is by the number of unit combinations to be considered in the solution process. Generally, unit commitment is a computationally intensive algorithm, since thousands of hourly economic dispatches must be performed to consider every possible unit combination over all the stages in the optimization interval [9]. Therefore, any effort toward the elimination of any unfeasible unit combinations performed off-line–that is before the start of the commitment algorithm and thus before any dispatches are considered–will handsomely pay off in the efficient use of computer resources. When the commitment problem is constrained to observe a minimum system spinning reserve and a dispatch of a unit combination does not comply with the requirement, the problem may still be solvable by the re-dispatch of these units, as long as the conditions prescribed by Wood [10] are satisfied. However, these feasibility conditions can only be checked after a dispatch has been performed and, as a consequence, many dispatches that turn out to be unfeasible are needlessly computed in the process. In this paper we present the off-line conditions that a unit combination must satisfy to not only meet the minimum system spinning reserve constraint, but also the power balance constraint, the unit capacity limits, and all the other pertinent constraints as well. These conditions are shown to be necessary. We further show that these conditions turn out to be both necessary and sufficient when the spinning reserve constraint is to be met by re-dispatch. Clearly then, when these conditions are not fulfilled by a unit combination, that combination can be discarded as unfeasible by the scheduling algorithm, thereby reducing drastically the number of decisions to be considered in the solution space. The net result is a very efficient commitment algorithm, as illustrated by examples. Furthermore, these feasibility conditions are independent of the problem formulation and thus can easily be implemented in other unit commitment algorithms.

In this paper, we have derived the mathematical formulation for the unit commitment problem in power systems using dynamic programming techniques. Two conditions were presented, which can be checked off-line to eliminate unit combinations that are guaranteed, a priori, to be infeasible combinations, since they are both necessary for a successful solution. Furthermore, we have presented a theorem with necessary and sufficient conditions for unit feasibility that require re-dispatch to meet the system spinning reserve requirement. Detailed examples on a 20-unit system showed specifically how the computational efficiency was attained. Therefore, when these conditions are checked as prescribed, they will always render very efficient solutions to unit commitment algorithms.