Abstract 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}$$ .

We design and implement two single-pass semi-streaming algorithms for the maximum weight $k$-disjoint matching ($k$-DM) problem. Given an integer $k$, the $k$-DM problem is to find $k$ pairwise edge-disjoint matchings such that the sum of the weights of the matchings is maximized. For $k \geq 2$, this problem is NP-hard. Our first algorithm is based on the primal-dual framework of a linear programming relaxation of the problem and is $\frac{1}{3+\varepsilon}$-approximate. We also develop an approximation preserving reduction from $k$-DM to the maximum weight $b$-matching problem. Leveraging this reduction and an existing semi-streaming $b$-matching algorithm, we design a $(\frac{1}{2+\varepsilon})(1 - \frac{1}{k+1})$-approximate semi-streaming algorithm for $k$-DM. For any constant $\varepsilon > 0$, both of these algorithms require $O(nk \log_{1+\varepsilon}^2 n)$ bits of space. To the best of our knowledge, this is the first study of semi-streaming algorithms for the $k$-DM problem. We compare our two algorithms to state-of-the-art offline algorithms on 95 real-world and synthetic test problems, including thirteen graphs generated from data center network traces. On these instances, our streaming algorithms used significantly less memory (ranging from 6$\times$ to 512$\times$ less) and were faster in runtime than the offline algorithms. Our solutions were often within 5% of the best weights from the offline algorithms. We highlight that the existing offline algorithms run out of 1 TB memory for most of the large instances ($>1$ billion edges), whereas our streaming algorithms can solve these problems using only 100 GB memory for $k=8$.