close

Вход

Забыли?

вход по аккаунту

?

j.ejor.2018.07.012

код для вставкиСкачать
ARTICLE IN PRESS
JID: EOR
[m5G;July 28, 2018;0:22]
European Journal of Operational Research 0 0 0 (2018) 1–11
Contents lists available at ScienceDirect
European Journal of Operational Research
journal homepage: www.elsevier.com/locate/ejor
Discrete Optimization
A hybrid adaptively genetic algorithm for task scheduling problem in
the phased array radar
Haowei Zhang a,∗, Junwei Xie a, Jiaang Ge a, Zhaojian Zhang b, Binfeng Zong c
a
Air and Missile Defense College, Air Force Engineering University, Shaanxi Xi’an 710051, PR China
Air Force Early Warning Academy of PLA, 410039, PR China
c
Unit 94710, Jiangsu Wuxi, 214000, PR China
b
a r t i c l e
i n f o
Article history:
Received 20 June 2017
Accepted 4 July 2018
Available online xxx
Keywords:
Combinatorial optimization
Phased array radar
Task scheduling
Genetic algorithm
Chaos theory
a b s t r a c t
A phased array radar (PAR) is used to detect new targets and update the information of those detected
targets. Generally, a large number of tasks need to be performed by a single PAR in a finite time horizon.
In order to utilize the limited time and the energy resources, it is necessary to provide an efficient task
scheduling algorithm. However, the existing radar task scheduling algorithms can’t be utilized to release
the full potential of the PAR, because of those disadvantages such as full PAR task structure ignored,
only good performance in one aspect considered and just heuristic or the meta-heuristic method utilized. Aiming at above issues, an optimization model for the PAR task scheduling and a hybrid adaptively
genetic (HAGA) algorithm are proposed. The model considers the full PAR task structure and integrates
multiple principles of task scheduling, so that multi-aspect performance can be guaranteed. The HAGA
incorporates the improved GA to explore better solutions while using the heuristic task interleaving algorithm to utilize wait intervals to interleave subtasks and calculate fitness values of individuals in efficient
manners. Furthermore, the efficiency and the effectiveness of the HAGA are both improved by adopting
chaotic sequences for the population initialization, the elite reservation and the mixed ranking selection,
as well as designing the adaptive crossover and the adaptive mutation operators. The simulation results
demonstrate that the HAGA possesses merits of global exploration, faster convergence, and robustness
compared with three state-of-art algorithms—adaptive GA, hybrid GA and highest priority and earliest
deadline first heuristic (HPEDF) algorithm.
© 2018 Elsevier B.V. All rights reserved.
1. Introduction
A radar sensor utilizes reflections of transmitted electromagnetic waves to detect the incoming targets and update the information of previously detected targets. The cycle over which the
radar transmits energy, waits and receives the reflected energy, is
defined as a task. It is often the case that, especially in the modern
battlefield, various tasks need to be performed by radar sensors
in a finite time horizon, such as communications, tracking targets
and searching horizons. Such various tasks should be performed by
multiple traditional mechanically rotating radars, each of which is
responsible for a single and dedicated function/task. By contrast,
owing to its agile beam pointing directions, a single phased array radar (PAR) is capable of handling the different tasks above.
However, such remarkable advantages depend on the efficient time
management.
∗
Corresponding author.
E-mail addresses: zhw_xhzf@163.com (H. Zhang), 752858328@qq.com (J. Ge).
The research on how to chronologically order and perform multiple tasks leads to the task scheduling problem, and it has been
investigated in various studies. Herr and Goel, (2016) and Oron,
Shabtay, and Steiner (2016) address the single machine scheduling problem with family setups or two competing agents. Sioud
and Gagné (2018) presents an enhanced migrating bird optimization (MBO) algorithm and a new heuristic for solving a permutation flow shop scheduling problem with sequence dependent setup times. Pessoa and Andrade (2018) addresses the flow
shop scheduling problem with delivery dates and cumulative payoffs and suggests the biased random-key genetic algorithm starting with a solution from FF heuristic after comparison. Moukrim,
Quilliot, and Toussaint (2015) proposes an effective branch-andprice algorithm for solving preemptive resource constrained project
scheduling problem based upon minimal interval order enumeration involving column generation as well as constraint propagation. Shioura, Shakhlevich, and Strusevich (2018) provides a review
of recent results on preemptive scheduling with controllable processing times. Just similar with the scheduling problems above, the
PAR task scheduling is able to be regarded as a preemptive flow
https://doi.org/10.1016/j.ejor.2018.07.012
0377-2217/© 2018 Elsevier B.V. All rights reserved.
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
JID: EOR
2
ARTICLE IN PRESS
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
shop scheduling problem in single machine subject to the time and
the energy constraints. A radar task consists of three subtasks: the
transmit interval, the wait interval and the receive interval, and the
execution of each task needs a certain duration and power consumption. Obviously, the PAR task scheduling problem is N-P hard.
Within the context of radar sensors, the solutions to the problem
can be divided into two parts: the heuristic algorithms and the
meta-heuristic algorithms. In the heuristic algorithms, each task is
assigned for a priority and the request tasks are orderly scheduled
from the highest priority. However, such algorithms only explore
the solution region by one path while ignoring other paths. Therefore, they can’t provide consistent results for wide ranges of problems. By contrast, the meta-heuristic algorithms exploit the swarm
cooperation and continuous evolution to explore solutions in the
whole solution region, and thus are able to obtain near-optimal results. The typical heuristic algorithms are the earliest deadline first
(EDF) algorithm (Butler, 1998; Reinosorondinel, Yu, & Torres, 2010)
and the highest value first algorithm (Deb, Bhattacharjee, & Vengadarajan, 2015; Orman, Potts, Shahani, & Moore, 1996; Sgambato,
Celentano, Dio, & Petrillo, 2016). However, these algorithms only
prioritize the request tasks by a single parameter, and such prioritization may be one-sided. Huizing and Bloemen (1996), Jiménez,
Izquierdo, Villacorta, and Val (2009), Jimenez, Val, Villacorta, and
Izquierdo (2012) divide the tasks into several queues by ordinations and task parameters, and the EDF algorithm or the first in
first out (FIFO) algorithm is used in each queue. Cheng, He, and Li
(2009), Cheng, He, and Tang (2009), Lu, Xiao, Xi, and Zhang (2011),
Lu, Xiao, Xi, and Zhang (2013) map the task mode and the deadline to the same layer to calculate the task synthetic priority and
prior schedule the task with the highest synthetic priority. On the
basis of the two elements in Chen, Tian, Wang, Zhang, and Cao
(2011), Cheng et al. (2009), Cheng, He, & Tang (2009), Lu et al.
(2011), Lu et al. (2013), and Cheng, He, and Tang (2008) further
take the timeliness principle of task scheduling into consideration
and propose the gain-based scheduling algorithm. Zhang, Xie, and
Sheng (2016a); Zhang, Xie, Zong, Lu, and Sheng (2017) exploit the
threat of the target to represent the task importance and offer the
dynamic-priority-based scheduling algorithm. These algorithms all
prioritize tasks by multiple task parameters, and such a prioritization is more reasonable. In addition, Mir and Abdelaziz (2012) and
Mir and Guitouni (2014) put forward the notion of the variable
dwell time, which brings more flexibility for the task scheduling.
In meta-heuristic algorithms, Pan (2014), Wang, He, Wang, and
Ji (2014), Zhang, Xie, and Sheng (2016b), Zheng, Tian, and Xing
(2016), Zhou, Wang, and Wang (2005), Zhou, Wang, and Wang
(2006) apply the improved genetic algorithms (GAs) to the radar
task scheduling problem, which renders the improvement of the
steadiness and the robustness.
While the existing work has made many seminal contributions
to the radar task scheduling, there are still some issues to be addressed. Firstly, some algorithms (Butler, 1998; Deb et al., 2015;
Huizing, & Bloemen, 1996; Jimenez et al., 2012; Jiménez et al.,
2009; Lu et al., 2011; Lu et al., 2013; Mir, & Abdelaziz, 2012; Pan,
2014; Reinosorondinel et al., 2010; Sgambato et al., 2016; Wang
et al., 2014; Zhang et al., 2016a; Zhang et al., 2017; Zheng et al.,
2016) just model the task structure as the non-preemptive. The
full radar task structure, which includes the transmit, wait and
receive subtask is not considered. This precludes exploiting the
wait subtask to interleave other subtasks and making a more efficient utilization of the radar timeline. Secondly, though some algorithms (Chen et al., 2011; Cheng et al., 2009; Cheng et al., 2008;
Cheng et al., 2009; Mir, & Guitouni, 2014; Orman et al., 1996; Zhou
et al., 2005; Zhou et al., 2006) model a full radar task structure
and utilize the wait interval to interleave subtasks, the optimization model of task scheduling is not posed or the algorithms only
try to achieve a simple goal such as maximizing the number of
scheduled tasks or the time utilization. Due to the inherent characteristics of radar task scheduling, such a simple objective function is not able to guarantee the performance in multiple aspects.
For example, tasks with higher priority may be simultaneously
with longer dwell time and thus, the sum priority of successfully
scheduled tasks and the number of successfully scheduled tasks
in a finite time horizon are conflicting. Thirdly, most of the works
(Butler, 1998; Chen et al., 2011; Cheng et al., 2009; Cheng et al.,
2008; Cheng et al., 2009; Deb et al., 2015; Huizing, & Bloemen,
1996; Jimenez et al., 2012; Jiménez et al., 2009; Lu et al., 2011;
Lu et al., 2013; Mir, & Abdelaziz, 2012; Mir, & Guitouni, 2014; Orman et al., 1996; Pan, 2014; Reinosorondinel et al., 2010; Sgambato
et al., 2016; Wang et al., 2014; Zhang et al., 2016a; Zhang et al.,
2017; Zheng et al., 2016; Zhou et al., 2005) just adopt one kind of
algorithm (heuristic or meta-heuristic) to solve the problem. The
superiorities of the two kinds of algorithms are not well balanced.
An exact optimization model of PAR task scheduling and a hybrid chaotic adaptively genetic algorithm are put forward aiming at
these issues. The main contributions of this paper are summarized
as follows:
(1) The full PAR task structure, which consists of the transmit interval, the wait interval and the receive interval, is
explicitly modeled, and the task scheduling optimization
model for the PAR, whose objective function integrated the
scheduling principles of the importance, the urgency and the
timeliness, is established. As such, the performance of the
algorithm in multiple aspects are compromised and guaranteed.
(2) An improved scheduling method over chaotic adaptively GA
is proposed to solve the problem. On the basis of the GA,
chaotic sequences are introduced to initialize the population. Chaos system is essentially a nonlinear system full of
bounded unstable dynamic behavior and infinite unstable
periodic motions (Singh, & Mahapatra, 2016; Yao, Liu, & Lin,
2002). As such, chaotic sequences, carrying with the properties of the randomness and the ergodicity of the chaos system, are able to diversify the initialized population. The elite
reservation and the mixed ranking selection operation are
adopted to prevent the premature convergence of the algorithm. In addition, the adaptive crossover operator and the
adaptive mutation operator are both designed to improve
the global exploration ability and the efficiency of the algorithm.
(3) A task interleaving scheduling heuristic is presented in the
chaotic adaptively GA framework. The task scheduling is
considered in a way that the wait interval can be utilized
to transmit or receive subtasks as well as the collision between the transmit interval and the receive interval is prevented while satisfying the energy constraint. The heuristic
exploits the time constraint feasibility check and the energy
feasibility check to analyze the task schedulability, and adaptively interleaves tasks as many as possible. Thereby the fitness value of individual can be quickly calculated and the
efficiency of the whole algorithm can be further improved.
(4) Through experimental results over randomly generated tasks
as well as closely real-world situations with various task
scales, the effectiveness and the efficiency of the proposed
algorithm are both verified.
The reminder of this paper is organized as follows. The optimization model of PAR task scheduling is established in Section 2.
A hybrid chaotic adaptively genetic algorithm is presented in
Section 3. Section 4 gives the simulation results and analysis.
Section 5 concludes the paper.
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
ARTICLE IN PRESS
JID: EOR
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
3
Each task should be executed before its deadline, or it will be
useless because of the target maneuver. ti satisfies:
tai = te(i−1) + ti
(4)
where te( i -1) denotes the execution time of the former task.
2.2. Resource constraint model
Similar with many scheduling problems, the PAR task scheduling is subject to multiple restrictions, where the time resource constraint and the energy constraint are two main elements.
2.2.1. Time resource constraint
The scheduling interval (SI) is the basic time unit of radar task
scheduling, when the PAR processes the returning signals in the
former SI and determine the tasks to be executed in the next SI
(Cheng et al., 2009; Zhang et al., 2017). The N1 tasks to be executed
in an SI must satisfy the following time constraints:
Fig. 1. The overall PAR scheduling structure.
N1
(txi + tri ) ≤ tSI
(5)
i=1
max(tai − wi , tstart ) ≤ tei < min(tdi , tend − tdwi )
(6)
where tSI is the SI time, tstart is the start time of the SI, and tend
is the end time of the SI, which satisfies tend = tstart + tSI . In addition, the transmit interval and the receive interval in PAR tasks are
non-preemptive. The N1 tasks as such should satisfy the following
constraint:
N1 Fig. 2. The PAR task model.
(tei , tei + txi )
(tei + txi + twi , tei + txi + twi + tri ) = ∅
(7)
i=1
2. Modeling
2.1. PAR task model
The overall PAR task scheduling structure is shown in Fig. 1.
It can be seen that a series of request tasks will generate when
a target is captured by the PAR. Then, the scheduling algorithm
will analyze all the request tasks and divide the tasks into three
parts: execution (scheduled) tasks, delayed tasks and deleted tasks
(Baugh, 1973 Butler, 1998; Huizing, & Bloemen, 1996; Orman et al.,
1996). The delayed tasks will request time to be executed later, and
the deleted tasks will be abandoned. The PAR task model is shown
in Fig. 2. It can be seen that a PAR task is composed of three parts:
the transmit interval, the wait interval and the receive interval. As
such, ith PAR task is described as:
Ti = {Pi , tai , txi , twi , tri , Pti , tdwi , wi , tdi , ti}
(1)
where Pi is for the task priority, ta i for the task request time, tx i for
the transmit interval, tw i for the wait interval, which depends on
the target distance. tr i is the receive interval, Pt i is the task power
consumption, which means the execution of a radar task requires
not only a certain duration but also a certain power consumption.
In reality, the transmit interval consumes the majority power of
the whole task, as such; Pt i can be regarded as the power consumption after the execution of tx i . tdw i is the task dwell time, wi
is the time window, td i is the deadline. ti is the sample interval
between two adjacent tasks in the same type. tdw i satisfies:
tdwi = txi + twi + tri
(2)
td i satisfies:
tdi = tai + w i
(3)
Eq. (7) shows that the tx and tr are non-preemptive in a task,
but the tw can be utilized to interleave subtasks. However, the task
interleaving scheduling prolongs the PAR transmitting duration, the
energy constraint as such must be taken into consideration.
2.2.2. Energy resource constraint
In order to protect the radar transmitter to be safe, the transient power constraint must be satisfied all the time (Ghosh,
Hansen, Rajkumar, & Lehoczky, 2004): Pτ (t)≤P̅τ max . P̅τ max is the
power threshold of the PAR and Pτ (t) is the power consumed by
the PAR in time t . Pτ (t) is defined in terms of an exponential sliding window (Baugh, 1973):
Pτ (t ) =
1
τ
0
t
p( x ) e
(x−t )/τ
dx
(8)
where p(x) is the instantaneous power dissipation in the PAR. τ
is the look-back period, which characterizes the heat dissipation
performance of the PAR.
Fig. 3 shows an example for the calculation of the system power
consumption, where a set of tasks are executed with the exponential sliding window at time t0 . The shadow box is the transmit
interval with a certain transmitted power consumption. The solid
line is the curve of system power consumption, and the dotted line
is the sliding window at time t0 . It can be seen that the tasks executed more recently have larger impact on the power consumption than the less executed tasks. Additionally, the cooling rate of
power consumption after executing a radar task is steady. The energy constraint is considered to be satisfied if Eq. (8) never exceeds the power threshold P̅τ max . However, a cool duration must
be waited to protect the PAR transmitter if the power threshold is
exceeded.
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
ARTICLE IN PRESS
JID: EOR
4
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
Fig. 3. Calculation of power consumption.
2.3. Formulation of the optimization model
Many existing work just structures a simple objective function
such as maximizing the number of scheduled tasks or minimizing the radar idle time. However, due to the radar task characteristics, many objectives are conflicting with each other. For example,
the radar task with higher priority may need longer duration, leading to the sum of priority of successfully scheduled tasks and the
number of successfully scheduled tasks can’t be achieved simultaneously under the condition of a finite time horizon. As such,
the performance of the scheduling algorithm in multiple aspects
is considered comprehensively and a versatile objective function is
proposed in this section by integrating the three principles of radar
task scheduling.
During the PAR scheduling tasks, these principles should be followed: (1) the importance principle, which means that the most
important task should be prior scheduled. (2) The urgency principle, which means that the most urgent task should be prior
scheduled. (3) The timeliness principle. It means that the execution time of the task should be as close to its request time as
possible. The importance principle corresponds to the priority relationships between radar tasks (Deb et al., 2015; Orman et al.,
1996; Sgambato et al., 2016), where the division usually depends
on the practicality and experience. For instance, the tracking tasks
on more threatening targets are with higher priority and more
important than the tracking task on less threatening targets. Additionally, tracking tasks are often more important than search
tasks. The urgency principle is originally from the real situations
in single-machine task scheduling, where each task is just valid in
a certain time window and various request tasks are with different deadlines. In order to ensure request tasks can be successfully
scheduled as many as possible, their deadlines must be taken into
consideration and urgent tasks should be prior scheduled (Butler,
1998; Reinosorondinel et al., 2010). The timeliness principle (Chen
et al., 2011; Cheng et al., 2008) reflects the characteristic of the
PAR beam and the dynamic change of environment where the PAR
works. Due to the stick-shape beam in the PAR and the target maneuver, the strongest reflect signal will be obtained and the most
target information can be extracted only if the task execution time
is equal to its request time. However, such situations are usually
inaccessible due to the large number of request tasks. Thus, a little
time shift from its request time is allowable and leads to the task
also being valid in a time window, though the reflected signal will
be a little weaker and also can be utilized to extract the less target
information. Therefore, the above three principles are integrated to
establish the scheduling objective function as:
o(P, ta , w, tstart , te ) = [o1 (P ) + o2 (ta , w, tstart )]o3 (te , ta , w )
(9)
In Eq. (9), o1 (P) is the function of the task priority, and it describes the task importance. Higher P means more important task.
o2 (ta ,w,tstart ) is the function of the relative deadline of the task in
an SI, and it describes the urgency of the task. As each task just
being valid in its time window, the urgency of each task in an SI
is relative. Here, the relative deadline in the SI (ta + w-tstart )/tSI is
used to indicate the relative urgency of each task. In addition, the
negative exponent form is adopt to ensure the increasing property of the objective function, which is accordant with o1 (P). Thus,
o2 (ta , w, tstart ) is adopted as exp[−2(ta + w-tstart )/tSI ]. o3 (te , ta , w)
is the function of the distance between the task request time and
the task execution time, and it describes the timeliness of scheduling the task. Similar with the relative deadline, the timeliness of
each request task is relative in its time window. Thus, |(te -ta )/w|
is adopted to indicate the timeliness. In order to ensure the increasing property of the function, o3 (te , ta , w) is chosen as [1-|(te ta )/w|]. Thereby, several goals are integrated in the objective function, ensuring the simultaneous good performance of the algorithm
in multiple aspects.
Assume that there are N request tasks in an SI, and the number of executed, delayed, and deleted tasks are N1 , N2 , and N3 respectively, which satisfies N = N1 + N2 + N3 . As such, the PAR task
scheduling optimization model is described as follows:
max
N1
o(Pi1 , ta i1 , wi1 , tstart , tei1 )
i1
s.t.max(tai1 − wi1 , tstart ) ≤ tei1 < min(tdi1 , tend − tdwi1 )
N1
[(tei1 , tei1 + txi1 ) (tei1 + txi1 + twi1 , tei1 + txi1 + twi1 + tri1 )] = ∅
i1=1
N1
i1=1
(txi1 + tri1 ) ≤ tSI , Pτ (t ) ≤ Pτ max , i1 = 1, 2...N1
tai2 + wi2 ≥ tend , i2 = 1, 2...N2
tai2 + wi2 < tend , i3 = 1, 2...N3
(10)
where the first four constraints are for the tasks to be executed,
and the other two constraints are for the tasks to be delayed and
to be deleted respectively.
Eq. (10) reflects the fact that the PAR task scheduling problem is
N-P hard, and its optimal solution is computationally demanding.
Therefore, an efficient algorithm that is based on the improved GA
is developed in the next section to solve the problem.
3. Hybrid chaotic adaptively genetic algorithm
The GA simulates the biological evolution procedure in nature,
and it explores the optimal solutions by the successive selection,
the crossover and the mutation operations. Compared with the
other meta-heuristic algorithms such as the particle swarm optimization and the fish swarm algorithm (Damm, Resende, & Ronconi, 2016; Fang, Zhou, & Zhang, 2014; Mehrdad, & Reza, 2015),
which are easily suffer from premature convergence, the GA has
advantages in less need of assistant information of the solution region and more powerful capability of finding out the global op-
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
JID: EOR
ARTICLE IN PRESS
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
timum, and thus is applied in the non-linear constraint problems
extensively (Zhang, & Wong, 2015; Zhang, Ong, & Nee, 2015). However, due to the real-time demand of the radar system, the traditional GA may be inefficient for the radar task scheduling. As such,
a hybrid chaotic adaptively genetic algorithm is proposed to solve
the task scheduling problem in the PAR.
3.1. Initialize the population by chaotic sequences
Before the GA exploring solutions, the population should be
firstly initialized. The population usually initialized randomly in
some GAs, leading to the algorithms started with low-quality solutions and easily sticking to a solution (Caponetto, Fortuna, Fazzino,
& Xibilia, 2003). However, high-quality initialized solutions promote the GA to find better solutions more quickly than it can
from a random start (Xu, Li, Hu, & Li, 2014). Here, the chaotic
sequence, which is characterized with the ergodicity and the intrinsic stochastic properties of the chaotic motion (Yao et al.,
2002)0, is introduced to diversify and improve the quality of the
initialized population. Various methods are available to obtain
chaotic sequences such as logistic map, tent map, Henon map, and
Ikeda map (Kantz, & Schreiber, 2004; Peitgen, Jurgens, & Saupe,
2004), among which the logistic map has been applied in numerous meta-heuristic algorithms (Coelho, 2008; Singh, & Mahapatra,
2016). As such, the Logistic equation is adopted to initialize the
chaotic population:
λk+1 = μλk (1 − λk )
(11)
where λk is obtained after the chaos variable λ iterating k times,
and λ∈[0,1]. μ controls the chaos situation, and μ∈[0,4]. When
μ = 4 and λ∈{0.25,0.5,0.75}, the initial population will own fully
chaotic property. The population initialization procedure is as follows.
Assume that there are N request task in an SI, the number of
genes in an individual is also N. Each gene represents the candidate execution time of the request task. The upper bound and the
lower bound of ith gene are tmax i and tmin i respectively (they can
be obtained by Eq. (6)). Firstly, each gene is mapped into [0,1] by:
te i = (tei − tm ini )/(tmax i − tmin i )
(12)
where te i represents the candidate execution time of ith gene (ith
request task). Then, t’e i will be mapped into the original region and
be truncated after iterating k times by Eq. (11). It is noticeable that
the each gene must be tethered in [tmin i , tmax i ] when the GA exploring the global optimum in order to ensure the feasibility of the
solution.
3.2. Mixed selection operation
The selection, the crossover operation and the mutation operation are the three main steps in the GA. By the three steps, the GA
removes the poor individuals and replaces them with better ones.
Thereby, the algorithm will be driven to find out the global optimum. In the three operations, the selected individuals are called
the parents, and the offspring are called the children. In the traditional GA, individuals are selected by their fitness values, where
the individual with higher fitness value will obtain higher selection chance. However, such a selection easily leads to the GA just
exploring solutions in a relative small solution region and reaching
to the local optimum. The elite reservation, a number of best solutions will be directly chosen as the offspring, can increase the quality of solutions and reduce the computational cost (Damm et al.,
2016; Zhao, Zhao, & Zhao, 2014), and ensures the best fitness value
being at least as good as the last generation and the convergence
of the algorithm. Additionally, in order to drive the GA to jump
5
out the small solution region, the mixed ranking selection is also
adopted, which reserves some poor individuals and ensures the diversity of the population. As such, the GA will explore solutions in
regions around poor individuals with the same probability as the
good ones to ensure the global optimization. The selection procedure is described as follows.
Assume that the cardinality of population is M. At first, the population will be ranked by their fitness values (in this paper, it is
Eq. (9)) in the descending order and the first m individuals will
be directly selected as the offspring. As to the remaining M-m individuals, the pseudo fitness value of ith individual is calculated
according to Eq. (13):
pi = ( 2 −
2i − 2
)/ ( M − m )
M−m−1
(13)
After that, the selection probabilities of the remaining M-m individuals are calculated through the roulette method:
pc = pi /
M−m
pi
(14)
i=1
where pc is the selection probability of ith individual.
3.3. Adaptive crossover operator and adaptive mutation operator
The crossover operation generates two new individuals from
the two selected parents and the mutation operation generates one
new individual from a selected offspring. Both of the operations
guarantee the reservation of good individuals and the variety of
the population.
The crossover and the mutation probabilities play important
roles in the two operations. The higher crossover probability enhances the GA exploration efficiency, but it also increases the probability of the premature convergence. The lower crossover probability drives the GA to traverse the most solution regions and find
out better results, but it also easily sinks the algorithm into a torpid state. Similar with the crossover probability, a higher mutation
probability drives the GA roughly explore the whole solution region in faster manner but leave out the local solution, and a lower
mutation probability ensures the find out of the optimum but retard the exploration efficiency. As such, an adaptive crossover operator and an adaptive mutation operator are proposed in order to
endow the algorithm both of the great exploration ability and the
high efficiency:
Pc =
Pc0 +
Pc1 −
Pm =
f − fmin
favg − fmin
f − favg
fmax − favg
Pm0 +
Pm1 −
f ≤ favg
f > favg
f − f min
f avg − f min
f − f avg
f max − f avg
f ≤ f avg
f > f avg
(15)
(16)
In Eq. (15), Pc is the crossover probability. Pc0 and Pc1 are the
initialized parameters for Pc adjustment. They determine the lower
boundary and the upper boundary of Pc respectively and can be
selected through a lot of simulations. f is the fitness value of the
individual. fmax , fmin and favg are the best fitness value, the worst
fitness value and the average fitness value of the population in
each generation respectively. In Eq. (16), Pm is the mutation probability, and the other parameters are similar to those in Eq. (15).
It can be seen from Eq. (15) and Eq. (16) that if the fitness value
of an individual is lower than the average level of the population,
the individual will be changed in higher probability. Conversely, if
the fitness value of an individual is higher than the average level,
the individual will be reserved in higher probability. As such, Pc
and Pm is able to be adaptively adjusted, and the efficiency of the
algorithm is able to be improved.
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
JID: EOR
6
ARTICLE IN PRESS
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
Fig. 4. Task scheduling ways in the PAR.
3.4. Heuristic task interleaving algorithm
Many scheduling algorithms regard the PAR task as the nonpreemptive (Butler, 1998; Deb et al., 2015; Huizing, & Bloemen,
1996; Jimenez et al., 2012; Jiménez et al., 2009; Lu et al., 2011;
Lu et al., 2013; Mir, & Abdelaziz, 2012; Pan, 2014; Reinosorondinel
et al., 2010; Sgambato et al., 2016; Wang et al., 2014; Zhang et al.,
2016a; Zhang et al., 2017; Zheng et al., 2016), leading to the preclusion of utilizing the wait interval to interleave transmit intervals
and receive intervals and make a more efficient use of the radar
timeline. When the task interleaving technique is introduced, the
time utility can be further improved. The task scheduling ways in
the PAR are shown in Fig. 4, where the shadow box is the task 1
and the blank box is task 2. Fig. 4(a) and (c) is two ways of noninterleaving scheduling. Fig. 4(b) and (d) is the two corresponding
ways of interleaving scheduling. Obviously, the radar timeline can
be utilized more efficiently to accommodate more request tasks in
the task interleaving ways. However, the task interleaving scheduling is more complicated. Fig. 4(b) and 4(d) shows that the two
interleaved tasks should satisfy the following time constraint, respectively:
tw1 ≥ tx2
(b) tr1 ≤ tw2
tx2 + tw2 ≥ tw1 + tr1
(d )tw1 ≥ tx2 + tw2 + tr2
(17)
Additionally, the two interleaved tasks also should satisfy the
constraints shown from Eqs. (5)–(8). As such, a heuristic task interleaving algorithm is put forward in order to reduce the complexity
of task interleaving analysis. The heuristic algorithm is summarized
as: apply the time test to the transmit interval and the receive interval of a task by the left and the right boundary of the remaining
timeline, and apply the energy test to the task, then, update the
power pointer and the remaining timeline.
Assume that the remaining timeline is initialized as [tstart , tend ]
in an SI, the power pointer is Pt0 , the number of request tasks is
N, and the number of genes in the individual is N. The gene represents the candidate execution time of each request task, and they
have been sorted by FIFO algorithm and signed as task 1, 2, 3, … N
separately. Firstly, the time constraint test is applied to the transmit interval of task 1:
te1 ≥ tstart
te1 + tx1 ≤ tend
(18)
If the transmit interval doesn’t meet the time constraint, the
task will be send to the delayed queue or the deleted queue according to Eq. (10). If the transmit interval satisfies the time constraint, update the remaining time line as: [tstart , te1 ], [te1 + tx1 ,
tend ]. Then, the time constraint analysis is applied to the receive
interval of task 1:
te1 + tx1 + tw1 ≥ te1 + tx1
.
te1 + tx1 + tw1 + tr1 ≤ tend
(19)
If the receive interval doesn’t meet the time constraint, set
the task to the delayed queue or the deleted queue according to
Eq. (10), and reset the remaining time line as: [tstart , tend ]. If the
receive interval satisfies the time constraint, continue to apply the
energy constraint test to task 1:
Pt0 e−tx1 /τ + Pt1 (1 − e−tx1 /τ ) ≤ P τ max .
(20)
If task 1 doesn’t meet the energy constraint, send the task to
the delayed queue or the deleted queue according to Eq. (10), and
reset the remaining timeline as: [tstart , tend ]. If task 1 also satisfies the energy constraint, update the remaining time line as: [tstart ,
te1 ], [te1 + tx1 , te1 + tx1 + tw1 ], [te1 + tx1 + tw1 , tend ], and update the
power pointer Pt0 as:
Pt0 = Pt0 e−tx1 /τ + Pt1 (1 − e−tx1 /τ ).
(21)
After that, the time constraint test and the energy constraint
test will be applied to the remaining tasks sequentially as task 1.
In this way, where the continuous update of Pt0 and the remaining
timeline, the task interleaving analysis is simplified and the fitness
value of the individual is able to be quickly calculated.
By the way, the remaining timeline will be divided into many
pieces along with the scheduling analysis. All the remaining timeline pieces should be tested when apply the time constraint test to
a subtask. When testing the following tasks by the time constraint,
the start time of a subtask may be less than the left boundary
of one remaining timeline piece. Therefore, the first constraint in
Eq. (19) is necessary as it reflects the procedure of the task interleaving algorithm.
3.5. Procedure of the hybrid chaotic adaptively genetic algorithm
On the basis of the proposed optimization methods, the procedure of the hybrid chaotic adaptively genetic algorithm is described
as follows:
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
JID: EOR
ARTICLE IN PRESS
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
7
4. Simulations and results
In this section, the four metric indexes are firstly introduced
in order to comprehensively evaluate the performance of the proposed algorithm. Then, the effectiveness of the proposed method
is verified by a small example, where a small number of request
tasks are randomly generated. Finally, the proposed method is
compared with other three baseline algorithms in the near-reality
simulations and the analysis shows its superiorities.
Fig. 5. Flow chart of the hybrid chaotic adaptively genetic algorithm.
4.1. Performance metric indexes
Step 1 Parameters initialization. Set the population scale as M,
the terminal generation number/criterion as Gmax , the chaos parameter as μ, the number of elite reservation as m, the bounds of
the adaptive crossover operator and the adaptive mutation operator as Pc0 , Pc1 , Pm0 and Pm1 , respectively.
Step 2 Population initialization. Code the genes in individuals by the real number. The number of the genes N is equal to
the number of the request tasks in the SI, and each gene represents the candidate execution time of the request task. The generated genes in the individual all satisfy the first constraint in
Eq. (10). As such, each individual stands for a candidate execution task sequence. The initial population is able to be obtained by
Section 3.1.
Step 3 Fitness values calculation and scheduling sequences acquisition. At first, analyze the task interleaving ways of the candidate scheduling sequences (individuals) by Eqs. (17)–(21). Then,
obtain the execution/scheduled tasks, delayed tasks and deleted
tasks in each individual. After that, calculate the fitness values of
the individuals according to Eq. (9).
Step 4 Selection operation. Apply the elite reservation and
the mixed ranking selection to the population according to Eqs.
(13) and (14). Then, obtain the selected generation.
Step 5 Adaptive crossover operation. Generate a random number belonging to (0,1) for each individual, and calculate the
crossover probability of each individual by Eq. (15). Then, find
out the individuals whose random numbers are smaller than Pc .
Next, divide those individuals into two parts, and each part is for
choosing one of the parents. Note that the total number of parents should be an integral multiple of two, or the number will be
rounded. For individual i in one part, choose another individual j in
another part and generate another random number r (r = 1,2,…N)
as the crossover point for them. Then, exchange the genes that
are located behind rth gene in the two individuals and obtain two
offspring. It should be noted that the offspring generated by the
crossover operation must be different from the two parents; meanwhile, the fitness value of the offspring must be not poor than the
parents or it will be deleted and replaced by the one of the parents
that has a better fitness value.
Step 6 Adaptive mutation operation. After the crossover operation, generate a random number belonging to (0,1) for each gene
in the individual, and calculate the mutation probability of the individual by Eq. (16). If the random number is smaller than the Pm ,
change the gene with a feasible one according to the first constraint in Eq. (10). Then, obtain the offspring after all genes in the
individual having been tested. Note that the offspring generated by
the mutation operation must be different from the parent and the
fitness value of the offspring must be better than the parent. If the
fitness value of the offspring is poor than the parent, it will be
deleted and replaced by the parent.
Step 7 If the generation comes to the terminal criterion Gmax ,
the algorithm ends and output the best scheduling sequence. Otherwise, go to the Step 3.
The flow chart of the algorithm is shown in Fig. 5.
Many radar task scheduling algorithms are only estimated by
one criterion. However, such evaluation may be partial because
the characteristics of radar tasks always lead to many evaluation
indexes being conflicting. As such, in order to comprehensively
evaluate the performance of the proposed algorithm in multiple
aspects, the following indexes are chosen according to the three
principles of PAR task scheduling.
(1) The high value ratio (HVR) (Cheng et al., 2009; Cheng et al.,
20 08; Cheng et al., 20 09; Lu et al., 2011; Lu et al., 2013). It
reflects whether the algorithm has prior scheduled the most
important task and is expressed as:
Nsuc
HVR =
Ntotal
Pi /
i=1
Pi
(22)
i=1
where Pi is the task priority, and it denotes the task importance. Nsuc and Ntotal are the number of successfully scheduled tasks and the number of request tasks respectively. It
can be seen from Eq. (22) that the higher HVR means the
better performance.
(2) The successful scheduling ratio (SSR) (Cheng et al., 2009;
Cheng et al., 2008; Cheng et al., 2009; Lu et al., 2011; Lu
et al., 2013). It is defined as the ratio between the number
of successfully scheduled tasks and the number of request
tasks. It reflects whether the algorithm has prior scheduled
the most urgent tasks. The SSR can be expressed as:
SSR = Nsuc /Ntotal
(23)
Obviously, the higher SSR means the better performance.
(3) The time utilization ratio (TUR) (Cheng et al., 2009; Cheng
et al., 2008; Cheng et al., 2009; Lu et al., 2011; Lu et al.,
2013). It reflects whether the scheduling algorithm has utilized all time resource efficiently and is defined as:
TUR =
Nsuc
txi + tri
i=1
Ttotal
(24)
where is Ttotal the total time resource. The time resource
constraint is the most important one that restricts the releasing of the PAR multifunctional potential. Hence, the
higher TUR means the better performance.
(4) The average time shift ratio (ATSR) (Chen et al., 2011; Lu
et al., 2013). It is expressed as:
ATSR =
Nsuc
1 |tai − tei |
Nsuc
wi
(25)
i=1
Eq. (25) reflects that whether the scheduling algorithm satisfies the timeliness principle. If the task execution time is
nearby its request time, the radar will obtain better search
and tracking performance. As such, the lower ATSR means
the better performance of the algorithm.
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
ARTICLE IN PRESS
JID: EOR
8
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
Table 1
Parameters of radar tasks.
Tasks
P
tx , tw , tr (ms)
Pt (kW)
w (ms)
t (ms)
Confirmation
High precision tracking
Tracking loss
Precision tracking
Normal tracking
search
6
5
4
3
2
1
1,
1,
1,
1,
1,
1,
5
4
5
3
3
5
30
30
50
100
200
–
150
10 0–20 0
–
250–500
10 0 0
10
–,
–,
–,
–,
–,
–,
1
1
1
1
1
1
Table 2
Comparison of the performance.
Algorithms
SSR
HVR
TUR
ATSR
HPEDF heuristic
AGA
HGA
proposed algorithm
0.50 0 0
0.50 0 0
0.9444
1.0 0 0 0
0.6721
0.7213
0.9836
1.0 0 0 0
0.3600
0.3600
0.6800
0.7200
0.5614
0.1540
0.1025
0.0601
4.2. Parameters designation
The time constraints are tSI = 50 ms and Ttotal = 50 s. The energy constraints are P̄τ max = 1.25 kW, τ = 200 ms. The radar task parameters are shown in Table 1. The scheduling algorithm based
on the heuristic rule: highest priority and earliest deadline first,
(HPEDF heuristic) (Cheng et al., 2009), the scheduling algorithm
based on the hybrid genetic algorithm (HGA) (Wang et al., 2014)
as well as the scheduling algorithm based on the adaptive genetic algorithm (AGA) (Pan, 2014;) are used as the baseline to
compare against the performance of the proposed scheduling algorithm. In the proposed algorithm, M = 100, Gmax = 200, μ = 4,
m = 1, Pc0 = 0.5, Pc1 = 0.8, Pm0 = 0.1, Pm1 = 0.2 (Compare, Martini, &
Zio, 2015; Damm et al., 2016; Karami, & Hasanzadeh, 2015; Lu, &
Huang, 2015; Xu et al., 2014; Zhang et al., 2015; Zhao et al., 2014;).
In the HGA, M = 100, Gmax = 200, Pc = 0.5, Pm = 0.1.
4.3. A small scheduling example
At first, a small scheduling example involving in 18 PAR tasks
is used to illustrate the efficiency of the proposed algorithm. The
request tasks are generated randomly in an SI and the scheduling
results and the performance of different algorithms are shown in
Fig. 6 and Table 2, respectively.
Fig. 6(a) shows the request tasks and the scheduled tasks over
the HPEDF heuristic and the AGA. In Fig. 6(a), the horizontal axis
stands for the timeline, the vertical axis is the task priority, and
a box stands for a radar task. Since the two algorithms both regard the request tasks as non-preemptive ones, the wait intervals
are not utilized to interleave subtasks. Fig. 6(b) shows the request
tasks and the scheduled tasks over the HGA and the proposed algorithm. In Fig. 6(b), the higher rectangle is the transmit interval
and the lower rectangle is the receive interval. Since both the HGA
and the proposed algorithm consider a full radar structure, the
wait intervals are as such fully utilized to transmit or receive intervals of other tasks. Therefore, more tasks are successfully scheduled. However, the performance of the two algorithms is different. Table 2 compares the performance of the four algorithms. It
is obvious that the proposed algorithm offer the best performance
among the four algorithms. The HGA, though also introduces the
task interleaving scheduling, only explores the suboptimal solutions. The detailed reasons will be shown in the following context.
4.4. Simulation results and analysis
A large-scale simulation is conducted to evaluate the performance of the proposed algorithm. The simulation is run on a
Fig. 6. (a) Request tasks and scheduled tasks, (b) Request tasks and scheduled
tasks.
single Inter (R) Core (TM) i7-4790CPU (3.6 GHz) processor with
4 GB memory, Windows 7 OS. The simulation framework focuses
on testing the performance of different scheduling algorithms and
leaves out the signal and data processing procedures in the PAR
(Lee, Kang, Shih, & Sha, 2006). In the simulations, a number of
periodical search tasks are firstly generated and they could be
converted into confirmation tasks at the probability of 0.4. The
confirmation task could be converted into the high precision tracking, precision tracking and normal tracking task at the probability
of 0.2, 0.3, and 0.5 respectively. The tracking task could be converted into the tracking loss task at the probability of 0.05 and
the other tracking tasks maintain at their periods. The number of
search tasks that are converted into confirmation tasks indicates
different number of targets and different workload situations.
The average statistical results are shown in Figs. 7–11 after 50
simulation times.
Figs. 7 and 8 show the comparison of the SSR and the HVR respectively. As the number of targets increases, the available space
on the radar timeline quickly decreases, causing more tasks being
dropped. Since the HPEDF heuristic and the AGA wastefully ignore
the chance of task interleaving, the timeline is quickly filled and
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
JID: EOR
ARTICLE IN PRESS
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
9
Fig. 7. Comparison of the successful scheduling ratio.
Fig. 9. Comparison of the time utilization ratio.
Fig. 8. Comparison of the high value ratio.
Fig. 10. Comparison of the average time shift ratio.
result in more tasks being dropped. The HGA exploits the task interleaving and thus drops fewer tasks and achieves the higher HVR.
However, the proposed algorithm offers the best performance in
both SSR and HVR. The main reason is that the proposed algorithm adopts multiple optimization methods: such as the chaotic
sequences initialization, the elite reservation and mixed ranking
selection operation, the adaptive crossover operation and the adaptive mutation operation, as well as the heuristic task interleaving
method, to integrate the task interleaving and tasks scheduling.
Thus, the proposed algorithm finds out the better optimum compared with the HGA, which only find out the local optimum.
Fig. 9 compares the TURs of the four algorithms. It can be seen
that HPEDF heuristic and AGA utilize the time resource in inefficient manners due to regarding radar tasks as non-preemptive
ones. Though both the HGA and the proposed algorithm utilize
wait intervals to interleave subtasks, the proposed algorithm obtains a higher TUR than the HGA.
Fig. 10 compares the ATSRs of the four algorithms. It can be
seen that the ATSR in the HPEDF heuristic algorithm reaches to
around 70%. By contrast, the other three meta-heuristic algorithms
control the ATSRs below 35%. The main cause is that the HPEDF
heuristic algorithm always prior schedules the task that satisfies
the preset rule. Such heuristic methods always explores solutions
though one path while ignoring other paths and can’t provide well
performance in multiple aspects. By contrast, the meta-heuristic
algorithms are able to explore solutions in the whole solution region through the swarm cooperation and the continuous evolution.
As such, the three meta-heuristic algorithms are able to find out
better solutions and achieve lower ATSRs. However, it is obvious
that the proposed algorithm achieves the lowest ATSR and executes tasks in the timeliest manner among the four algorithms. It
also indicates that the proposed algorithm finds out the global optimum while the HGA only finds out the suboptimal solution.
Table 3 compares average runtimes of the four algorithms in
an SI. It can be seen that the proposed algorithm, the AGA and
the HPEDF heuristic all satisfy the real-time demand of PAR system
(< 50 ms). The HGA is inefficient and can’t satisfy the real-time demand of PAR system (The reasons will show in the following part).
Though the HPEDF heuristic and the AGA provide faster runtime
than the proposed algorithm, the inferior performance that they
have been achieved, shown in Figs. 7–10, should be highlighted. It
is because they both regard the PAR task as non-preemptive ones.
Such a simplification precludes the utilization of wait intervals to
interleave subtasks and make a more efficient use of the PAR timeline. The HGA and the proposed algorithm both model a full PAR
task structure and utilize wait intervals for the purpose of task interleaving. That naturally leads to the higher computational burden
than the AGA and the HPEDF heuristic. However, it is obvious that
the proposed algorithm provides the best performance among the
four algorithms while maintaining a reasonable runtime.
Fig. 11(a)–11(c) shows the convergence speed of the two better algorithms (HGA and proposed algorithm) when the number of
targets is 30, 60 and 90, respectively. The subfigures in Fig. 11(a)
and (b) shows the convergence speed of HGA in detail. It can
be seen that the proposed algorithm possesses higher quality of
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
ARTICLE IN PRESS
JID: EOR
10
[m5G;July 28, 2018;0:22]
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
Table 3
Comparison of average runtime in an SI (ms).
number of targets
10
20
30
40
50
60
70
80
90
100
proposed algorithm
HGA
AGA
HPEDF heuristic
14.6
138.5
10.9
1.5
18.3
142.4
14.2
2.0
20.5
148.1
16.7
2.3
21.7
152.3
18.6
2.7
25.2
163.4
22.0
3.1
27.3
178.8
23.2
3.4
28.9
200.4
24.6
3.8
31.2
202.3
27.1
4.2
36.7
221.5
32.5
4.5
39.2
245.4
35.9
4.7
Conversely, the proposed algorithm optimizes the population
by the chaotic sequences. The initialized population spreads
out the whole solution region in ergodicity, and the quality
of the population is as such better than the HGA.
(2) The HGA adopts the elite selection operation, which means
the better individual has a higher probability to be selected.
Such a selection renders the HGA exploring the solution regions around the elite individuals but ignoring the solution
regions around the poor individuals with a high probability. As such, the HGA easily falls into local optimums. By
contrast, the proposed algorithm uses the elite reservation
and the mixed ranking selection operation. The elite reservation ensures elite individuals directly inherit as the next
generation and the convergence. The mixed ranking selection endows the other individuals pseudo fitness values by
Eq. (13) and sufficiently mixed them in order to let poor
individuals has the same selection probability with better
ones. As such, the proposed algorithm is able to explore solutions in the whole solution region and find out the global
optimum with a higher probability.
(3) The HGA utilizes the crossover operation and the mutation
operation at a constant probability, resulting in a torpid exploration performance. However, the proposed algorithm adjusts the crossover probability and the mutation probability
adaptively by designing the adaptive crossover operator and
the adaptive mutation operator. As such, the efficiency of the
algorithm is significantly improved.
(4) Though the HGA also takes advantage of the task interleaving, where the wait interval is utilized further to accommodate more request tasks, it complicates the task interleaving schedulability analysis due to transporting the
resource constraints for task interleaving to the gene coding, the crossover operation and the mutation operation. By
contrast, there is no need for the proposed algorithm to analyze the constraints in the crossover operation and the mutation operation owing to the proposed heuristic task interleaving method, which is utilized to analyze the feasibility
of task interleaving and to calculate the fitness value of the
individual. The complexity of the proposed algorithm is as
such decreased. Such a performance is also corroborated by
Table 3, which shows the runtime of the HGA is much
slower than the proposed algorithm.
Fig. 11. (a) Comparison of convergence speed when the number of targets is 30, (b)
Comparison of convergence speed when the number of targets is 60, (c) Comparison
of convergence speed when the number of targets is 90.
In a word, the proposed algorithm finds out the better solutions
and possesses faster convergence compared with the HGA. In addition, the proposed algorithm improves the SSR by 40%, the HVR
by 20%, the TUR by 70%, and decreases the ATSR by 80% compared
with the HPEDF heuristic algorithm. As such, the proposed algorithm should be prior considered in the PAR task scheduling.
5. Summary and conclusion
initialized population, more powerful exploration ability and
quicker convergence compared with the HGA. The reasons are able
to be summarized as follows:
(1) The HGA initializes the population by heuristic methods,
resulting in lower quality of the initialized population.
Realizing the optimal resource allocation to tasks is the key
to unlocking the fully multifunctional potential of the PAR. An
optimization scheduling model is structured and a scheduling
method over the hybrid chaotic adaptively genetic algorithm is
proposed in this paper. In the optimization model, the full PAR task
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
JID: EOR
ARTICLE IN PRESS
H. Zhang et al. / European Journal of Operational Research 000 (2018) 1–11
structure is modeled in order to utilize wait intervals to interleave subtasks and the three scheduling principles are integrated
in an objective function to guarantee multi-aspect performance.
The hybrid chaotic adaptively GA adopts the chaotic sequences
initialization, the mixed selection operation as well as the adaptive crossover and the adaptive mutation operation to find out the
global optimum. A heuristic task interleaving algorithm, embed in
the GA frame, is presented for the task interleaving schedulability
analysis and the fitness value calculation. Thereby, the proposed algorithm takes advantages of meta-heuristic algorithms and heuristic algorithms while avoiding their drawbacks. The simulation results show that the proposed algorithm is able to effectively schedule PAR tasks with better performance in multiple aspects compared with the three state-of-art scheduling algorithms. Furthermore, the proposed algorithm possesses the merits of global exploration, fast convergence, and robustness to solve the task scheduling problem in the PAR.
Acknowledgment
This work was supported by the National Youth Science Foundation from China [grant number: 61503408].
References
Baugh, R. A. (1973). Computer control of modern radars (pp. 37–49). NewYork: RCA
Corporation.
Butler, J. M. K. (1998). Tracking and control in multi-function radar. University of London.
Caponetto, R., Fortuna, L., Fazzino, S., & Xibilia, G. M. (2003). Chaotic sequences to
improve the performance of evolutionary algorithm. IEEE Transactions on Evolutionary Computation, 7(3), 289–304.
Chen, J., Tian, Z., Wang, L., Zhang, W., & Cao, J. (2011). Adaptive simultaneous multi-beam dwell scheduling algorithm for multifunction phased array radars. Journal of Information & Computational Science, 8(14), 3051–3061.
Cheng, T., He, Z., & Li, H. (2009). Adaptive dwell scheduling for digital array radar
based on online pulse interleaving. Chinese Journal of Electronics, 18(3), 574–578.
Cheng, T., He, Z., & Tang, T. (2008). Dwell scheduling algorithm for multifunction
phased array radars based on the scheduling gain. Journal of Systems Engineering
and Electronics, 19(3), 479–485.
Cheng, T., He, Z., & Tang, T. (2009). Novel radar dwell scheduling algorithm based on
pulse interleaving. Journal of Systems Engineering and Electronics, 20(2), 247–253.
Coelho, L. D. S. (2008). A quantum particle swarm optimizer with chaotic mutation
operator. Chaos, Solutions and Fractals, 37(5), 1409–1418.
Compare, M., Martini, F., & Zio, E. (2015). Genetic algorithms for condition-based
maintenance optimization under uncertainty. European Journal of Operational
Research, 244(2), 611–623.
Damm, R. B., Resende, M. G. C., & Ronconi, D. P. (2016). A biased random key genetic
algorithm for the field technician scheduling problem. Computers & Operations
Research, 75, 49–63.
Deb, D., Bhattacharjee, R., & Vengadarajan, A. (2015). Resource manager for MIMO
radar. In IEEE Radar Conference (pp. 71–75). IEEE.
Fang, N., Zhou, J., Zhang, R., et al. (2014). A hybrid of real coded genetic algorithm and artificial fish swarm algorithm for short-term optimal hydrothermal
scheduling. Electrical Power and Energy Systems, 62, 617–629.
Ghosh, S., Hansen, J., Rajkumar, R., & Lehoczky, J. (2004). Integrated resource management and scheduling with multi-resource constraints. In IEEE International
Real-Time Systems Symposium: Vol. 33 (pp. 12–22). IEEE Computer Society.
Herr, O., & Goel, A. (2016). Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints. European Journal of
Operational Research, 248(1), 123–135.
Huizing, A. G., & Bloemen, A. A. F. (1996). An efficient scheduling algorithm for a
multifunction radar. In IEEE International Symposium on Phased Array Systems
and Technology (pp. 359–364). IEEE.
Jiménez, M. I., Izquierdo, A., Villacorta, J. J., & Val, L. D. (2009). Analysis and design of multifunction radar task schedulers based on queue. In Ieee/aiaa, Digital
Avionics Systems Conference (pp. 6.B.3-1-6.B.3-9) IEEE.
Jimenez, M. I., Val, L. D., Villacorta, J. J., & Izquierdo, A. (2012). Design of task
scheduling process for a multifunction radar. IET Radar Sonar & Navigation, 6(5),
341–347.
Kantz, H., & Schreiber, T. (2004). Nonlinear time series analysis. Cambridge, UK: Cambridge University Press.
Karami, A. H., & Hasanzadeh, M. (2015). An adaptive genetic algorithm for robot motion planning in 2D complex environments. Computers and Electrical Engineering,
43, 317–329.
Lee, C. G., Kang, P. S., Shih, C. S., & Sha, L. (2006). Schedulability envelope for real–
time radar dwell scheduling. IEEE Transactions on Computers, 55(12), 1599–1613.
[m5G;July 28, 2018;0:22]
11
Lu, H., & Huang, Y. (2015). An efficient genetic algorithm with a corner space algorithm for a cutting stock problem in the TFT-LCD industry. European Journal of
Operational Research, 246, 51–66.
Lu, J., Xiao, H., Xi, Z., & Zhang, M. (2011). Multifunction phased array radar resource
management: Real-time scheduling algorithm. Journal of Computational Information Systems, 7(2), 385–393.
Lu, J., Xiao, H., Xi, Z., & Zhang, M. (2013). Phased array radar resource management:
Task scheduling and performance evaluation. Journal of Computational Information Systems, 9(3), 1131–1138.
Mehrdad, A., & Reza, Z. (2015). An effective asexual genetic algorithm for solving
the job shop scheduling problem. Computers & Industrial Engineering, 83, 123–
138.
Mir, H. S., & Abdelaziz, F. B. (2012). Cyclic task scheduling for multifunction radar.
IEEE Transactions on Automation Science & Engineering, 9(3), 529–537.
Mir, H. S., & Guitouni, A. (2014). Variable dwell time task scheduling for multifunction radar. IEEE Transactions on Automation Science & Engineering, 11(2),
463–472.
Moukrim, A., Quilliot, A., & Toussaint, H. (2015). An effective branch-and-price algorithm for the preemptive resource constrained project scheduling problem
based on minimal interval order enumeration. European Journal of Operational
Research, 244(2), 360–368.
Orman, A. J., Potts, C. N., Shahani, A. K., & Moore, A. R. (1996). Scheduling for a multifunction phased array radar system. European Journal of Operational Research,
90(1), 13–25.
Oron, D., Shabtay, D., & Steiner, G. (2016). Single machine scheduling with two competing agents and equal job processing times. Annals of Operations Research,
238(1–2), 145–178.
Pan, W. (2014). Application of adaptive genetic algorithm to optimal scheduling
of phased array radar. Electronic Information Warfare Technology, 29(1), 38–
41.
Peitgen, H. O., Jurgens, H., & Saupe, D. (2004). Chaos and fractals: New frontiers of
science (2nd ed.). Berlin: Springer.
Pessoa, L. S., & Andrade, C. E. (2018). Heuristics for a flowshop scheduling problem
with stepwise job objective function. European Journal of Operational Research,
266, 950–962.
Reinosorondinel, R., Yu, T. Y., & Torres, S. (2010). Multifunction phased-array radar:
Time balance scheduler for adaptive weather sensing. Journal of Atmospheric &
Oceanic Technology, 27(11), 1854–1867.
Sgambato, P., Celentano, S., Dio, C. D., & Petrillo, C. (2016). A flexible on-line
scheduling algorithm for multifunctional radar. In Radar Conference (pp. 1–5).
IEEE.
Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2018). Preemptive models of
scheduling with controllable processing times and of scheduling with imprecise
computation: A review of solution approaches. European Journal of Operational
Research, 266, 795–818.
Singh, M. R., & Mahapatra, S. S. (2016). A quantum behaved particle swarm optimization for flexible job shop scheduling. Computers & Industrial Engineering,
93, 36–44.
Sioud, A., & Gagné, C. (2018). Enhanced migrating birds optimization algorithm for
the permutation flow shop problem with sequence dependent setup times. European Journal of Operational Research, 264, 66–73.
Wang, S., He, J., Wang, B., & Ji, R. (2014). Research on adaptive scheduling algorithm
based on improved genetic algorithm for multifunctional phased array radar.
icfcce-14, 10(1), 13–20.
Xu, Y., Li, K., Hu, J., & Li, K. (2014). A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues. Information Sciences, 270(6), 255–287.
Yao, X., Liu, Y., & Lin, G. (2002). Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 3(2), 82–102.
Zhang, H. W., Xie, J. W., & Sheng, C. (2016b). Scheduling method for phased array
radar over chaos adaptively genetic algorithm. In International Conference on Information Science & Technology (pp. 111–116). IEEE.
Zhang, H., Xie, J., & Sheng, C. (2016a). Adaptive scheduling algorithm over comprehensive priority for phased array radar. Acta Armamentarii, 37(11), 2164–
2169.
Zhang, H., Xie, J., Zong, B., Lu, W., & Sheng, C. (2017). Dynamic priority scheduling
method for the air-defence phased array radar. IET Radar Sonar Navigation, 11(7),
1140–1146.
Zhang, L., & Wong, T. N. (2015). An object-coding genetic algorithm for integrated process planning and scheduling. European Journal of Operational Research, 244(2), 434–444.
Zhang, R., Ong, S. K., & Nee, A. Y. C. (2015). A simulation-based genetic algorithm approach for remanufacturing process planning and scheduling. Applied Soft Computing, 37, 521–532.
Zhao, W., Zhao, J., Zhao, S., et al. (2014). Resources scheduling for data relay satellite with microwave and optical hybrid links based on improved niche genetic
algorithm. Optik, 125, 3370–3375.
Zheng, Y. J., Tian, K. S., Xing, X. N., et al. (2016). Optimal scheduling for phased
array radar based on niche genetic algorithm. Modern Defense Technology, 44(1),
168–174.
Zhou, Y., Wang, G. Y., Wang, X. S., et al. (2006). Optimal scheduling using hybrid GA
with heuristic rules for phased array radar. Systems Engineering and Electronics,
28(7), 992–996.
Zhou, Y., Wang, X. S., Wang, L. D., et al. (2005). Optimal scheduling for phased array
radar based on genetic algorithm. Systems Engineering and Electronics, 27(12),
1977–1980.
Please cite this article as: H. Zhang et al., A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar,
European Journal of Operational Research (2018), https://doi.org/10.1016/j.ejor.2018.07.012
Документ
Категория
Без категории
Просмотров
0
Размер файла
2 111 Кб
Теги
ejor, 012, 2018
1/--страниц
Пожаловаться на содержимое документа