Please use this identifier to cite or link to this item:
http://hdl.handle.net/2440/110415
Citations  
Scopus  Web of Science®  Altmetric 

?

?

Type:  Journal article 
Title:  Efficient approximation algorithms for the bounded flexible scheduling problem in clouds 
Author:  Guo, L. Shen, H. 
Citation:  IEEE Transactions on Parallel and Distributed Systems, 2017; 28(12):35113520 
Publisher:  IEEE 
Issue Date:  2017 
ISSN:  10459219 15582183 
Statement of Responsibility:  Longkun Guo and Hong Shen 
Abstract:  Clouds, such as Amazon InfrastructureasaService (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resourceefficiency scheduling. The bounded flexible scheduling (BFS) problem is one of the problems proposed to meet such requirements. In BFS, we are given a set of identical machines and a set of jobs, each of which is with a value, a workload, a deadline and a parallelism degree, i.e., the maximum number of machines on which the job can execute concurrently. The problem is to compute an assignment of the given jobs to the machines, such that the total value of the jobs successfully completed by their deadlines is maximized. This paper presents a factor C/Ck approximation algorithm for BFS, where k is the maximum parallelism degree and C is the capacity of the system (i.e., the number of machines). Since C ≫ k in BFS, our result significantly improves the known best approximation ratio of (2Ck/Ck)(1ϵ) for tight deadlines [17], and C/Ck · s/s1/s for loose deadlines [18] on a slackness ratios > 1 that is the maximum ratio between a job's earliest actual finish time and its deadline. We first propose feasibility condition to determine whether an instance of BFS is feasible, i.e., whether there exists a scheduling according to which all jobs can finish before their deadlines, which is the key to achieve the ratio improvement of our algorithm. To prove the correctness of the feasibility condition, we give a simple linear program (LP) for a weaker version of BFS, and show that it is with an integral polyhedron and hence the version of BFS is polynomialtime solvable. Then we present a greedy algorithm and its equivalent primaldual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C/Ck, and time complexity O(n² + nT), where n is the number of jobs and T is the number of time slots. As a byproduct, we show that the BFS admits a polynomialtime approximation scheme (PTAS) when T is fixed. 
Keywords:  Approximation algorithm; primal dual method; bounded flexible scheduling; resource allocation 
Rights:  Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. 
RMID:  0030076079 
DOI:  10.1109/TPDS.2017.2731843 
Grant ID:  http://purl.org/auresearch/grants/arc/DP150104871 
Appears in Collections:  Computer Science publications 
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.