TY - GEN
T1 - Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput
AU - Schieber, Baruch
AU - Samineni, Bhargav
AU - Vahidi, Soroush
N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - IoT
KW - NP-hardness
KW - Scheduling
KW - Throughput maximization
UR - http://www.scopus.com/inward/record.url?scp=85151066638&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85151066638&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-27051-2_26
DO - 10.1007/978-3-031-27051-2_26
M3 - Conference contribution
AN - SCOPUS:85151066638
SN - 9783031270505
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 305
EP - 316
BT - WALCOM
A2 - Lin, Chun-Cheng
A2 - Lin, Bertrand M.
A2 - Liotta, Giuseppe
PB - Springer Science and Business Media Deutschland GmbH
T2 - 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023
Y2 - 22 March 2023 through 24 March 2023
ER -