Online Job Scheduling with <i>K</i> Servers

DOI Web Site 19 References Open Access
  • JIANG Xuanke
    Computational Learning theory Team, RIKEN-Advanced Intelligence Project (AIP) Department of Information Science and Technology, Kyushu University
  • HASHIMA Sherief
    Computational Learning theory Team, RIKEN-Advanced Intelligence Project (AIP)
  • HATANO Kohei
    Computational Learning theory Team, RIKEN-Advanced Intelligence Project (AIP) Department of Informatics, Kyushu University
  • TAKIMOTO Eiji
    Department of Informatics, Kyushu University

Search this article

Description

<p>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 $O(n^2 \sqrt{T\ln (nk)})$ for general bipartite graphs, $O((n^2/k^{1/2}) \sqrt{T\ln (nk)})$ for the complete bipartite graphs, and $O((n^2/k) \sqrt{T \ln (nk)}$ for the disjoint star graphs, respectively. We also give a lower regret bound of $\Omega((n^2/k) \sqrt{T})$ for the disjoint star graphs, implying that our regret bounds are almost optimal.</p>

Journal

References(19)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top