Cloud Scheduling with Discrete Charging Units

Ming Ming Tan, Runtian Ren, Xueyan Tang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We consider a scheduling problem for running jobs on machines rented from the cloud. Cloud service providers such as Amazon EC2 and Google Cloud offer machines to rent on demand, and charge the rental usage by a specific interval of time, say at an hourly rate. This pricing model creates an interesting optimization problem called Interval Scheduling with Discrete Charging Units (ISDCU) which assigns jobs to run on the machines with the objective of minimizing the rental cost. In this paper, we study the problem of ISDCU where each machine can process a maximum of gg jobs simultaneously. We focus on interval jobs where each job must be assigned to a machine upon its arrival and run for a required processing length. We show that ISDCU is NP-hard even for the case of g = 1g=1. We also show that no deterministic online algorithm can achieve a competitive ratio better than \max \lbrace 2, g\rbracemax{2,g} in the non-clairvoyant setting, and better than \max \lbrace 3/2, g\rbracemax{3/2,g} in the clairvoyant setting. Lastly, we develop and analyze several online algorithms, most of which achieve a competitive ratio of O(g)O(g).

Original languageEnglish (US)
Article number8588304
Pages (from-to)1541-1551
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number7
StatePublished - Jul 1 2019
Externally publishedYes


  • Cloud scheduling
  • interval scheduling
  • online algorithm

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Cloud Scheduling with Discrete Charging Units'. Together they form a unique fingerprint.

Cite this