A Modified Earliest Start Time (MEST) Algorithm for Multi-Function Radar Task Scheduling
Zhen Ding, Zhen Qu, Peter W. Moo · 2022
The earliest start time (EST) algorithm, a head-tail connection approach, has been used for many scheduling applications. This algorithm is simple and efficient. The drawback of its head-tail connection results in its mediocre performance. We propose a Modified EST (MEST) algorithm in this paper, which removes the head-tail assumption, as long as the rest of tasks is still schedulable. The new algorithm assigns the current task’s start time when possible, not the tail time as done in the EST. In this way, the time shift for the current task is minimized. Overall, the total cost, a measure of all time shifts, would be decreased significantly. The algorithm is evaluated by a multi-function radar scheduling problem. Comparing the cost, Monte Carlo simulation shows that the MEST is much lower than the EST when the radar loading rate is below around 80%, and the two algorithms perform the same when the radar loading rate is above around 80%, with the EST’s performance being the worst case for the MEST. In addition, the MEST is very efficient for real world radar systems.