Short-term scheduling of thermal-electric generators using Lagrangian relaxation. (English) Zbl 0655.90030

Bard, Jonathan F.

Oper. Res. 36, No. 5, 756-766 (1988).

Summary: This paper presents an expanded formulation of the unit commitment problem in which hundreds of thermal-electric generators must be scheduled on an hourly basis, for up to 7 days at a time. The underlying model incorporates the full set of costs and constraints including setup, production, ramping, and operational status, and takes the form of a mixed integer nonlinear control problem. Lagrangian relaxation is used to disaggregate the model by generator into separate subproblems which are then solved with a nested dynamic program. The strength of the methodology lies partially in its ability to construct good feasible solutions from information provided by the dual. Thus, the need for branch-and-bound is eliminated. In addition, the inclusion of the ramping constraint provides new insight into the limitations of current techniques. Computational experience with the proposed algorithm indicates that problems containing up to 100 units and 48 time periods can be readily solved in reasonable times. Duality gaps of less than 1 % were achieved in all cases.

MSC:

90B30	Production models
90C39	Dynamic programming
65K05	Numerical mathematical programming methods
90C11	Mixed integer programming
90B35	Deterministic scheduling theory in operations research
90C90	Applications of mathematical programming

Keywords:

electric utilities; unit commitment problem; thermal-electric generators; mixed integer nonlinear control problem; Lagrangian relaxation; nested dynamic program; branch-and-bound; ramping constraint