An Energy-Efficient Online Parallel Scheduling Algorithm for Cloud Data Centers

This paper considers online energy-efficient scheduling of real-time virtual machines (VMs) for Cloud data centers. Each request is associated with a starttime, a end-time, a processing time and demand for a Physical Machine (PM) capacity. The goal is to schedule all of the requests non-preemptively in their start-timeend- time windows, subjecting to PM capacity constraints, such that total busy time of all used PMs is minimized (called MinTBT-ON for abbreviation). This problem is a fundamental scheduling problem for parallel jobs allocation on mutliple machines, it has important applications in power-aware scheduling in cloud computing, optical network design and customer service systems and other related areas. Offline scheduling to minimize busy time is NP-hard already in the special case where all jobs have the same processing time and can be scheduled in a fixed time interval. One best-known result for MinTBT-ON problem is a g-competitive algorithm for general instances using First-Fit algorithm for unit-size jobs, where g is the total capacity of a PM. In this paper, a B-competitive algorithm, GRID is proposed and proved for general case, where B is a natural number and 1 < B < g. More results are obtained and applied to Cloud computing to improve energy-efficiency.