Dynamic Scheduling for Emergency Tasks on Distributed Imaging Satellites with Task Merging

Scheduling plays a significant role in improving observation effectiveness of distributed imaging satellites. Although extensive satellite scheduling algorithms have been proposed, none of them focuses on dynamic scheduling for emergency tasks. In this paper, a novel multi-objective dynamic scheduli...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2014-09, Vol.25 (9), p.2275-2285
Main Authors: Jianjiang Wang, Xiaomin Zhu, Dishan Qiu, Yang, Laurence T.
Format: Article
Language:English
Subjects:
Algorithms
backward shift
Distributed imaging satellites
Dynamic scheduling
Dynamics
Emergencies
emergency
Heuristic
Heuristic algorithms
Image resolution
Imaging
Merging
Production scheduling
rehabilitation
Satellite imagery
Satellites
Scheduling
task merging
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Scheduling plays a significant role in improving observation effectiveness of distributed imaging satellites. Although extensive satellite scheduling algorithms have been proposed, none of them focuses on dynamic scheduling for emergency tasks. In this paper, a novel multi-objective dynamic scheduling model for emergency tasks on distributed imaging satellites is established for the first time. To improve user's satisfaction ratio and resource utilization, we propose the task merging strategy: establishing a task merging graph (TMG) model and proposing a task merging algorithm-CP-TM based on clique partition. In addition, a rehabilitation technique is suggested to overcome the disadvantage that task merging will make tasks have less imaging opportunities. To further enhance the schedulability, the task backward shift in the waiting sequence is considered in our study. Furthermore, a novel dynamic scheduling algorithm called TMBSR-DES is presented, which comprehensively considers task merging, backward shift, and rehabilitation. To demonstrate the superiority of our TMBSR-DES, we conduct extensive experiments by simulations to compare TMBSR-DES with three existing algorithm-RBHA, RTSSA, and LSA, as well as three baseline algorithms-BS-DES, TMR-DES, and TMBS-DES. The experimental results indicate that TMBSR-DES outperforms the others and is suitable for emergency task scheduling.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2013.156