Optimal control approach to scheduling power supply facilities: theory and heuristics

We consider a scheduling problem for a power charging facility under hard bounds on the deliverable power. Appliances require an amount of energy for a certain time interval at specific times. Under congestion, power supply to the appliances may be possibly delayed and the goal of the scheduler is to minimize the average waiting time. We formulate the problem as an optimal control problem. We study three versions of the problem: the case when no interruption of an appliance is possible after admission, the case in which it is possible, and the case in which the overall energy can be delivered at an arbitrary rate over time. We show that these three versions of the problem can be faced in the proposed framework by suitably choosing the cost function. We then propose some relaxations to derive lower bounds for the cost. These lower bounds will be used to test some heuristics with real data available from the literature.