We study a scheduling problem arising in demand response management in smartgrid. Consumers send in power requests with a flexible feasible time intervalduring which their requests can be served. The grid controller, upon receivingpower requests, schedules each request within the specified interval. Theelectricity cost is measured by a convex function of the load in each timeslot.The objective is to schedule all requests with the minimum total electricitycost. Previous work has studied cases where jobs have unit power requirementand unit duration. We extend the study to arbitrary power requirement andduration, which has been shown to be NP-hard. We give the first onlinealgorithm for the general problem, and prove that the problem is fixedparameter tractable. We also show that the online algorithm is asymptoticallyoptimal when the objective is to minimize the peak load. In addition, weobserve that the classical non-preemptive machine minimization problem is aspecial case of the smart grid problem with min-peak objective, and show thatwe can solve the non-preemptive machine minimization problem asymptoticallyoptimally.
展开▼
