Please use this identifier to cite or link to this item:
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):3511-3520
Publisher: IEEE
Issue Date: 2017
ISSN: 1045-9219
Statement of
Longkun Guo and Hong Shen
Abstract: Clouds, such as Amazon Infrastructure-as-a-Service (IaaS) clouds and EMC Hybrid Cloud, impose growing requirements of resource-efficiency 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/C-k 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 (2C-k/C-k)(1-ϵ) for tight deadlines [17], and C/C-k · s/s-1/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 polynomial-time solvable. Then we present a greedy algorithm and its equivalent primal-dual algorithm for the complementary problem of BFS. Both algorithms have an approximation ratio of C/C-k, and time complexity O(n² + nT), where n is the number of jobs and T is the number of time slots. As a by-product, we show that the BFS admits a polynomial-time 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 for more information.
DOI: 10.1109/TPDS.2017.2731843
Grant ID:
Published version:
Appears in Collections:Aurora harvest 8
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.