论文标题
将实时工作与能量收获交织以最大化吞吐量
Interweaving Real-Time Jobs with Energy Harvesting to Maximize Throughput
论文作者
论文摘要
在无生产物联网设备的动机中，我们考虑以下调度问题。输入包括$ n $单位时间作业$ \ MATHCAL {J} = \ {J_1，\ ldots，J_n \} $，其中每个作业$ J_I $都有一个发布时间$ r_i $，截止日期$ d_i $，engile $ d_i $，engile $ d_i $，engile $ e_i $和权重$ w_i $。我们考虑时间被插入；因此，所有相关的工作价值都指的是插槽。令$ t = \ max_i \ {d_i \} $。该输入还包括每个时间插槽$ t $（$ 1 \ leq t \ leq t $）的$ H_T $值，这是该插槽上的能量。当没有工作时，在时间段段收获能量。目的是找到一个可行的时间表，以最大程度地提高预定作业的重量。时间表是可行的。据我们所知，我们是第一个考虑这个问题的理论方面的人。 在这项工作中，我们显示以下内容。 （1）当所有作业都具有相同的$ r_i，d_i $和$ w_i $时，多项式时间算法。 （2）$ \ frac {1} {2} $ - 近似算法当所有作业都具有相同的$ w_i $，但任意$ r_i $和$ d_i $。 （3）当所有作业都具有相同的$ r_i $和$ d_i $，但任意$ w_i $时，FPTA。 （4）减少表明，所有问题中至少一个属性，$ d_i $或$ w_i $中的所有属性中的所有变体都不相同。
Motivated by baterryless IoT devices, we consider the following scheduling problem. The input includes $n$ unit time jobs $\mathcal{J} = \{J_1, \ldots, J_n\}$, 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\{d_i\}$. The input also includes an $h_t$ value for every time slot $t$ ($1 \leq t \leq 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 $J_j$ in the schedule and its corresponding slot $t_j$, $t_{j} \neq t_{j'}$ if ${j} \neq {j'}$, $r_j \leq t_j \leq 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 NP-Hard.
