Competitive algorithms for demand response management in a smart grid

Vincent Chau (), Shengzhong Feng () and Nguyễn Kim Thắng ()
Additional contact information
Vincent Chau: Southeast University
Shengzhong Feng: Chinese Academy of Sciences
Nguyễn Kim Thắng: IBISC, University Paris Saclay

Journal of Scheduling, 2023, vol. 26, issue 6, No 3, 535-542

Abstract: Abstract We consider a scheduling problem that abstracts a model of demand response management in a smart grid. We investigate the problem with a set of unrelated machines, and each job j (representing a client demand) is characterized by its release date, and its power request function expressing its request demand at specific times. Each machine has an energy power function, and the energy cost incurred at a time depends on the load of the machine at that time. The goal is to find a non-migrative schedule that minimizes the total energy. We give a competitive algorithm for the problem in the online setting where the competitive ratio depends (only) on the power functions of machines. In the setting with typical energy function $$P(z) = z^{\nu }$$ P ( z ) = z ν , the algorithm is $$\varTheta (\nu ^{\nu })$$ Θ ( ν ν ) -competitive, which is optimal up to a constant factor. Our algorithm is robust in the sense that the guarantee holds for arbitrary request demands of clients. This enables flexibility on the choices of clients in shaping their demands—a desired property in a smart grid. We also consider a particular case in the offline setting in which jobs have unit processing time, constant power request, and identical machines with energy function $$P(z) = z^{\nu }$$ P ( z ) = z ν . We present a $$2^{\nu }$$ 2 ν -approximation algorithm for this case.

Keywords: Smart grid; Scheduling; Approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00690-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:6:d:10.1007_s10951-021-00690-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00690-x

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().