Release Round Robin: R3 an energy-aware non-clairvoyant scheduling on speed bounded processors


In the past few years the online scheduling problem has been studied extensively under clairvoyant settings and a relatively lessamount of evolution is observed under non-clairvoyant setting. A non-clairvoyant scheduling problem has its practical significance.We study online non-clairvoyant scheduling problem of minimizing total weighted flow plus energy. Usually weights in weightedflow study are assumed to be system generated and they are allocated to the jobs at their release time. In this paper, weights are notprovided by the system, rather they are generated using the release time by the scheduler. The scheduler maintains a balance of themachine's state to obtain an efficient schedule of jobs and avoid energy wastage. This paper provides potential analysis of aweighted generalization of the power management algorithm which is coupled with Weighted Round Robin. We adopt thetraditional model of power function P ¼ sa, where s, P and a > 1 are speed of processor, power and a constant, respectively. Weintroduced Release Round Robin (R3) scheduling algorithm with competitive ratio O (3a/t) when using a processor with themaximum speed (3 þ t) times higher than the maximum speed of the Optimal offline adversary, where 0 < t (3a1).