# Energy-Aware Online Non-Clairvoyant Scheduling Using Speed Scaling with Arbitrary Power Function
## 1 Introduction
Initial researches [16; 17; 18; 19; 20; 21] considered the objective to minimize the flow time, i.e., only the quality of service criteria. Later on, some new algorithms were proposed with an objective of minimizing the weighted/prioritized flow time [22; 23; 24], i.e., not only the quality of service but also the reduction in energy consumption by the machines. [PERSON] and [PERSON] [25] studied the scheduling problem with an objective to minimize the flow time plus energy in the dynamic speed scaling approach. Online non-clairvoyant job scheduling algorithms are studied less extensively than online clairvoyant job scheduling algorithms. Highest Density First (HDF) is optimal [10] in online clairvoyant settings for the objective of fractional weighted/importance-based flow time plus energy. HDF cannot operate in the non-clairvoyant settings. HDF [10] algorithm always runs the job of highest density and the density of a job is its importance divided by its size. In non-clairvoyant settings, the complete size of a job is only known at the completion of it. Therefore, the HDF cannot be used directly in the non-clairvoyant settings. [PERSON] et al. [11] proposed an algorithm (Non-Clairvoyant) NC for the known job densities in the online non-clairvoyant settings on a uniprocessor, using the traditional power function. In NC, the density (i.e., the importance/size) is known at arrival time. Speed scaling and job assignment policy used in non-clairvoyant algorithm NC-PAR (Non-Clairvoyant on Parallel identical machines) is based on a clairvoyant algorithmic approach, which shows that NC-PAR is not a pure non-clairvoyant algorithm. WLAPS (Weighted Latest Arrival Processor Sharing) [26] provides high priority to some latest jobs which increases the average response time. WLAPS does not schedule a fixed portion of active jobs rather it selects jobs having total importance equal to a fixed portion of the total importance of all active jobs. It needs to update the importance of some job to avoid under-scheduling or over-scheduling. It does not consider the importance of jobs in appropriate manner and suffers from high average response time. The above-mentioned deficiencies motivated us to continue the study in this field for the objective of minimizing importance-based importance based flow time plus energy. In this paper, an online non-clairvoyant scheduling Highest Scaled Importance First (HSIF) is proposed with an objective of minimizing the scaled importance-based flow time plus energy. In HSIF, rather than the complete importance of a job the scaled importance of a job is considered. The scaled importance of a job increases if the job is new and it does not get the chance to execute; consequently, the starvation condition is avoided. If a job executes then the scaled importance will decrease. It the HSIF, the impotence of any job is calculated and it is the scaled value of the fixed importance of that job. As the importance is time dependent it can be termed as dynamic importance/scaled importance. This balances the speed and energy consumption. The speed of a processor is a function of the total scaled importance of all active jobs. The competitive ratio of HSIF is analysed using the arbitrary power function and amortized potential function analysis. The remaining paper is segregated in the following sections: Next section describes some related previous scheduling algorithms and their results. Section 3 provides notations used in our paper and definitions necessary for discussion. In Section 4, the authors have explained a 2-competitive scheduling Highest Scaled Importance First (HSIF), which includes the algorithm as well as the comparison of HSIF with the optimal algorithm using amortized analysis (potential function). In Section 5, a set of jobs and traditional power function is used to examine the performance of HSIF. Section 6 draws some concluding remarks and future scope of this study.