# The Novel Heuristic for Data Transmission Dynamic Scheduling Problems

Authors: Hao Xu; Yue Zhao; Li-Ning Xing; You Zhou
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The data transmission dynamic scheduling is a process that allocates the ground stations and available time windows to the data transmission tasks dynamically for improving the resource utilization. A novel heuristic is proposed to solve the data transmission dynamic scheduling problem. The characteristic of this heuristic is the dynamic hybridization of simple rules. Experimental results suggest that the proposed algorithm is correct, feasible, and available. The dynamic hybridization of simple rules can largely improve the efficiency of scheduling.


---

## Body

## 1. Introduction

With the approaching of information age, the number of communication satellites has increased constantly, and the request of satellite data transmission is also increased. Because of the cost of ground stations, the contradiction between resources and demands is more serious than before. Under the limitations of ground resources, the data transmission scheduling that shows how to properly allocate limited ground resources to meet the request of data transmission has become an important problem to be solved. The data transmission scheduling is a process that allocates the ground stations and available time windows to data transmission tasks under the certain constraints and assumed conditions [1, 2]. It is a kind of complex constraint satisfaction optimization problem and has the characteristics of time window constraint, multiresource constraint, and high confliction.Recently, many scholars have widely investigated the data transmission scheduling problems. They proposed some reasonable scheduling models and scientific scheduling algorithms [3–5]. These models and approaches mainly focus on the static scheduling. In the actual scheduling process, the resource constraint and task attribute will be changed due to many reasons. During the execution of scheduling plan, it needs to be adjusted dynamically to ensure the maximization of scheduling objectives.With the consideration of actual scheduling demands, the idea of dynamic scheduling and automatic planning are proposed based on the analysis of data transmission scheduling. The mathematical model is constructed to describe the problem with unified standard. The scheduling framework is designed according to the actual scheduling process. Some basic rules and rule-based heuristics are designed according to the problem characteristics and practical operating experience. The best scheduling plan for each algorithm is obtained through the comprehensive evaluation by TOPSIS. The algorithm can be evaluated through comparing the comprehensive index of algorithms.


## 2. Data Transmission Dynamic Scheduling Problem

The data transmission dynamic scheduling is a process that dynamically allocates the ground station resources and time windows for executing the data transmission [6–9]; it needs the satellites to adjust in real time according to the situation of data transmission. Therefore, the idea of dynamic scheduling and automatic planning are proposed based on the analysis of data transmission scheduling. This idea has omitted the link of summarizing information by the control center, which really realized the automation and real time of data transmission. The dynamic scheduling was completed via automatic planning and the initial plans were rescheduled in real time. It requires the less computing power, makes fast decision and dynamic real-time decision.


### 2.1. Basic Symbols

The basic symbols of data transmission dynamic scheduling problems can be summarized as in the following five tuples [10–12]:
(1)Θ=(T,R,C,TW,thorizon).T
=
{
t
1
,
t
2
,
…
,
t
n
} means the task set; the task attributes are denoted as TA=(ID,D,P,EST,LET), in which ID denotes the task identification, D denotes the duration of each task, P denotes the task priority, EST denotes the earliest start time for each task, and LET denotes the latest end time.R denotes the resource set, and the resource attributes are denoted as RA=(S,G), in which S={S1,S2,…,SSN} denotes the satellite resource and G={G1,G2,…,GGN} denotes the ground station resource.The main constraint of data transmission dynamic scheduling isC=Ct∧Cr∧Ctw, in where Ct denotes the task constraint, namely, the execution of tasks. Cr denoted the relation constraint, it is, a data transmission resource can only be allocated to one task at any time. The time constraint is represented by Ctw,   indicating the performance of all the tasks in the given period of time.TW
=
{
t
w
1
,
t
w
2
,
…
,
t
w
n
} denotes the time window set, namely, the quantity of time windows between each task and each satellite. thorizon denotes the deadline of the whole scheduling process.


### 2.2. Mathematical Model

