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

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.


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
Full Text: DOI