Load Balancing Algorithms For Task Scheduling With Resource Sharing

With the development of society and economic,consumption pattern based on cooperation and sharing has been accepted by more and more people.Meanwhile,the popularity of intelligent devices highly promotes resource aggregation of society and sharing economics in various fields(e.g.,ride-sharing,group-buying and crowd-sensing).Operation pattern with resource sharing has great potential in enhancing the utility of social resource and operation efficiency,while current scheduling strategy does not fully take advantage of resource sharing.In this thesis,we study three task scheduling optimization problems in scheduling systems based on resource sharing.Firstly,we study the task schedule optimization problem in a single-device schedule system.By allowing delay tolerance and resource sharing,we aim to design algorithms to minimize the total busy time to complete all tasks.For the optimization problem respectively in offline scenario and online scenario,we design offline exact algorithm and 4-aprroximatin online algorithm.Secondly,we consider multiple devices and design load balancing algorithms to minimize the maximum load of the devices.We describe the schedule system model and introduce the offline problem and online problem.For the offline scenario,we design a 2-approximation algorithm based on dynamic programming and prove the approximation ratio.For the online scenario,we design an 8-competitive online algorithm.Finally,we model the real time location-aware scheduling problem and develop a load balancing algorithm by considering time constraint,location constraint and resource constraint.For the real time scheduling problem,we design device searching algorithm and feasibility checking algorithm to schedule the devices.For all the algorithms in this thesis,we conduct simulations and validate the efficiency of the proposed algorithms.