On the online minimization of completion time in an energy harvesting system

Authors:

Abstract
This paper considers a single-transmitter energy harvesting system and looks into the problem of completion time minimization from the worst-case point of view. In offline study, an optimal algorithm [1] is given to yield the minimum completion time of transmission. However, for online algorithms, the randomness of future energy arrivals adds to the difficulty of scheduling, thus the offline minimum completion time cannot always be reached. This leads to the question "What is the deterministic performance bound of online algorithms compared to the offline optimum". By a game-theoretic method, this paper shows that with an infinite-sized battery, there exist several algorithms that guarantee a completion time no more than the twice of its offline counterpart for all possible energy arrivals, and more importantly that the ratio of two cannot be further reduced. This property is of great significance especially when reliability is valued in the system.

This publication has 12 references indexed in Scilit: