Interweaving real-time jobs with energy harvesting to maximize throughput

), 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

J_{j}

in the schedule and its corresponding slot

t_{j}

,

t_{j} e q t_{j^{'}}

if

j e q j^{'}

,

r_{j} l e q t_{j} l e q d_{j}

, and the available energy before

t_{j}

is at least

e_{j}

. 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

r_{i}, d_{i}

and

w_{i}

. (2) A

f r a c 12

-approximation algorithm when all jobs have identical

w_{i}

but arbitrary

r_{i}

and

d_{i}

. (3) An FPTAS when all jobs have identical

r_{i}

and

d_{i}

but arbitrary

w_{i}

. (4) Reductions showing that all the variants of the problem in which at least one of the attributes

r_{i}

,

d_{i}

, or

w_{i}

are not identical for all jobs are NP-Hard.

Cites work

This page was built for publication: Interweaving real-time jobs with energy harvesting to maximize throughput

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6091174)