Task Scheduling for Phased Array Multi-Function Radar

1. Introduction

Historically, radar systems were designed to perform specific functions using individual mechanical radars. Today, Multi-Function Radars (MFRs) leverage phased arrays to electronically steer the radar beam, enabling rapid execution of multiple functions such as tracking, surveillance, and fire control. To achieve these functions, the start times of individual transmit and receive tasks must be carefully scheduled. Each task is defined by start time t_start, duration t_dwell, and priority p. A single function may consist of multiple tasks, each with unique t_start, t_dwell, and p. Efficiently managing these tasks to optimize radar performance is the essence of Radar Resource Management (RRM) [1].

RRM involves selecting, prioritizing, and scheduling tasks. This chapter focuses on the scheduling aspect of RRM. When tasks are initially set for execution, overlaps can occur since radars typically cannot perform tasks simultaneously. Therefore, tasks must be scheduled sequentially. The scheduler’s goal is to arrange tasks to avoid overlaps and maximize task completion within specific time intervals, known as execution time windows. Tasks scheduled to start at t_start within an execution window are assigned new scheduled times t_sched to minimize a predefined cost function. If a task cannot be scheduled within the available time, it is dropped. The scheduler must decide which tasks to drop, usually prioritizing lower-priority tasks to minimize overall cost.

Resource management (RRM) is a critical issue when radar performs multiple functions, each comprising numerous tasks. These tasks request radar resources and have different priorities, often overlapping in time. The radar’s ability to assign appropriate resources to all functions and tasks ultimately determines its performance. Scheduling algorithms are designed to sequence tasks to achieve optimal or sub-optimal performance.

Figure 1 illustrates a Navy ship-borne multi-function radar performing volume search, horizon search, target tracking, and missile guidance. Here, RRM is the brain of the radar. It is an essential component; without it, the radar cannot operate. Moreover, an improved RRM scheduler enhances the radar’s effectiveness and efficiency.

Optimal task scheduling can theoretically be achieved through brute-force search or branch-and-bound methods, but these approaches are impractical for real-time radar systems due to the NP-hard nature of the scheduling problem [2]. As a result, sub-optimal scheduling algorithms have been developed to approximate the global optimum with greater computational efficiency. Key scheduling algorithms include Earliest Start Time (EST), Earliest Deadline (ED) [3], heuristic-based approaches [4], Random Shifted Start Time (RSST) [5], Gaussian RSST (GRSST) [6], Dual-Side-Scheduling (DSS) [7], task selection (TS) [8], greedy algorithms [9], a thorough literature review of AI-based RRM techniques [10], and a few AI/ML-based methods [11, 12, 13, 14].

Among these algorithms, RSST and GRSST use random search, which typically find a better solution from more random searches [5, 6]. The DSS algorithm introduces two smaller scheduling windows by a separator [7]. The TS algorithm handles overloading tasks, which will drop less important tasks, resulting in fewer tasks for scheduling [8]. Supervised machine learning and reinforcement learning (RL) are used to improve the efficiency of the Monte Carlo Tree Search (MCTS) [12], which were further enhanced by deep RL (DRL), transfer learning (TL) [13], and a modified MuZero approach [14]. Compared with traditional approaches [2, 3, 4, 5, 6, 7, 8, 9], AI/ML methods [11, 12, 13, 14] still need better efficiency for real-world applications. Typically, the scheduling time window is around 200 ms. Computation of a practical radar scheduler shall not take too much time from this time window, less than 5%, that is, 10 ms.

We will focus on the traditional scheduling approaches. Among those algorithms, the Earliest Start Time (EST) and Earliest Deadline (ED) algorithms are the simplest and most time efficient. Both algorithms follow a first-come-first-served principle, scheduling tasks based on their start time in EST and their deadline in ED, respectively. This approach involves relocating tasks through a head-to-tail scenario. However, this strategy can result in tasks being scheduled much earlier than necessary, leading to ineffectiveness.

