Title
Cost-aware demand scheduling for delay tolerant applications
Abstract
In this paper, we study the problem of demand scheduling for delay tolerant applications. With regard to the time-varying resource cost per unit size of the demand, we study two optimization problems: (1) how to minimize the peak resource usage, while making sure that each demand is served before the deadline; (2) how to minimize the longest completion time of all the demands under a given maximum allowable resource constraint. For the first problem, we prove that it is NP-hard, under the general setting that the demands are of different sizes and require several continuous time slots to complete. We then provide an integer linear programming solution, and propose an efficient heuristic algorithm. For a special case of the same size demand and single serving time slot, the proposed algorithm is proved to be optimal. We further study a special case that all the demands have the same deadline, and prove that the proposed algorithm can achieve three times the optimal solution if the number of serving time slots required for each demand is at most two. For the second problem, we also prove it to be NP-hard and formulate it into an integer linear programming. An efficient polynomial-time algorithm is then proposed, whose completion time is proved to be at most two times the optimal minimum completion time under a specific setting. Finally, simulation results demonstrate the superiorities of the proposed schemes.
Year
DOI
Venue
2015
10.1016/j.jnca.2015.04.002
Journal of Network and Computer Applications
Keywords
Field
DocType
Demand scheduling,Peak resource reduction,Completion time minimization
Mathematical optimization,Scheduling (computing),Computer science,Heuristic (computer science),Integer programming,Optimization problem,Distributed computing,Special case
Journal
Volume
Issue
ISSN
53
C
1084-8045
Citations 
PageRank 
References 
2
0.49
18
Authors
5
Name
Order
Citations
PageRank
Xiumin Wang113511.68
Chau Yuen24493263.28
Xiaoming Chen330128.67
Naveed Ul L. Hassan423117.78
Yiming Ouyang5187.51