New Competitive Analysis Results of Online List Scheduling Algorithm

EasyChair Preprint 14910

Abstract

The online algorithm has been an emerging area of interest for researchers in various domains of Computing. The online $m$-machine list scheduling problem introduced by Graham has gained theoretical as well as practical significance in the development of competitive analysis as a performance measure for online algorithms. In this paper, we study and explore the performance of Graham's online \textit{list scheduling algorithm(LSA)} for independent jobs. In the literature, algorithm \textit{LSA} has been shown $(2-\frac{1}{m})$-competitive, where $m$ is the number of machines. We present two new upper bound results on competitive analysis of \textit{LSA}. We obtain upper bounds on the competitive ratio of $2-\frac{2}{m}$ and $2-\frac{m^2-m+1}{m^2}$ respectively for practically significant two special classes of input job sequences. Our analytical results can motivate the practitioners to design improved competitive online algorithms for the $m$-machine list scheduling problem by characterizing the real-life input sequences.

Keyphrases: Makespan, Non-preemptive, competitive analysis, identical machines, online scheduling

@booklet{EasyChair:14910,
  author    = {Rakesh Mohanty and Debasis Dwibedy and Shreeya Swagatika Sahoo},
  title     = {New Competitive Analysis Results of Online List Scheduling Algorithm},
  howpublished = {EasyChair Preprint 14910},
  year      = {EasyChair, 2024}}