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

AbstractIn the past few years the online scheduling problem has been studied extensively under clairvoyant settings and a relatively less amount 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 weighted flow study are assumed to be system generated and they are allocated to the jobs at their release time. In this paper, weights are not provided by the system, rather they are generated using the release time by the scheduler. The scheduler maintains a balance of the machine's state to obtain an efficient schedule of jobs and avoid energy wastage. This paper provides potential analysis of a weighted generalization of the power management algorithm which is coupled with Weighted Round Robin. We adopt the traditional model of power function P=sα, where s, P and α>1 are speed of processor, power and a constant, respectively. We introduced Release Round Robin (R3) scheduling algorithm with competitive ratio O (3α/τ) when using a processor with the maximum speed (3 + τ) times higher than the maximum speed of the Optimal offline adversary, where 0