Minimizing total busy time in offline parallel scheduling with application to energy efficiency in cloud computing. (5th November 2013)

• Record Type: Journal Article
• Authors: Tian, Wenhong; Yeo, Chee Shin; Smari, Waleed; Fiore, Sandro; Trinitis, Carsten; Ranjan, Rajiv; Buyya, Rajkumar; Nepal, Surya; Georgakopulos, Dimitrios
• Is Part Of: Concurrency and computation. Volume 27:Number 9(2015:Jun.)
• Page Start: 2470
• Page End: 2488
• Publication Date: 2013-11-05
• Subjects: Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.3176
• Languages: English
• ISSNs: 1532-0626

Abstract

<abstract abstract-type="main" id="cpe3176-abs-0001"> <title>Summary</title> <p>Our paper considers the following fundamental scheduling problem. There are <italic>n</italic> deterministic jobs to be scheduled offline on multiple identical machines, which have bounded capacities. Each job is associated with a start‐time, an end‐time, a process time, and demand for machine capacity. The goal is to schedule all of the jobs non‐preemptively in their start‐time‐end‐time windows, subject to machine capacity constraints such that the total busy time of the machines is minimized. We refer to this problem as minimizing the total busy time for the scheduling of multiple identical machines (MinTBT). This problem has important applications in power‐aware scheduling for Cloud computing, optical network design, customer service systems, and other related areas. Scheduling to minimize busy times is already NP‐hard in the special case where all jobs have the same process time and can be scheduled in a fixed time interval. One best‐known result for this problem is a 5‐approximation algorithm for special instances using first‐fit‐decreasing algorithm. In this paper, we propose and prove a 3‐approximation algorithm, modified first‐fit‐decreasing‐earliest for the general case and obtain more results for special cases. We then show how our results are applied in cloud computing to improve the energy efficiency. Copyright © 2013 John Wiley &amp; Sons, Ltd.</p> </abstract>