Motivated by batteryless IoT devices, we consider the following scheduling problem. The input includes n unit time jobs \(\mathcal{J}= \left\{ J_1, \ldots, J_n \right\} \) , where each job \(J_i\) has a release time \(r_i\) , due date \(d_i\) , energy requirement \(e_i\) , and weight \(w_i\) . We consider time to be slotted; hence, all time related job values refer to slots. Let \(T=\max _i\left\{ d_i \right\} \) . The input also includes an h(t) value for every time slot t \(\left( 1 \le t \le T \right) \) , 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} \ne t_{j'}\) if \({j} \ne {j'}\) , \(r_j \le t_j \le 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 \(\frac{1}{2}\) -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 \(\textsf{NP-Hard}\) .