To improve EST’s and ED’s performance, we propose two new enhancements. First, a modified EST (MEST) is developed, which removes the head-to-tail restriction, resulting in much better performance for underloading situations [15]. We introduced the same modification to ED (MED), achieving similar improvement [16]. Secondly, we noticed that both EST and ED use start time or deadline time for scheduling, but the task priorities have not been used at all. We proposed a priority-based Minimum Cost First (MCF) algorithm and enhanced MCF (EMCF) [17]. Simulation studies show that these two new algorithms perform significantly better than other traditional approaches.

This chapter is organized as follows:

Section 1: Provides a high-level introduction to radar task scheduling, summarizing both traditional and AI/ML approaches.

Section 2: Presents the problem formulation and introduces the cost function.

Section 3: Discusses two baseline algorithms, EST and ED.

Section 4: Describes MEST and MED, along with the simulation results. These modified algorithms address the ineffectiveness of EST and ED in underloading situations.

Section 5: Details both MCF and EMCF, with comparison to the baseline approaches. These new algorithms incorporate priority into the assignment process, significantly reducing costs.

Section 6: Concludes the chapter.

2. Problem formulation

In this section, we formulated radar task scheduling as a cost function optimization problem. Consider a radar system designed to handle N tasks within an execution time window of size L. Each task has six parameters: tstart, tdwell, p, tdeadline=tstart+tdwell, tearliest, tlatest. In this problem, tasks cannot be executed in parallel, so the ideal value for tdwell would be L/N, ensuring that the sum of all tasks’ r tdwell equals the entire window size L. These variables are used for all tasks. For a specific task n, we will add “(n)” after the variable. For example, tstart(1) is the start time for task 1.

The execution window size is normalized such that L = 1, with tstart ranging from 0 to 1 and tdwell ranging from 0 to 2/N. In real simulations, the number of tasks in an execution window might be larger or smaller than the designed N tasks. This actual number of tasks is denoted as Nactual and the ratio between Nactual and N is called the loading rate, γ = Nactual/N. If γ <100%, the radar is under-loaded; if γ > 100%, the radar is over-loaded.

For a particular loading rate, the tdwell of all tasks are normalized so that their sum exactly equals the loading rate γ. This process, called tdwell normalization, ensures that loading rates less than or equal to 100% remain underloaded and all tasks fit within the task sequence. Without tdwell normalization, the random distribution of tdwell could cause their sum to exceed 1, necessitating the dropping of a task. This can significantly skew cost results when scheduling for a specific loading rate.

A 5-task sequence with and without tdwell normalization can be seen below:

In Figure 2, an unscheduled task sequence is shown where each rounded rectangle represents a task. The left edge of the task indicates its start time, the width corresponds to the dwell time, and the more red and thicker the border, the higher the task’s priority. When generating the tdwell for each task, all tdwell values are below average. This results in a task sequence that is supposed to be 100% loaded but only occupies about one-third to one-half of the entire execution window. Conversely, if all tdwell values are above average, the sequence could take much more than 100% of the window. This issue is addressed using tdwell normalization.

Real radar systems have different scheduling time windows, which require a normalized window length for algorithm development, so that performance evaluation can be done fairly. We use time-length “1” as the normalized time window. The normalization process is as follows. Step 1: sum up the dwell times of all tasks. Let’s assume the summation time is 0.9 second in total. Step 2: Calculate radar time for the aimed loading rate. For example, 50% loading rate is 0.5 second. Step 3: Recalculate the dwell time for each task, divided by 0.9 and then multiplied by 0.5. The three steps will generate tasks of 50% loading rate, that is, 0.5 seconds of total dwell time.

A scheduling algorithm must arrange the tasks across the execution window such that as many tasks as possible are executed and scheduled as close to their tstart as possible. The resulting scheduled time from the algorithm is called tsched. Each task will have an associated cost, C(n), which increases when tsched is far from tstart. The total cost, J, of the scheduled times is the sum of the individual costs of the tasks. Relevant cost equations are shown below.

Each task has a unique identifier number, and each parameter is indexed by this ID. For example, task #2’s start time can be written as tstart2 . The cost of the task depends on the difference between tschedn and tstartn. The farther the scheduled time is from its original start time, the greater the cost accrued. This difference is multiplied by a priority, pn, implying that the higher the task’s priority, the higher the cost of the task. For our purposes, pn will be a random number between 0.1 and 0.9 in intervals of 0.1. The difference in time ranges from 0 to 1, and when multiplied by the priority, it will always result in a product lower than 1.

