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. In: The 27th International Symposium on Algorithms and Computation (ISAAC), 2016-12-12 - 2016-12-14, Australia.

This is the latest version of this item.

	Text paper52.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (563kB)
	Text LIPIcs-ISAAC-2016-53.pdf - Published version Available under License : See the attached licence file. Download (564kB)

Abstract

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:	19 Jan 2023 06:56
DOI:	10.4230/LIPIcs.ISAAC.2016.53
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3009287