Non-preemptive Scheduling in a Smart Grid Model and Its Implications on Machine Minimization
- PDF / 2,619,118 Bytes
- 43 Pages / 439.37 x 666.142 pts Page_size
- 113 Downloads / 200 Views
Non‑preemptive Scheduling in a Smart Grid Model and Its Implications on Machine Minimization Fu‑Hong Liu1 · Hsiang‑Hsuan Liu2 · Prudence W. H. Wong3 Received: 5 August 2017 / Accepted: 5 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 the best-possible in an asymptotically sense 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 achieve the best-possible competitive ratio in an asymptotically sense when solving the non-preemptive machine minimization problem. Keywords Scheduling · Non-preemptive · Convex cost function · Online algorithms · Fixed parameter tractable
1 Introduction The smart grid [14, 46, 47] is a power grid system [17, 37] that makes power generation, distribution and consumption more efficient through information and communication technologies compared to the traditional power system. Peak demand A preliminary version of this paper titled “Optimal Nonpreemptive Scheduling in a Smart Grid Model” appeared in Proceedings of the 27th International Symposium on Algorithms and Computation, ISAAC 2016 [30] and some results are improved in this version. * Fu‑Hong Liu [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Algorithmica
hours happen only for a short duration, which makes existing electrical grid less efficient. It has been noted in [9] that in the US power grid, 10% of all generation assets and 25% of distribution infrastructure are required for less than 400 hours per year, roughly 5% of the time [47]. Demand response management [16, 21, 22, 34, 51] attempts to overcome this problem by shifting users’ demand to off-peak hours in order to reduce peak load [7, 26, 33, 36, 39, 42]. Research initiatives in the area include [24, 32, 40, 45]. We study a scheduling problem arising in demand response management. The electricity grids supports demand response mechanisms and obtains energy efficiency by organizing customer consumption of electricity in response to supply conditions. It is demonstrated in [34] that demand
Data Loading...
