The algorithm needs to decide whether to start new VMs, or shut them down, and should probably use the following information
Our forecast of the arrival rate \(\lambda(t)\) over the coming hour
How far the VMs are from their next billing period
The length of the queue right now, and forecasts for the queues (or the absence of them)
A few heuristics that I can think off:
Calculate the estimated penalty we have to pay in the next 1 hour (integrating the waiting time distribution over the penalty function) for \(c\) and \(c + 1\) VMs. If the difference is greater than 1, we should start an extra VM.
If we forecast a peak in demand 1 hour from now, do we start the VMs half an hour before so that the peak of demand falls in the middle of the VM cycle?
Never shut down a VM until 1 second before its billing cycle
If significant penalties were incurred for the last few minutes, add a VM
If a large number of the VMs has been idle for the last few minutes, shut down a VM