In this report, only underloaded task sequences are evaluated, and we consider the case where all tasks can be scheduled anywhere in the execution window, that is, tearliest = 0 and tlatest = 1. Because of this, no tasks need to be dropped, and thus no drop cost is outlined.

3. Two baseline algorithms: The EST and ED

The Earliest Start Time (EST) and Earliest Deadline (ED) algorithms are two baseline scheduling algorithms that are simple to implement and very fast, making them suitable for processing large amounts of tasks in real-world radar systems. However, their performance compared to more advanced methods like machine-learning-based approaches, the branch and bound algorithm, or RSST leaves much to be desired. EST and ED do not consider priority when scheduling; instead, they only consider a task’s tstart or tdeadline, respectively.

The EST algorithm schedules tasks in order of increasing start times tstart, meaning the task with an earlier start time gets scheduled first. The ED algorithm schedules tasks in order of increasing deadlines tdeadline, meaning the task with an earlier deadline gets scheduled first. Both algorithms use a head-to-tail connection for scheduling, where the end of one task coincides with the scheduled time of the next task.

One area where EST and ED struggle is in underloaded situations. Due to the head-to-tail restriction, tasks with later start times will be scheduled much earlier. An example of scheduling with both EST and ED for a simple 100% loaded 10-task sequence is shown below in Figure 3.

Even though EST and ED schedule tasks quickly, they have two fundamental drawbacks: ineffectiveness in underloading situations and the lack of consideration for task priority in the assignment process.

4. MEST and MED algorithms for underloading situations

In underloading situations, EST and ED tend to arrange tasks toward the left side of the time window, which increases the overall cost. To overcome this drawback, we proposed the Modified Earliest Start Time (MEST) and Modified Earliest Deadline (MED) algorithms. These enhanced versions of the baseline EST and ED algorithms maintain similar speed and the ability to handle large amounts of tasks. Like their unmodified counterparts, the modified algorithms schedule tasks in the same order. However, the restriction of scheduling tasks head-to-tail is relaxed.

For the next task with the earliest tstart or tdeadline among the unscheduled tasks, the modified algorithm schedules the task at its tstart provided that the sum of the remaining tasks’ tdwell does not exceed the remaining time in the window. Otherwise, MEST/MED schedules it right after the previous task (head-to-tail connection). MEST and MED aim to improve the performance of EST and ED in underloaded cases by scheduling tasks right at their tstart whenever possible.

In overloaded situations, the modified algorithms will perform similar to EST and ED since the modified versions would only perform head-to-tail connections (with no remaining time). Because of this, the MEST and MED algorithms are almost always better than the EST and ED algorithms across all loading rates. An example of an underloaded task sequence scheduled using ED and MED is shown below.

As seen in Figure 4, later tasks such as the one starting at around 0.9 need to be scheduled much earlier when using a head-to-tail connection as seen when scheduling by ED. MED resolves this by scheduling it instead at its original tstart.

The MEST and MED algorithms improve the baseline algorithms in underloaded cases by removing the head-to-tail restriction inherent in both. By eliminating this restriction, the modified algorithms perform much better than their unmodified counterparts for loading rates of 80% and below. For all other underloaded loading rates, the modified algorithms accrue costs very similar to their respective unmodified algorithms. The time efficiency of MEST and MED is comparable to EST and ED, making them very feasible for real-world radar systems. This “modified” approach could be applied to other scheduling algorithms to increase their efficacy in underloaded circumstances if a similar head-to-tail restriction exists.

The algorithms are compared by running 10,000 simulations with randomly generated tasks for 13 different loading rates. The simulated multi-function radar is designed to handle 50 tasks within the execution window (N = 50). The average cost for both algorithms is calculated using eqs. (1) through (3). The average computation time used for each algorithm and loading rate is recorded from MATLAB. Since modified versions would have the same performance as the unmodified algorithms for overloaded cases, only loading rates under 100% were considered. The following loading rates were used: 10, 20, 30, 40, 50, 60, 70, 80, 90, 92, 94, 96, 98%. The differences between EST and MEST are largely the same as the differences between ED and MED. To simplify the report results, ED will be used to represent the unmodified algorithms and MED will be used to represent the modified algorithms.