The data transmission dynamic scheduling model can be represented by the following tuples:(2)Θl+1=(Θl,αlΘ,DI,thorizon),
in which Θl denotes the initial scheduling problem Θ=(T,R,C,TW,thorizon) before a new task arrives, and αlΘ means the initial scheduling plan. DI=(Tnew,Rnew,Cnew,TWnew) denotes the dynamic scheduling information set, representing the change of task of data transmission in scheduling process, resource, constraint condition, and time window. Cnew=Ctnew∧Crnew∧Ctwnew denotes the dynamic constraint set, and
(3)Ctnew:si=si(αlΘ),if(si+di≤t),or((si<t),(si+di>t)),i∈N,(4)Crnew:{Crnew(Tr)=∧((Tr=0)∨(∪SSN≠⌀)),Crnew(Tr)=∧((Tr=0)∨(∪Qr,j≠⌀)),hhhhhhhhhhhhhhhhhhhhhhhr=1,2,…,m,Ctwnew:t≤sr≤thorizon,t≤sr+dr≤thorizon.The first constraint indicates that, in original scheduling plan, the task dispatched or was dispatched before the available time window studied in dynamic scheduling time can no more be rescheduled.Crnew(Tr)=∧((Tr=0)∨(∪SSN≠⌀)) indicates that it is established only if either Tr=0 or ∪SSN≠⌀ is met, which means that there are two situations over whether the task is dispatched, and, meanwhile, the task should obtain a data transmission resource at least.C
r
new
(
T
r
)
=
∧
(
(
T
r
=
0
)
∨
(
∪
Q
r
,
j
≠
⌀
)
) indicates that it is established only if either Tr=0 or ∪Qr,j≠⌀ is met, which means that there are two kinds of scheduling for the task, and, meanwhile, each task can obtain the available time window under certain resource; Qr,j denotes the demand variable, namely, the demand of available time window between the ith task and the jth ground station.C
tw
new
:
t
≤
s
r
≤
t
horizon
,
t
≤
s
r
+
d
r
≤
t
horizon denotes the dynamic time constraint, in which sr and dr are, respectively, the start time and the time required to finish the rth task scheduling; namely, any task of data transmission must be completed before the given deadline.In the data transmission dynamic scheduling problem, the scheduling plan should transmit the information to destination in time as fast as possible to ensure the effectiveness [13–16]. It mainly contains the indexes of total priority of scheduling task and the task scheduling success ratio in this research. The total priority of scheduling tasks is set to reflect the validity of scheduling plan, and its formula is listed as follows:
(5)SP=∑i=1nTIiPi.
Here, TI={TI1,TI2,…,TIn} denotes the decision variable of tasks, ∀i≤n, TIi={0,1}:TIi=1 means being scheduled, and TIi=0 means not being scheduled. An effective scheduling plan should successfully dispatch as many tasks as possible. Hence, the task scheduling success ratio is set to reflect the validity of scheduling plan, and its formula is listed as follows:
(6)TP=∑i=1nTIiN,
in which N denotes the total number of dynamic scheduling tasks.


## 2.1. Basic Symbols

The basic symbols of data transmission dynamic scheduling problems can be summarized as in the following five tuples [10–12]:
(1)Θ=(T,R,C,TW,thorizon).T
=
{
t
1
,
t
2
,
…
,
t
n
} means the task set; the task attributes are denoted as TA=(ID,D,P,EST,LET), in which ID denotes the task identification, D denotes the duration of each task, P denotes the task priority, EST denotes the earliest start time for each task, and LET denotes the latest end time.R denotes the resource set, and the resource attributes are denoted as RA=(S,G), in which S={S1,S2,…,SSN} denotes the satellite resource and G={G1,G2,…,GGN} denotes the ground station resource.The main constraint of data transmission dynamic scheduling isC=Ct∧Cr∧Ctw, in where Ct denotes the task constraint, namely, the execution of tasks. Cr denoted the relation constraint, it is, a data transmission resource can only be allocated to one task at any time. The time constraint is represented by Ctw,   indicating the performance of all the tasks in the given period of time.TW
=
{
t
w
1
,
t
w
2
,
…
,
t
w
n
} denotes the time window set, namely, the quantity of time windows between each task and each satellite. thorizon denotes the deadline of the whole scheduling process.


## 2.2. Mathematical Model

The data transmission dynamic scheduling model can be represented by the following tuples:(2)Θl+1=(Θl,αlΘ,DI,thorizon),
in which Θl denotes the initial scheduling problem Θ=(T,R,C,TW,thorizon) before a new task arrives, and αlΘ means the initial scheduling plan. DI=(Tnew,Rnew,Cnew,TWnew) denotes the dynamic scheduling information set, representing the change of task of data transmission in scheduling process, resource, constraint condition, and time window. Cnew=Ctnew∧Crnew∧Ctwnew denotes the dynamic constraint set, and
(3)Ctnew:si=si(αlΘ),if(si+di≤t),or((si<t),(si+di>t)),i∈N,(4)Crnew:{Crnew(Tr)=∧((Tr=0)∨(∪SSN≠⌀)),Crnew(Tr)=∧((Tr=0)∨(∪Qr,j≠⌀)),hhhhhhhhhhhhhhhhhhhhhhhr=1,2,…,m,Ctwnew:t≤sr≤thorizon,t≤sr+dr≤thorizon.The first constraint indicates that, in original scheduling plan, the task dispatched or was dispatched before the available time window studied in dynamic scheduling time can no more be rescheduled.Crnew(Tr)=∧((Tr=0)∨(∪SSN≠⌀)) indicates that it is established only if either Tr=0 or ∪SSN≠⌀ is met, which means that there are two situations over whether the task is dispatched, and, meanwhile, the task should obtain a data transmission resource at least.C
r
new
(
T
r
)
=
∧
(
(
T
r
=
0
)
∨
(
∪
Q
r
,
j
≠
⌀
)
) indicates that it is established only if either Tr=0 or ∪Qr,j≠⌀ is met, which means that there are two kinds of scheduling for the task, and, meanwhile, each task can obtain the available time window under certain resource; Qr,j denotes the demand variable, namely, the demand of available time window between the ith task and the jth ground station.C
tw
new
:
t
≤
s
r
≤
t
horizon
,
t
≤
s
r
+
d
r
≤
t
horizon denotes the dynamic time constraint, in which sr and dr are, respectively, the start time and the time required to finish the rth task scheduling; namely, any task of data transmission must be completed before the given deadline.In the data transmission dynamic scheduling problem, the scheduling plan should transmit the information to destination in time as fast as possible to ensure the effectiveness [13–16]. It mainly contains the indexes of total priority of scheduling task and the task scheduling success ratio in this research. The total priority of scheduling tasks is set to reflect the validity of scheduling plan, and its formula is listed as follows:
(5)SP=∑i=1nTIiPi.
Here, TI={TI1,TI2,…,TIn} denotes the decision variable of tasks, ∀i≤n, TIi={0,1}:TIi=1 means being scheduled, and TIi=0 means not being scheduled. An effective scheduling plan should successfully dispatch as many tasks as possible. Hence, the task scheduling success ratio is set to reflect the validity of scheduling plan, and its formula is listed as follows:
(6)TP=∑i=1nTIiN,
in which N denotes the total number of dynamic scheduling tasks.


## 3. Heuristic Algorithms

The data transmission dynamic scheduling implements the real-time scheduling by automatic planning. The basic framework of proposed heuristic is designed according to the actual dynamic scheduling process, the basic rules of dynamic scheduling were summarized from previous planning and scheduling experience, and finally the rule-based heuristic algorithm was proposed. The basic framework of proposed heuristic is shown in Figure1.Figure 1
The basic framework of proposed heuristic.The essence of data transmission dynamic scheduling is, when executing the task based on initial scheduling plan, rescheduling it according to dynamic interaction information. The advantage of rule-based heuristic is being without plenty of computation, which has reduced the demand for allocation of computing resources in scheduling operation and avoided the combination explosion [17–21]. Only when the proper rule is selected, the corresponding scheduling strategy can be produced [22, 23]. At present, the deterministic single rule heuristic has been widely employed to the data transmission scheduling [24, 25]. In order to solve the data transmission dynamic scheduling effectively, a novel heuristic is proposed based on the existing deterministic single rule. The characteristic of this novel heuristic is the dynamic hybridization of deterministic simple rules. Since the data transmission dynamic scheduling is a kind of multiobjective problem, the TOPSIS was employed to make a comprehensive evaluation of different objectives.


### 3.1. Deterministic Single Rules

The following kinds of deterministic single rules are considered in this research work. These deterministic single rules determine the task processing sequence according to the given attribute (such as, task priority, task duration, earliest start time and latest end time etc.) firstly and then arrange each task following the previous sequence. The realization process of deterministic single rules is simple, its idea is easy to understand, and the execution speed is relatively fast.(1)
Deterministic sequence based on the priority (DSP): it determines the task processing sequence according to the task priority (prior to sequencing the task with the large priority).(2)
Deterministic sequence based on the duration (DSD): it determines the task processing sequence according to the duration (prior to sequencing the task with the small duration).(3)
Deterministic sequence based on the start time (DSST): it determines the task processing sequence based on the start time (prior to sequencing the task with the small earliest start time).(4)
Deterministic sequence based on the end time (DSET): it determines the task processing sequence according to the end time (prior to sequencing the task with the small latest end time).


### 3.2. Random Single Rules

Four kinds of random single rules are considered in this work. These random single rules randomly determine the task processing sequence based on the certain attributes (for example, task priority, task duration, earliest start time, and latest end time etc.) firstly and then arrange each task following the previous sequence. The realization process of random single rules is simple and the obtained solution is fairly outstanding.(1)  Random Sequence Based on the Priority (RSP). It randomly determines the task processing sequence based on the task priority. For each task, it will be selected with the following probability:
(7)Pri=Pi∑i=1nPi.
Here, Pri denotes the selected probability of task i, Pi denotes the priority of task i, and n denotes the number of tasks.(2)  Random Sequence Based on the Duration (RSD). This random single rule randomly determines the task processing sequence according to the duration. For each task, it will be selected with the following probability:
(8)Pri=Di′∑i=1nDi′.
Here, Pri denotes the selected probability of task i, and
(9)Di′=2×max1≤i≤n{Di}-Di.Di denotes the duration of task i.(3)  Random Sequence Based on the Start Time (RSST). It randomly determines the task processing sequence based on the start time. For each task, it will be selected with the following probability:
(10)Pri=ESTi′∑i=1nESTi′.
Here, Pri denotes the selected probability of task i, and
(11)ESTi′=2×max1≤i≤n{ESTi}-ESTi.ESTi denotes the earliest start time of task i.(4)  Random Sequence Based on the End Time (RSET). It randomly determines the task processing sequence based on the end time. For each task, it will be selected with the following probability:
(12)Pri=LETi′∑i=1nLETi′.
Here, Pri denotes the selected probability of task i, and
(13)LETi′=2×max1≤i≤n{LETi}-LETi.LETi denotes the latest end time of task i.


### 3.3. Random Hybrid Rules

Based on the previous kinds of random single rules, the random hybrid rule (RHR) is proposed to the data transmission dynamic scheduling. the random hybrid rule randomly determines the task processing sequence based on the different random single rules firstly and then arranges each task following the previous sequence. The realization process of random hybrid rule is slightly complex and the obtained solution is fairly outstanding. The random hybrid rule is defined as follows:(14)RHR={RSP0≤r<p1RSDp1≤r<p2RSSTp2≤r<p3RSETp3≤r≤1.
Here, r is a random number and p1, p2, and p3 are three predefined thresholds. In the random hybrid rule, the RSP rule is selected with the probability p1, the RSD rule is selected with the probability p2-p1, the RSST rule is selected with the probability p3-p2, and the TSET is selected with the probability 1-p3. After repeatedly employing the random single rules, they will obtain multiple different solutions. In order to compare these solutions, the TOPSIS was utilized to make a comprehensive evaluation. Since the random hybrid rule has integrated many rules for scheduling, the space of feasible solution was extended and the optimum capability of algorithms was improved greatly.


## 3.1. Deterministic Single Rules

The following kinds of deterministic single rules are considered in this research work. These deterministic single rules determine the task processing sequence according to the given attribute (such as, task priority, task duration, earliest start time and latest end time etc.) firstly and then arrange each task following the previous sequence. The realization process of deterministic single rules is simple, its idea is easy to understand, and the execution speed is relatively fast.(1)
Deterministic sequence based on the priority (DSP): it determines the task processing sequence according to the task priority (prior to sequencing the task with the large priority).(2)
Deterministic sequence based on the duration (DSD): it determines the task processing sequence according to the duration (prior to sequencing the task with the small duration).(3)
Deterministic sequence based on the start time (DSST): it determines the task processing sequence based on the start time (prior to sequencing the task with the small earliest start time).(4)
Deterministic sequence based on the end time (DSET): it determines the task processing sequence according to the end time (prior to sequencing the task with the small latest end time).


## 3.2. Random Single Rules

Four kinds of random single rules are considered in this work. These random single rules randomly determine the task processing sequence based on the certain attributes (for example, task priority, task duration, earliest start time, and latest end time etc.) firstly and then arrange each task following the previous sequence. The realization process of random single rules is simple and the obtained solution is fairly outstanding.(1)  Random Sequence Based on the Priority (RSP). It randomly determines the task processing sequence based on the task priority. For each task, it will be selected with the following probability:
(7)Pri=Pi∑i=1nPi.
Here, Pri denotes the selected probability of task i, Pi denotes the priority of task i, and n denotes the number of tasks.(2)  Random Sequence Based on the Duration (RSD). This random single rule randomly determines the task processing sequence according to the duration. For each task, it will be selected with the following probability:
(8)Pri=Di′∑i=1nDi′.
Here, Pri denotes the selected probability of task i, and
(9)Di′=2×max1≤i≤n{Di}-Di.Di denotes the duration of task i.(3)  Random Sequence Based on the Start Time (RSST). It randomly determines the task processing sequence based on the start time. For each task, it will be selected with the following probability:
(10)Pri=ESTi′∑i=1nESTi′.
Here, Pri denotes the selected probability of task i, and
(11)ESTi′=2×max1≤i≤n{ESTi}-ESTi.ESTi denotes the earliest start time of task i.(4)  Random Sequence Based on the End Time (RSET). It randomly determines the task processing sequence based on the end time. For each task, it will be selected with the following probability:
(12)Pri=LETi′∑i=1nLETi′.
Here, Pri denotes the selected probability of task i, and
(13)LETi′=2×max1≤i≤n{LETi}-LETi.LETi denotes the latest end time of task i.


## 3.3. Random Hybrid Rules

Based on the previous kinds of random single rules, the random hybrid rule (RHR) is proposed to the data transmission dynamic scheduling. the random hybrid rule randomly determines the task processing sequence based on the different random single rules firstly and then arranges each task following the previous sequence. The realization process of random hybrid rule is slightly complex and the obtained solution is fairly outstanding. The random hybrid rule is defined as follows:(14)RHR={RSP0≤r<p1RSDp1≤r<p2RSSTp2≤r<p3RSETp3≤r≤1.
Here, r is a random number and p1, p2, and p3 are three predefined thresholds. In the random hybrid rule, the RSP rule is selected with the probability p1, the RSD rule is selected with the probability p2-p1, the RSST rule is selected with the probability p3-p2, and the TSET is selected with the probability 1-p3. After repeatedly employing the random single rules, they will obtain multiple different solutions. In order to compare these solutions, the TOPSIS was utilized to make a comprehensive evaluation. Since the random hybrid rule has integrated many rules for scheduling, the space of feasible solution was extended and the optimum capability of algorithms was improved greatly.


## 4. Experimental Results

In this paper, the testing examples are produced based on the AFIT benchmark data which were generated by United States Air Force Academy. The AFIT benchmark data include seven contents. The task is distinguished by identification and the scheduling resources only have the ground station antenna. According to the actual demand, the task priority attribute is increased. Since the set-up time exists, the task execution time and the visible time window can be extended directly. The improved validation data are shown in Table1. The AFIT benchmark data provided 14 groups of scheduling task data by high-low earth orbit satellites. This paper selected medium-scale low earth orbit satellites and constructed four scheduling instances with different scales.Table 1
The Actual Validation Data Format.
Task identification
Task priority
Task execution time
Start time of visible window
End time of visible window
Ground station and antenna used for executing tasks
92
10
33
913
946
REEF-A
REEF-B
93
5
36
915
951
GUAM-A
GUAM-BThe four instances were used to verify the nine different heuristics; their comprehensive evaluation indexes were compared based on the simulation results, as shown in Figure2. The following conclusions can be made from experimental results. In the respect of comprehensive evaluation index, the random hybrid rule is better than the random single rule, and random simple rule is superior to the deterministic simple rule. It is known that since the random hybrid rule has introduced the thought of random selection and summarized multiple heuristic rules for scheduling, the space of feasible solutions was extended and the optimum capability of heuristic rules was greatly improved. Generally speaking, the proposed random hybrid rule can obviously enhance the validity of dynamic scheduling and ensure the high efficiency and stability, which has a higher comprehensive performance.Figure 2
The comparison of comprehensive evaluation indexes.


## 5. Conclusions

The data transmission dynamic scheduling problem is a complex scheduling problem. In this paper, the reasonable mathematical model was established, the rule-based heuristic algorithm was designed, and TOPSIS was applied into the comprehensive evaluation. Through verifying by several groups of instances, their results of comparison indicate that the proposed algorithm is able to enhance the validity of dynamic scheduling obviously. It can also ensure the high efficiency and stability.



---

*Source: 837659-2013-12-16.xml*