Optimal nonpreemptive scheduling in a smart grid model



Liu, FH, Liu, HH and Wong, PWH ORCID: 0000-0001-7935-7245
(2016) Optimal nonpreemptive scheduling in a smart grid model. .

This is the latest version of this item.

[img] Text
paper52.pdf - Accepted Version
Available under License : See the attached licence file.

Download (563kB)
[img] Text
LIPIcs-ISAAC-2016-53.pdf - Published Version
Available under License : See the attached licence file.

Download (564kB)

Abstract

© Fu-Hong Liu, Hsiang-Hsuan Liu, and Prudence W. H. Wong. We study a scheduling problem arising in demand response management in smart grid. Consumers send in power requests with a flexible feasible time interval during which their requests can be served. The grid controller, upon receiving power requests, schedules each request within the specified interval. The electricity cost is measured by a convex function of the load in each timeslot. The objective is to schedule all requests with the minimum total electricity cost. Previous work has studied cases where jobs have unit power requirement and unit duration. We extend the study to arbitrary power requirement and duration, which has been shown to be NP-hard. We give the first online algorithm for the general problem, and prove that the worst case competitive ratio is asymptotically optimal. We also prove that the problem is fixed parameter tractable. Due to space limit, the missing proofs are presented in the full paper.

Item Type: Conference or Workshop Item (Unspecified)
Depositing User: Symplectic Admin
Date Deposited: 17 Nov 2017 11:39
Last Modified: 29 Sep 2020 08:20
DOI: 10.4230/LIPIcs.ISAAC.2016.53
URI: http://livrepository.liverpool.ac.uk/id/eprint/3009287

Available Versions of this Item