An Application of Lagrangian Relaxation to Scheduling in Power-Generation Systems

Two major decisions are made when scheduling the operations of a fossil-fuel power-generating system over a short time horizon. The “unit commitment” decision indicates what generating units are to be in use at each point in time. The “economic dispatch” decision is the allocation of system demand among the generating units in operation at any point in time. Both these decisions must be considered to achieve a least-cost schedule over the short time horizon. In this paper we present a mixed integer programming model for the short time horizon power-scheduling problem. The objective of the model is to minimize the sum of the unit commitment and economic dispatch costs subject to demand, reserve, and generator capacity and generator schedule constraints. A branch-and-bound algorithm is proposed using a Lagrangian method to decompose the problem into single generator problems. A sub gradient method is used to select the Lagrange multipliers that maximize the lower bound produced by the relaxation. We present computational results that indicate the technique is capable of solving large problems to within acceptable error tolerances.