Online scheduling on a CPU-GPU cluster

Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


We consider the online scheduling problem in a CPU-GPU cluster. In this problem there are two sets of processors, the CPU processors and GPU processors. Each job has two distinct processing times, one for the CPU processor and the other for the GPU processor. Once a job is released, a decision should be made immediately about which processor it should be assigned to. The goal is to minimize the makespan, i.e., the largest completion time among all the processors. Such a problem could be seen as an intermediate model between the scheduling problem on identical machines and unrelated machines. We provide a 3.85-competitive online algorithm for this problem and show that no online algorithm exists with competitive ratio strictly less than 2. We also consider two special cases of this problem, the balanced case where the number of CPU processors equals to that of GPU processors, and the one-sided case where there is only one CPU or GPU processor. We provide a (1 + v3)-competitive algorithm for the balanced case, and a 3-competitive algorithm for the one-sided case.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 10th International Conference, TAMC 2013, Proceedings
Number of pages9
ISBN (Print)9783642382352
StatePublished - 2013
Event10th International Conference on Theory and Applications of Models of Computation, TAMC 2013 - Hong Kong, China
Duration: May 20 2013May 22 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7876 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Conference on Theory and Applications of Models of Computation, TAMC 2013
CityHong Kong


  • CPU-GPU cluster
  • Competitive ratio
  • Online scheduling
  • Unrelated machine scheduling


Dive into the research topics of 'Online scheduling on a CPU-GPU cluster'. Together they form a unique fingerprint.

Cite this