Paper Info
Title
Subset Selection for Hybrid Task Scheduling with General Cost Constraints
Abstract
Subset selection problem for task scheduling with general cost constraints exists widely in IoT applications. Its objective is to select several profitable tasks to execute under routing and cost constraints such that the total profit is maximized. Most prior arts only focus on either online tasks or offline tasks, which are usually inapplicable in practical applications where online tasks and offline tasks co-exist. In this paper, we study the subset selection problem for HybrId Task Scheduling with general cost constraints (HITS), in which both online and offline tasks are scheduled to maximize the overall profit. We first divide the HITS problem into online and offline subproblems and propose two algorithms to solve them with bounded approximation ratios. Furthermore, we propose an approximation algorithm for the hybrid scenario where both online and offline tasks are considered. Extensive simulations show that our proposed algorithm outperforms baseline algorithms by 21.5% averagely in profit and also performs well in pure online/offline scenarios. We further demonstrate the feasibility of our algorithm through test-bed experiments in a realistic scene.
Year
DOI
Venue
2022
10.1109/INFOCOM48880.2022.9796947
IEEE INFOCOM 2022 - IEEE Conference on Computer Communications
Keywords
DocType
ISSN
subset selection problem,hybrid task scheduling,general cost constraints,HITS problem,profit maximization,approximation algorithm
Conference
0743-166X
ISBN
Citations 
PageRank 
978-1-6654-5823-8
0
0.34
References 
Authors
0
5
Name
Order
Citations
PageRank
Yao Sun14118.81
Chia-Lin Yang2103376.39
Ju Ren362158.80
Pichao Wang449327.18
Ling Wang52745165.98