English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Online algorithm has been an emerging area of interest for researchers invarious domains of computer science. The online $m$-machine list schedulingproblem introduced by Graham has gained theoretical as well as practicalsignificance in the development of competitive analysis as a performancemeasure for online algorithms. In this paper, we study and explore theperformance of Graham's online \textit{list scheduling algorithm(LSA)} forindependent jobs. In the literature, \textit{LSA} has already been proved to be$2-\frac{1}{m}$ competitive, where $m$ is the number of machines. We presenttwo new upper bound results on competitive analysis of \textit{LSA}. We obtainupper bounds on the competitive ratio of $2-\frac{2}{m}$ and$2-\frac{m^2-m+1}{m^2}$ respectively for practically significant two specialclasses of input job sequences. Our analytical results can motivate thepractitioners to design improved competitive online algorithms for the$m$-machine list scheduling problem by characterization of real life inputsequences.

New Competitive Analysis Results of Online List Scheduling Algorithm