In this paper, we investigate the dynamic task scheduling problem with stochastic task arrival times and due dates in the UAV-based intelligent on-demand meal delivery system (UIOMDS) to improve the efficiency. The objective is to minimize the total tardiness. The new constraints and characteristics introduced by UAVs in the problem model are fully studied. An iterated heuristic framework SES (Stochastic Event Scheduling) is proposed to periodically schedule tasks, which consists of a task collection and a dynamic task scheduling phases. Two task collection strategies are introduced and three Roulette-based flight dispatching approaches are employed. A simulated annealing based local search method is integrated to optimize the solutions. The experimental results show that the proposed algorithm is robust and more effective compared with other two existing algorithms.
3 June 2024 in IEEE Transactions on Mobile Computing
In the paper, the Unmanned Aerial Vehicle (UAV) path planning and task offloading problem in UAV-assisted mobile edge computing (MEC) systems is investigated. A bi-criterion ant colony optimization (bi-ACO) framework is proposed for the considered problem with the objectives of minimizing the total cost and the completion time, meanwhile satisfying the energy, deadline, location, and priority constraints. In the bi-ACO framework, multiple heterogeneous colonies are introduced with different preferences of objectives. Each colony maintains five pairs of pheromone matrices for constructing feasible solutions. Besides the colony settings, three key components of bi-ACO are delicately designed: feasible solution generation method (FSGM) to construct a feasible solution, solution division method (SDM) to improve obtained solutions of good quality, and pheromone update method (PUM) to updates pheromone matrices by pheromone evaporation operation and pheromone enhancement operation based on the preferences of colonies. Four Pareto-based metrics are introduced to evaluate the performance of the compared algorithms. Experimental results show that the proposal outperforms the compared baseline algorithms in effectiveness and robustness.
22 October 2021 in IEEE Transactions on Intelligent Transportation Systems
In this paper, we investigate the task scheduling problem in the UAV-enable Mobile Edge-Computing (MEC) system with the objectives of minimizing the cost and the completion time. A NSGA-II algorithm is proposed for the problem under study. The solution is represented as a two-dimension location sequence. Major components of NSGA-II are delicately designed including the feasible solution generation method (FSGM) and genetic operations of crossover, mutation and selection. Three strategies are introduced in FSGM. A simulated annealing local search is integrated into the crossover operation, and meanwhile two novel mutation methods are proposed. The Pareto-based metrics are introduced to evaluate the performance of the compared algorithms. Experimental results show that the proposal is more effective and robust than the three existing algorithms.
9 January 2020 in IEEE Transactions on Services Computing
Electricity prices differ during different time periods and change from place to place. Cloud workflow applications often require geo-distributed data which is transmitted among heterogeneous servers in intra- and inter- data centers. Such varying electricity prices and data transmission time bring great challenges when optimizing the energy cost for scheduling tasks in workflow applications to heterogeneous servers in cloud data centers. In this paper, we minimize the total electricity cost in a deadline constrained energy-aware workflow scheduling problem with data being geographically distributed across data centers. A scheduling framework is proposed. Strategies are developed to sequence workflow applications, divide deadlines and sort tasks. An adaptive local search method is presented to improve solutions during the search process which dynamically balances intensification using neighborhood structures of increasing size. Components and parameter values are statistically calibrated over a comprehensive set of random instances. The proposed algorithm is compared to modified classical algorithms for similar problems. Experimental results demonstrate the effectiveness of the proposal for the considered problem.
15 January 2018 in IEEE Transactions on Parallel and Distributed Systems
We consider a special workflow scheduling problem in a hybrid-cloud-based workflow management system in which tasks are linearly dependent, compute-intensive, stochastic, deadline-constrained and executed on elastic and distributed cloud resources. This kind of problems closely resemble many real-time and workflow-based applications. Three optimization objectives are explored: number, usage time and utilization of rented VMs. An iterated heuristic framework is presented to schedule jobs event by event which mainly consists of job collecting and event scheduling. Two job collecting strategies are proposed and two timetabling methods are developed. The proposed methods are calibrated through detailed designs of experiments and sound statistical techniques. With the calibrated components and parameters, the proposed algorithm is compared to existing methods for related problems. Experimental results show that the proposal is robust and effective for the problems under study.
22 June 2020 in IEEE Transactions on Parallel and Distributed Systems
We investigate a workflow scheduling problem with stochastic task arrival times and fuzzy task processing times and due dates. The problem is common in many real-time and workflow-based applications, where tasks with fixed stage number and linearly dependency are executed on scalable cloud resources with multiple price options. The challenges lie in proposing effective, stable, and robust algorithms under stochastic and fuzzy tasks. A triangle fuzzy number-based model is formulated. Two metrics are explored: the cost and the degree of satisfaction. An iterated heuristic framework is proposed to periodically schedule tasks, which consists of a task collection and a fuzzy task scheduling phases. Two task collection strategies are presented and two task prioritization strategies are employed. In order to achieve a high satisfaction degree, deadline constraints are defined at both job and task levels. By designing delicate experiments and applying sophisticated statistical techniques, experimental results show that the proposed algorithm is more effective and robust than the two existing methods.