Each task has a tstart generated using a uniform distribution between 0 and 1−tdwell such that all tasks cannot extend past the end of the execution window. The tdwell is generated using a uniform distribution between 0 and 2N with an average of 1N and thus on average sum to 1. The tearliest and the tlatest are set to 0 and 1 respectively meaning all tasks can be scheduled anywhere within the window. The p of each task is generated uniformly between 0.1 and 0.9 in increments of 0.1. For each loading rate, γ, the number of tasks to be scheduled, Nactual, is given by Nactual=γ∗N.

Figure 5 illustrates the performance improvement, showing that a lower loading rate results in better improvement. Figure 6 demonstrates that the computation time is less than 0.1 ms, making it highly efficient for practical applications.

5. MCF and EMCF algorithms with priority-embedded

These four algorithms (EST, ED, MEST, and MED) missed a critical factor: task prioritization. Higher priority tasks should be treated differently in scheduling algorithms, as they directly affect the cost to be optimized. We propose the Minimum Cost First (MCF) algorithm, which incorporates priority when assigning tasks. Furthermore, an enhanced version of MCF is also proposed.

5.1 MCF algorithm

The MCF algorithm aims to minimize the total scheduled task sequence cost through a greedy approach. The algorithm calculates the cost of each task when hypothetically scheduling it and then schedules the task with the lowest cost. Instead of only scheduling on one side of the execution window, tasks are scheduled by alternating from the start and the end of the window. This reduces the chance of tasks being left behind, as tasks not scheduled near their start time will incur higher costs as more tasks get scheduled.

Alternating the tasks also lowers the cost if tasks are left behind, as these tasks will be scheduled near the middle of the window where they would usually be scheduled at the end if not alternated. The pseudo-code of the MCF algorithm is shown in Table 1. The MCF algorithm is put through numerical simulations to find its average cost and time. Figures 7 and 8 show the average costs and cost ratio over EST using the classic cost function. Figures 9 and 10 show the same but using the tauless cost function. The computation time of MCF is shown in Figure 11. In these figures, blue, red, and yellow represent EST, RSST, and MCF, respectively.

1	Initialize variables: wind_start = 0, wind_end = 1, bool_start = true
2	For i = 1: N
3	If bool_start // Schedule at start of sequence
4	costs_start ← calculate cost of all tasks using Eq. 2–5 if scheduled at wind_start
5	min_cost, min_idx ← find minimum cost from costs_start
6	tsched(min_idx) = wind_start, bool_start = false
7	wind_start = wind_start + tdwell(min_idx)
8	Else // Scheduling at end of sequence
9	costs_end ← calculate cost of all tasks using if scheduled at wind_end - tdwell
10	min_cost, min_idx ← find minimum cost from costs_end
11	wind_end = wind_end - tdwell(min_idx)
12	tsched(min_idx) = wind_end, bool_start = true
13	End
13	costs(min_idx) = min_cost
14	p(min_idx) = Inf // Already scheduled tasks produce an infinite cost
15	End

Table 1.

MCF scheduling algorithm.

As seen in Figures 7 and 8, when using the classic cost function, MCF has much lower costs than both EST and RSST. Its average cost goes as low as 0.3 times that of EST and averages around 0.42 times over all tasks. RSST still outperforms MCF with five tasks, as RSST almost always gets the optimal solution with small numbers of tasks and a large enough K iterations.

Figures 9 and 10 illustrate how the change in cost function can drastically affect the cost of MCF. When using the tauless cost function, MCF’s cost is significantly higher than EST, reaching up to 5 times larger than EST and averaging 3.3 times larger over all tasks. This sudden change in cost between cost functions occurs due to how MCF schedules tasks and how the classic cost function operates when scheduling at the ends of the execution window.

When scheduling at the start or end of the execution window, the classic cost function only depends on the priority of the task, regardless of its position in the window. For subsequent tasks, the distance between tstart and tsched becomes more significant as tasks are scheduled further from the ends of the window. This results in an unintuitive optimal scheduling pattern and those algorithms like EST generally do not perform well in, but MCF matches very well.

