Cloud Scheduling with Discrete Charging Units

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).