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 flowtime of the scheduler over T rounds and that of the best-fixed scheduling in hindsight. We propose an algorithm whose regret bounds are O(n(2) root T ln(nk) for general bipartite graphs, O((n(2)/k(1/2))root T ln(nk) for the complete bipartite graphs, and O(n(2)/k)root T ln(nk) for the disjoint star graphs, respectively. We also give a lower regret bound of Omega ((n(2)/k)root T) for the disjoint star graphs, implying that our regret bounds are almost optimal.