Balancing SRPT and FCFS via Starvation Mitigation

In this paper, we balance two fundamental yet seemingly contradicting job scheduling objectives, namely the average flow time and the maximum flow time. Specifically, Shortest Remaining Processing Time (SRPT) minimizes the average flow time but may lead to job starvation. In contrast, First-Come-First-Served (FCFS) minimizes the maximum flow time but may result in poor average flow time. A natural way to balance these two objectives is to minimize the $\ell_2$ norm of flow time. For this problem, no online algorithm is known to achieve a better competitive ratio than SRPT and FCFS. It can be argued that SRPT and FCFS complement each other. To exploit this complementary relationship, we mitigate the starvation caused by SRPT with the help of FCFS. Specifically, when there are starving jobs, we process the job that becomes starving first. The main question is: when should a job be viewed as starving? If the timing is too early or too late, then the algorithm still behaves like FCFS or SRPT, respectively. In this paper, we answer the above question by estimating the number of jobs. Our algorithm significantly improves upon SRPT and FCFS in terms of the competitive ratio for minimizing the $\ell_2$ norm of flow time, even if the estimate is loose.