Online Job Scheduling with K Servers

In this paper, we investigate an online job scheduling problem with n jobs and k servers, where the accessibilities between the jobs and the servers are given as a bipartite graph. The scheduler is tasked with minimizing the regret, defined as the difference between the total flow time of the scheduler over T rounds and that of the best-fixed scheduling in hindsight. We propose an algorithm whose regret bounds are (Formula presented) for general bipartite graphs, (Formula presented) for the complete bipartite graphs, and (Formula presented) for the disjoint star graphs, respectively. We also give a lower regret bound of (Formula presented) for the disjoint star graphs, implying that our regret bounds are almost optimal.