An algorithm for optimal scheduling of a class of cascade water supply systems

The problem of determining overall optimized control schedules for a class of cascade water supply systems containing only fixed speed pumps is examined. The system control is by nature an on-off type. The optimal scheduling problem can be formulated as dynamical optimal control problems wit purely discrete symbols, discrete controls and also with continuous intermediate variables interrelated in a highly non-linear way. An efficient problem solver is proposed. Its high efficiency is achieved by exploiting, through a suitable decomposition, certain structural properties of the problem. Lagrange relaxation is applied in order to break down the time structure of discrete control variables. The decomposition also enables consideration of mixed integer optimization on purely static grounds. The dynamical optimization constitutes only that part of the solver which deals with entirely continuous variables. There is a duality gap in the problem. However, certain, but not complete, information obtained through solving the dual problem (dual optimal information) is close to that which corresponds to the true (primal) optimal solution. This is an important property of the scheduling problem, which together with the problem structure creates a basis for the solver design.