Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput

Baruch Schieber, Bhargav Samineni, Soroush Vahidi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Motivated by baterryless IoT devices, we consider the following scheduling problem. The input includes n unit time jobs, where each job has a release time, due date, energy requirement, and weight. We consider time to be slotted; hence, all time related job values refer to slots. Let. The input also includes an value for every time slot t, which is the energy harvestable on that slot. Energy is harvested at time slots when no job is executed. The objective is to find a feasible schedule that maximizes the weight of the scheduled jobs. A schedule is feasible if for every job in the schedule and its corresponding slot, and the available energy before is at least. To the best of our knowledge, we are the first to consider the theoretical aspects of this problem. In this work we show the following. (1) A polynomial time algorithm when all jobs have identical and. (2) A -approximation algorithm when all jobs have identical but arbitrary and. (3) An FPTAS when all jobs have identical and but arbitrary. (4) Reductions showing that all the variants of the problem in which at least one of the attributes are not identical for all jobs are.

Original languageEnglish (US)
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 17th International Conference and Workshops, WALCOM 2023, Proceedings
EditorsChun-Cheng Lin, Bertrand M. Lin, Giuseppe Liotta
PublisherSpringer Science and Business Media Deutschland GmbH
Pages305-316
Number of pages12
ISBN (Print)9783031270505
DOIs
StatePublished - 2023
Event17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 - Hsinchu, Taiwan, Province of China
Duration: Mar 22 2023Mar 24 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13973 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023
Country/TerritoryTaiwan, Province of China
CityHsinchu
Period3/22/233/24/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Approximation algorithms
  • IoT
  • NP-hardness
  • Scheduling
  • Throughput maximization

Fingerprint

Dive into the research topics of 'Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput'. Together they form a unique fingerprint.

Cite this