When using the tauless cost function, scheduling becomes more intuitive. Scheduling the task with the minimum cost first often results in low-priority tasks being scheduled first, which might cause high-priority tasks to be scheduled later, thus significantly increasing the cost. Missing one high-priority task to be scheduled before a lower-priority task can cause the high-priority task to accrue massive costs until it is the last task and needs to be scheduled.

Figure 11 shows the average computation time of MCF. MCF averages 0.47 ms over all tasks and is very comparable to the runtime of EST. MCF improves on the cost of EST and RSST, when using the classic cost function, while also being close to the computation time of EST. A drawback of MCF is that even with alternating, tasks are still left behind and are scheduled much later than they should be. An example of this phenomenon can be seen in Figures 12 and 13.

In Figure 10, tasks that are between 0.9 and 1 in the execution window are left behind and will only get scheduled after every other task is scheduled. An enhanced version of the algorithm addresses this issue and decreases the cost by scheduling based on the overall cost instead of just the per-task cost.

5.2 EMCF algorithm

The Enhanced Minimum Cost First EMCF algorithm improves the cost performance of MCF at the expense of time efficiency. EMCF schedules tasks based on the total scheduled task sequence cost Eq. (1) instead of the per-task cost Eq. (2). Like MCF, tasks are scheduled by alternating between the start and end of the execution window. To choose which task to schedule, three tasks are selected: one with the earliest start time EST, one with the earliest deadline ED, and one with the minimum cost MCF. When scheduling at the end, the latest start time or deadline is chosen instead of the earliest.

Only three tasks are chosen to reduce computation time while maintaining a lower cost. For each task, the remaining sequence is completed using a simple scheduling algorithm like EST. The task that gets scheduled is the one that results in the lowest overall cost of the three. The pseudo-code of the EMCF algorithm is shown in Table 2.

1	Initialize variables: wind_start = 0, wind_end = 1, bool_start = true, tdeadline = tstart + tdwell, tshift = tstart
2	For i = 1:N
3		If bool_start
4			( idxEST, idxED, idxMCF) ← find indices of unscheduled tasks with earliest tstart, tdeadline and minimum cost at wind_start.
5			costsEST ← conduct EST Scheduling Algorithm using tshift.
6			prev_tshift = tshift
7			costsED ← conduct EST Scheduling Algorithm using tshiftidxED = -N + i-1.
8			tshift = prev_tshift
9			costsMCF ← conduct EST Scheduling Algorithm using tshiftidxMCF = -N + i-1.
10		Else
11			(idxEST, idxED, idxMCF) ← find indices of unscheduled tasks with latest tstart, tdeadline and minimum cost at wind_end.
12			costsEST ← conduct EST Scheduling Algorithm using tshift.
13			prev_tshift = tshift
14			costsED ← conduct EST Scheduling Algorithm using tshiftidxED = N-i + 1.
15			tshift = prev_tshift
16			costMCF ← conduct EST Scheduling Algorithm using tshiftidxMCF = N-i + 1.
17		End
18		tshift = prev_tshift
19		costsmin ← find minimum of: sum of costsEST, sum of costsED and sum of costsMCF.
20		idx ← pick the task that corresponds to costsmin.
21		costs(idx) = costsmin(idx)
22		If bool_start: tshift(idx) = -N + i-1
23		If not bool_start: tshift(idx) = N-i + 1
24		bool_start = not bool_start
25		update wind_start and wind_end using task idx.
26	End

Table 2.

EMCF scheduling algorithm.

When running the EST algorithm in lines 5–9 and 12–16, tshift is used to alter the starting times such that some tasks always start first and others start last while keeping tstart the same for cost calculation purposes. By making tshift equal to times that are before and after the execution window, tasks can be forced to get scheduled at the start or end without interfering with the rest of the scheduling. Numerical simulations are performed, the cost graphs are seen in Figures 14–18 shows the time graph.

