Methods for virtual machine scheduling with uncertain execution times in cloud computing

Execution times are crucial for effectiveness of tasks or jobs scheduling. It is very hard to accurately estimate execution times because they are influenced by many factors. Though there are some models for traditional machine scheduling problems, no attention has been paid on virtual machine scheduling in cloud computing. Based on cloud agent (VM administrator, scheduler or intelligent procedure) experiences, we develop integrated learning effects models to obtain accurate execution times. Based on the constructed learning effects model for single virtual machine scheduling, optimal schedule rules are proposed for minimizing makespan, the total completion time and the sum of (square) completion times. Problems with the total weighted completion time and the maximum lateness minimization are proved to be optimally solvable in polynomial time only for certain assumptions. Furthermore, we adapt the developed learning effects model to two special m-virtual machine MapReduce scenarios, for which optimal schedule rules are introduced correspondingly. Optimal solutions are demonstrated by examples of the problems under study using the constructed rules.