Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization



Liu, Fu-Hong, Liu, Hsiang-Hsuan and Wong, Prudence WH ORCID: 0000-0001-7935-7245
(2016) Non-preemptive Scheduling in a Smart Grid Model and its Implications on Machine Minimization. Algorithmica, 82 (12). pp. 3415-3457.

[img] Text
1602.06659v3.pdf - Submitted version

Download (709kB)

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 problem is fixed parameter tractable. We also show that the online algorithm is asymptotically optimal when the objective is to minimize the peak load. In addition, we observe that the classical non-preemptive machine minimization problem is a special case of the smart grid problem with min-peak objective, and show that we can solve the non-preemptive machine minimization problem asymptotically optimally.

Item Type: Article
Uncontrolled Keywords: cs.DS, cs.DS
Depositing User: Symplectic Admin
Date Deposited: 29 Aug 2017 07:41
Last Modified: 19 Jan 2023 06:56
DOI: 10.1007/s00453-020-00733-3
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3009203