## 5 An O(1)-Competitive Algorithm
### Potential Function \(\Phi(t)\)  
An active job \(j\) is lagging, if \((pwk_{a}(j,\ t)-pwk_{o}(j,\ t))>0\). Since \(t\) is the instantaneous time, this factor is dropped from the rest of the analysis. For any processor \(u\), let \(LG_{u}\ =\ \left\{j_{1},\ j_{2},\ \ldots,\ j_{lg_{u}}\right\}\) be a group of lagging jobs using MBS and these jobs are managed in the ascending order of latest time (when any job gets changed into lagging job). \(LG\ =\ \sum_{u\ =\ 1}^{m}LG_{u}\) is a set of all lagging jobs on all \(m\) processors. Further, \(imp_{lg_{u}}\ =\ \sum_{i\ =\ 1}^{lg_{u}}\ imp_{u}(j_{i})\) is the sum of the importance of lagging jobs on a processor \(u\). Following this, \(imp_{lg}\ =\ \sum_{u\ =\ 1}^{m}\ imp_{lg_{u}}\) is the sum of the importance of lagging jobs on all \(m\) processors. Our potential function \(\Phi(t)\) for IbF+E is the addition of all potential values of \(m\) processors. \[\Phi(t)\ =\ \sum_{u\ =\ 1}^{m}\ \Phi_{u}(t)\  
**Proof.** If \(n_{a}\leq m\) then every processor executes not more than one job, i.e., every job is processed on individual processor.  
(a) It is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\). To calculate the upper-bound, the worst-case is considered which occurs if Opt executes a job on \(u\) with the largest coefficient \(c_{lg_{u}}~{}=~{}imp_{lg_{u}}^{1-2\delta}\). At this time, \(\omega_{i}\) increases at the rate of \(s_{uo}\) (because of Opt on \(u\)). The count of lagging jobs on some \(u\) may be only one.  
\[\frac{d\Phi_{uo}}{dt}\leq c_{lg_{u}}s_{uo}\leq imp_{lg_{u}}^{1-2\delta}.s_{uo} \tag{7}\]  
Using [PERSON]'s inequality, Lemma 1 (Equation (6)) in (7) such that \(A=s_{uo}\), \(B=\left(imp_{lg_{u}}\right)^{1-2\delta}\), \(x=\alpha\) and \(y=\frac{1}{1-2\delta}\) we have:  
\[\frac{d\Phi_{uo}}{dt}\leq\frac{s_{uo}}{\alpha}+(1-2\delta).imp_{lg_{u}} \tag{8}\]  
(b) Next, it is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\). To compute the upper-bound, consider that a lagging job \(j_{i}\) on \(u\) is executed at the rate of \(\left(s_{uu}.\frac{imp_{u}(j_{i})}{\sum_{k~{}=~{}1}^{uu}imp_{u}(j_{k})}\right)\) or \(\left(s_{uu}.\frac{imp_{u}(j_{i})}{imp_{uu}}\right)\), therefore, the change in \(\omega_{i}\) is at the rate of \(\left(-s_{uu}.\frac{imp_{u}(j_{i})}{imp_{uu}}\right)\). \[\frac{d\Phi_{ua}}{dt}=\sum\
olimits_{i~{}=~{}1}^{lg_{u}}\left(\left(\sum \
olimits_{k~{}=~{}1}^{i}imp_{u}(j_{k})\right)^{1-2\delta}\right)\left(-s_{ uu}.\frac{imp_{u}(j_{i})}{imp_{uu}}\right)\]  
As only one job executes on a processor, therefore \(\frac{imp_{u}(j_{i})}{imp_{uu}}~{}=~{}1\) and \(lg_{u}~{}=~{}i~{}=~{}1\),  
\[ \begin{array}{l}\frac{d\Phi_{ua}}{dt}~{}=~{}\left(imp_{lg_{u}}^{1-2\delta} \right).(-s_{ua})\\ \frac{d\Phi_{ua}}{dt}~{}=~{}-\left(s_{ua}.imp_{lg_{u}}^{1-2\delta}\right)\end{array}  \tag{9}\]  
\(\Box\)  
**Lemma 3**. : _If \(n_{a}\leq m\) and \(imp_{lg_{u}}>\eta^{\alpha}\)_  
(a) \(\frac{d\Phi_{uu}}{dt}\leq\left(\frac{1}{1-\delta}\right)\)_-imp_{lg_{u}}; (b) \(\frac{d\Phi_{ua}}{dt}~{}=~{}-\frac{(1+\
icefrac{{\Delta}}{{3m}})}{(1-\delta)} \cdot imp_{lg_{u}}\)_  
**Proof. ** If \(n_{a}\leq m\) then every processor executes not more than one job, i.e., every job is processed on individual processor. (a) It is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\). To calculate the upper-bound, the worst-case is considered which occurs if Opt executes a job on \(u\) with the largest coefficient \(c_{lg_{u}}~{}=~{}\left(\frac{1}{1-\delta}\right)\cdot imp_{lg_{u}}\cdot\eta^{ -1}\). At this time, \(\omega_{i}\) increases at the rate of \(s_{uo}\) (because of Opt on \(u\)) where \(s_{uo}\leq\eta\). The count of lagging jobs on any \(u\) may be only one. \[ \begin{array}{l}\frac{d\Phi_{uu}}{dt}\leq c_{lg_{u}}s_{uo}\leq c_{lg_{u}} \cdot\eta_{1}~{}=~{}\left(\frac{1}{1-\delta}\right)\cdot imp_{lg_{u}}\cdot \eta^{-1}\cdot\eta\\ \frac{d\Phi_{uu}}{dt}\leq\left(\frac{1}{1-\delta}\right)imp_{lg_{u}}\end{array}  \tag{10}\]  
(b) Next, it is required to upper-bound \(\frac{d\Phi_{uu}}{dt}\) for a processor \(u\).