With the classic cost function, EMCF improves upon MCF in terms of cost for all numbers of tasks. From Figures 14 and 15, the EMCF algorithm produces a cost that goes as low as 0.11x of EST and averages around 0.19x of EST over all tasks. EMCF is strictly better than MCF in terms of cost for every number of tasks. EMCF has a slightly higher cost than RSST at five tasks as RSST usually gets the optimal solution with enough iterations at low numbers of tasks. Note that the absolute cost values are indicators how the algorithms perform, but the cost ratios provide a better comparison to the baseline algorithm. Here, the EST algorithm is chosen as the baseline for the cost ratio calculation.

In the figures below, blue, red, yellow, and pink represent EST, RSST, MCF, and EMCF, respectively.

Using the tauless cost function, EMCF drastically improves upon the MCF algorithm. By checking how scheduling a task affects the entire sequence, the algorithm can make sure that scheduling a task does not push back higher priority tasks later. Because of this, EMCF is suitable to schedule using the tauless cost function and produces less costs than EST and RSST. EMCF accrues costs around 0.5x of EST.

The EMCF algorithm performs better than all other algorithms in terms of cost using both classic and tauless cost functions. However, the time it takes to run is larger than EST and MCF but is still less than RSST. EMCF takes around 4.7 ms on average over all number of tasks. If the radar system allows for the increased computation time, it is recommended to use EMCF over MCF.

The number of times that each sub-algorithm in EMCF leads to the scheduled task is analyzed. The EMCF algorithm and which task is selected to get scheduled is somewhat independent of which cost function you use. Because of this, only the results from using the classic cost function are used. Table 3 shows the percentages of how often each algorithm or group of algorithms provide the best task with the lowest total cost. Table 4 shows the percentages of how often the individual algorithms provide the best task.

Algorithms	Number of tasks
	5	10	15	20	25	30	35	40	45	50
EST	3	3	3	4	4	5	4	5	5	5
ED	3	3	4	4	4	4	5	4	4	5
MCF	25	25	25	25	24	24	24	24	24	23
EST & ED	10	14	17	18	20	22	23	24	25	26
EST & MCF	5	5	5	5	5	4	4	4	4	4
ED & MCF	5	5	4	4	4	4	4	4	3	3
EST & ED & MCF	49	45	42	40	39	37	36	35	35	34

Table 3.

Percentages of combined best tasks.

Algorithms	Number of tasks
	5	10	15	20	25	30	35	40	45	50
EST	31	31	32	32	33	33	33	34	34	34
ED	31	31	32	32	32	33	33	33	33	34
MCF	39	37	36	36	35	34	33	33	33	32

Table 4.

Percentages of single best task.

The computation time of EMCF is well below 5% of the time widow 200 ms when there are 45 or less tasks. Note that the number of tasks in a real radar system is 20–30. The EMCF algorithm maximizes the performance and keeps the computation practical.

For most cases, choosing a task with EST, ED, or MCF provides the same solution and is thus used as the “best” solution. From Table 1, MCF provides the most unique best solutions out of the three algorithms as EST and ED are likely to be the same task. Table 2 shows us that for smaller numbers of tasks, MCF provides the best task while with larger numbers of tasks, EST, ED, and MCF all provide the best task out of the three at the same rate.

6. Conclusion

Two modified approaches to baseline radar task scheduling algorithms were proposed: Modified Earliest Start Time (MEST) and Modified Earliest Deadline (MED). These algorithms improve upon the unmodified versions in underloaded cases by removing the head-to-tail restriction inherent in both. By eliminating this restriction, the modified algorithms perform much better than their unmodified counterparts for loading rates of 80% and below. Additionally, two algorithms were proposed using the cost function as a scheduling tool. The first algorithm, Minimum Cost First (MCF), schedules tasks based on the lowest individual task cost. The second algorithm, Enhanced Minimum Cost First (EMCF), schedules tasks based on overall task cost. The MCF algorithm provides a solution that is three times better than EST, while the EMCF algorithm offers a solution that is 6.2 times better than EST. The proposed scheduling algorithms are suitable for real-world radar systems due to their low computation time and low costs.

For future work, efficiency improvements are needed for current AI/ML approaches. Combining AI/ML with traditional methods may offer new solutions for radar scheduling. Efficiency could be directly enhanced through parallel and/or quantum computing.