Resource assignment algorithms for vehicular clouds
Date
2016
Authors
Nabi, Mahmudun
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Abstract
In this thesis, we study the task scheduling problem in vehicular clouds. It falls in the category of unrelated parallel machine scheduling problems. Resource assignment in vehicular clouds must deal with the transient nature of the cloud resources and a relaxed definition of non-preemptive tasks. Despite a rich literature in machine scheduling and grid computing, the resource assignment problem in vehicular clouds has not been examined yet. We show that even the problem of finding a minimum cost schedule for a single task over unrelated machines is NP-hard. We then provide a fully polynomial time approximation scheme and a greedy approximation for scheduling a single task. We extend these algorithms to the case of scheduling n tasks. We validate our algorithms through extensive simulations that use synthetically generated data as well as real data extracted from vehicle mobility and grid computing workload traces. Our contributions are, to the best of our knowledge, the first quantitative analysis of the computational power of vehicular clouds.
Description
Keywords
availability constraint , non-preemption , smart vehicles , task scheduling problems , vehicular resource utilization