# Energy-Aware Online Non-Clairvoyant Scheduling Using Speed Scaling with Arbitrary Power Function
## 4 A 2-Comptitive Scheduling Highest Scaled Importance First (HSIF)
### Scaled Importance-Based Flow Plus Energy
#### 4.1.2 Potential Function \(\Phi(t)\)  
Let Opt be the optimal offline adversary that minimizes scaled importance based flow time plus energy. At any time \(t\), let \(pr_{o}^{t}\) and \(pr_{h}^{t}\) be the total scaled importance of all active jobs for Opt and HSIF,respectively. At any time \(t\), let \(pr_{o}^{t}(a)\) and \(pr_{h}^{t}(a)\) be the total scaled importance of all active jobs with at least a ascending inverse density in Opt and HSIF, respectively. Let \(pr^{t}(a)\) be \(\big{(}pr_{h}^{t}(a)-pr_{o}^{t}(a)\big{)}_{+}\), where \(\big{(}\cdot\big{)}_{+}=max\{0,\ \cdot\}\). A potential function can be defined as follows:  
\[\Phi(t)=2\int_{a=0}^{\infty}\int_{x=0}^{pr^{t}(a)}P^{\prime}(Q(x))dx\ da\]  
Since \(P^{\prime}(x)\) and \(Q(x)\) are increasing, \(P^{\prime}(Q(x))\) is an increasing function of \(x\). Therefore,  
\[\frac{d\Phi(t)}{dt}=2\int_{0}^{\infty}P^{\prime}\big{(}Q\big{(}pr^{t}(a)\big{)} \big{)}\frac{d\big{(}pr^{t}(a)\big{)}}{dt}\ da\]  
To observe the effectiveness of the algorithm, it is required to observe the boundary condition, job arrival and completion condition, and running conditions. For the boundary condition, one can observe that before arrival of any job and after completion of all jobs \(pr^{t}(a)=0\), \(\forall\) a. Therefore, \(\Phi(t)=0\). On arrival of any job, the value of \(pr^{t}(a)\) remains the same for all \(a\), therefore \(\Phi(t)\) remains the same. The scaled importance of a job decreases continuously when a job is executed by the HSIF or Opt, hence \(\Phi(t)\) does not decrease on completion of a job. At any other time t when no job arrives or completes, it is required to prove that the following inequality follows:  
\[pr_{h}^{t}+P\big{(}s_{h}^{t}\big{)}+\frac{d\Phi(t)}{dt}\leq c\cdot\big{(}pr_{o }^{t}+P\big{(}s_{o}^{t}\big{)}\big{)},\textit{where }c=2\]  
Since t is the current time only, the superscript t is omitted from the parameters in the rest of the analysis. Let \(a_{o}\) and \(a_{h}\) be the minimum ascending inverse densities of an active job using Opt and HSIF, respectively. Let \(a_{h}\) (or \(a_{o}\)) be \(\infty\) if HSIF (or Opt) has no active job. HSIF executes jobs on the basis of the highest scaled importance first at a speed \(s_{h}\). Therefore, \(pr_{h}(a)\) decreases at the rate of \((s_{h}/a_{h})\), \(\forall a\in[0,\ a_{h}]\), and \(pr_{h}(a)\) remains the same for \(a>a_{h}\). Similarly, \(pr_{o}(a)\) changes at the rate of \((s_{o}/a_{o})\)\(\forall a\in[0,\ a_{o}]\), and \(pr_{o}(a)\) remains the same for \(a>a_{o}\). Rest of the analysis is based on the three cases depending on \(pr_{o}>pr_{h}\), \(pr_{o}>pr_{h}\) and \(pr_{o}=pr_{h}\). **Case 1: If \(pr_{o}>pr_{h}\) then, one can observe that**  
**(a)**\(\forall a\in[0,\ a_{o}]\), \(pr_{o}(a)=pr_{o}>pr_{h}\geq pr_{h}(a)\)  
\(\Rightarrow\forall a\in[0,\ a_{o}]\), \(pr(a)=\big{(}pr_{h}^{t}(a)-pr_{o}^{t}(a)\big{)}_{+}=0\). Therefore, \(\mathrm{pr}(a)\) remains the same. Hence for \(a\leq a_{o}\) the rate of change of \(pr(a)=0\), i.e., \(\frac{d}{dt}pr(a)=0\). **(b)** If \(a>a_{o}\), \(pr_{o}(a)\) remains the same, therefore the rate of change of \(pr(a)\leq 0\), i.e., \(\frac{d}{dt}pr(a)\leq 0\). Considering both the sub cases it is observed that  
\[\frac{d\Phi}{dt}=2\int_{0}^{\infty}P^{\prime}(Q(pr(a)))\frac{d(pr(a))}{dt}\ da \ \leq 0\]  
\[\Rightarrow pr_{h}+P(s_{h})+\frac{d\Phi}{dt}\leq 2\ pr_{h}<(pr_{o}+P(s_{o}))\]  
Hence the running condition is satisfied for \(pr_{o}>pr_{h}\).