WU Jian,LU Fang,ZHANG Jiawei,3,*,YANG Jinghui,and XING Lining,

1.College of Systems Engineering,National University of Defense Technology,Changsha 410073,China;2.College of Logistics and Transportation,Central South University of Forestry and Technology,Changsha 410004,China;3.College of Information and Communication,National University of Defense Technology,Xi’an 710106,China;4.College of Engineering,Shanghai Polytechnic University,Shanghai 201209,China

Abstract: In the imaging observation system, imaging task scheduling is an important topic. Most scholars study the imaging task scheduling from the perspective of static priority, and only a few from the perspective of dynamic priority. However,the priority of the imaging task is dynamic in actual engineering. To supplement the research on imaging observation, this paper proposes the task priority model, dynamic scheduling strategy and Heuristic algorithm. At first, this paper analyzes the relevant theoretical basis of imaging observation, decomposes the task priority into four parts, including target priority, imaging task priority, track, telemetry & control (TT&C)requirement priority and data transmission requirement priority, summarizes the attribute factors that affect the above four types of priority in detail, and designs the corresponding priority model. Then, this paper takes the emergency tasks scheduling problem as the background, proposes the dynamic scheduling strategy and heuristic algorithm. Finally, the task priority model,dynamic scheduling strategy and heuristic algorithm are verified by experiments.

Keywords: imaging observation system, imaging task priority,task priority model, dynamic scheduling strategy, heuristic algorithm.

1.Introduction

In the imaging observation system,imaging task scheduling refers to using reasonable methods to schedule various types of satellites and tasks with multiple constraints.The fast expansion of various fields in the imaging observation system,such as the huge growth of users’requirement and space resources, increases the difficulty of imaging task scheduling[1].

The task priority is an important issue, which plays an important role in imaging observation.The order in which different imaging tasks accept space resources is determined by priority. It is subcategorized into fixed priority and dynamic priority. The imaging task with the fixed priority cannot allocate space resources according to the users’ dynamic requirement. Only the imaging task with the dynamic priority can meet the users’dynamic requirement.At the same time,the task priority has a deep influence on the scheduling results. Therefore, how to set the task priority reasonably is a very important issue.

However, the current research on the task priority for imaging observation is not sufficient, which lacks corresponding theoretical basis and an efficient dynamic adjustment strategy. Therefore, in the actual project, the users only determine the task priority based on their own experience,which results in inevitable errors and uncertainties.Most scholars study the imaging tasks scheduling from the perspective of the static priority, and only a few scholars study it from the perspective of dynamic priority. Therefore,we make some attempts to schedule the imaging tasks reasonably.(i) We propose the task priority model which is decomposed into four parts based on the basic characters of various priorities, and calculate the initial priority of imaging tasks.(ii)We propose the dynamic scheduling strategy to get better results,which are consistent with actual engineering.This strategy is easy to understand and be applied to the actual engineering.(iii)The problem of the emergency tasks scheduling problem is taken as the background,and the heuristic algorithm is proposed to schedule the imaging tasks.

2.Literature review

Research on the imaging observation problem mainly involves the related knowledge of the task priority model and algorithm.Therefore,we will review the literature from the following two parts.

2.1 Task priority model

At present,scholars have proposed some task priority models, including earliest deadline first (EDF) [2–4], least slack first (LSF) [5], highest value first (HVF) [6], and highest value density first(HVDF)[7,8].In order to handle the system overload,Semghouni et al.[2]proposed a new scheduling strategy to improve the EDF algorithm’s ability based on the value of the task. Chantem et al. [3] proposed a real-time task model,which allows periodic tasks to change over certain periods.Balbastre et al.[4]proposed an algorithm for calculating the minimum deadline for periodic tasks. This algorithm accelerates the task scheduling speed, reduces the waiting time, and improves the efficiency of the system. Jin et al. [5] used the integrated weighted method to synthesize the EDF and LSF to design the task priority,and adjust the weight of the two task priority models through the weight parameters.Burns et al.[6]pointed out one way to improve the flexibility and efficiency of real-time systems,which are based on a valuebased priority scheduling strategy. Buttazzo et al. [7] determined the value density of the task based on the value and the maximum execution time of the task,and proposed the HVDF model to ensure the task priority.Based on the value and remaining execution time for the task, Aldarmi and Burns[8]proposed a real-time task priority model to optimize the utilization of system resources.

2.2 Task scheduling algorithm

At present, there is only few research focusing on task scheduling algorithms in the field of imaging observation,and most of them focus on the fixed priority.Therefore,this paper studies the scheduling algorithms from other fields and uses this as a research basis.

At present, scholars have proposed some task scheduling algorithms, including simulated annealing (SA) [9–11], artificial bee colony (ABC) algorithm [12,13], genetic algorithms (GAs) [14–16], ant colony optimization (ACO) [17–20] and particle swarm optimization(PSO)[21,22]which have been applied to solving the task scheduling.Afzalirad and Shafipour[23]proposed an efficient GA to solve the scheduling problem of the resourceconstrained unrelated parallel machine.In order to achieve better scheduling results, Lu[24]proposed the GA to cut down the task scheduling time.Ji et al.[25]presented the orthogonal design-based non-dominated sorting genetic algorithm III (ONSGA-III)algorithm to schedule the lockage co-scheduling of Three Gorges Dam and Gezhou Dam(LCSTD)problem.

3.Task priority model for imaging observation

3.1 Target priority model

This section establishes a target priority evaluation indicator system,which is shown in Table 1.

Table 1 Target priority evaluation indicator system

Each factor in the indicator system has different degrees of impact on the target priority.Therefore,each factor should be evaluated. We introduce the weight, which reflects the impact degree of each factor. Therefore, this paper establishes the priority calculation model.

Ptargetindicates the target priority,ωiindicates the weight, andvAttriindicates attribute values of each factor.

3.1.1 Determining the weight

The relative comparison method is an empirical scoring method,which lists all factors to establish anm×msquare matrix.Then the user compares and scores each factor in pairs. Finally, the scores of each factor are summed and standardized.We use the 0-1 method to score each factor.The remaining elements are determined according to the following rules and meetaxy+ayx=1.

If the factorxis more important than the factory,thenaxy= 1; if the factorxis as important as the factory,thenaxy= 0.5; if the factorxis less important than the factory,thenaxy=0.

We can calculate the weight according to the following formula.

3.1.2 Calculating attribute values of each factor

(i)Type

This section divides the target type into two standards.We ask the experts in the area of imaging observation to get the attribute values,which are shown in Table 2.

Table 2 Attribute values of target type

(ii)Imaging

Through national imagery interpretability rating scale(NIIRS), general image-quality equation (GIQE) and related research,we use the NIIRS level to indicate the priority of imaging. According to the above-mentioned factors,this section focuses on the influence of the sensor on the image quality.The other factors take the average level,and the calculation is carried out in the simplified form of GIQE,which was given in[26].The formula is as follows:

In (3), GSD indicates the ground sampling distance. If the image belongs to the synthetic aperture radar (SAR),thenc= 10.5; If the image belongs to the infrared,thenc= 9.82; if the image belongs to the visible light, thenc= 9.191 5. It should be noted that GSD is in inches. Since the resolution is usually converted in metric units, a corresponding conversion is required.According to (3), the NIIRS level of the 1 m resolution visible light image is about 4 levels,and the 0.03 m resolution visible light image can reach the highest level of 9. Finally, the calculation results retain two decimal places.

(iii)Airspace

The airspace factor considers two aspects. One is the area coverage.The value is a floating point type, and we can use(4)to calculate the attribute value.

T ar5indicates the imaging coverage requirement for the target.

The other factor is the geographical characteristic,whose value is an enumeration type. The attribute valuesvAttr3areaare shown in Table 3.

Table 3 Attribute values of geographical characteristic

We can calculate the airspace attribute values according to(5).

(iv)Time domain

The attribute values of the number of observationsvAttr4frepare shown in Table 4.

Table 4 Attribute values of number of observations

The attribute values of the maximum time intervalvAttr4itvare shown in Table 5.

Table 5 Attribute values of maximum time interval

We can calculate the attribute value of the time domain according to(6).

3.2 Imaging task priority model

This section establishes an imaging task priority evaluation indicator system,which is shown in Table 6.

Table 6 Imaging task priority evaluation indicator system

The imaging task priority is determined by the target priority,and it will derive the corresponding track,telemetry&control(TT&C)requirement priority.At the same time,there are special task groups such as periodic imaging tasks in the imaging observation system.Based on those characteristics,this section will use the technique for order preference by similarity to ideal solution(TOPSIS)method to establish an imaging task priority model.

Step 1 Quantify the attribute value of each factor in the evaluation index system.

(i)Target

The target attribute value is shown in(7).

(ii)Application scenarios

The application scenarios attribute values are shown in Table 7.

Table 7 Attribute values of application scenarios

(iii)User

The user attribute valuesrtAttr3are shown in Table 8.

Table 8 Attribute values of users

(iv)Application

The application attribute valuesrtAttr4are shown in Table 9.

Table 9 Attribute values of application

(v)Satellite working mode

The satellite working mode attribute valuesrtAttr5are shown in Table 10.

Table 10 Attribute values of satellite working mode

(vi)Type

The task type attribute valuesrtAttr6are shown in Table 11.

Table 11 Attribute values of task type

(vii)Satellite’s own properties

The satellite’s own properties attribute valuertAttr7are shown in Table 12.

Table 12 Attribute values of satellite’s own properties

(viii)Execution urgency

The formula for execution urgency is as follows:

ettaskindicates the deadline of the task, andttaskindicates the current moment.

Therefore, we can calculate the execution urgency attribute value according to(9).

Step 2 Construct the factor matrix.

The factor matrix of the imaging tasks is as follows:

xijindicates the jth factor attribute value in the ith imaging task.

Step 3 Standardize the factor matrix.

According to the method in Step 1, the above factor matrix is standardized,and the standardized matrix is obtained as follows:

where

Step 4 Calculate the negative ideal solution,the ideal solution,and the weight of each factor.

(i)We assume Y?= (0,0,...,0)as the negative ideal solution.

(ii)We assume Y+= (1,1,...,1)as the plus ideal solution.

(iii)Determine the weight of each factor.

Because the relative importance between the various factors is vague,it is difficult to obtain the objective results.Therefore,this paper uses the Delphi method to determine the weight.The specific steps are as follows.

(i) Invite the users and authorities of the satellite management to score the attribute indicators.

(ii)Analyze the scores of the importance of the various attribute indicators by experts, use statistical methods to process these scores, and send the results to the experts,then ask them to re-score and start statistical processing again.After several cycles,the opinions of the experts are relatively consistent.

(iii)Calculate the weight coefficient of each attribute of each expert opinion.

Step 5 Calculate the Euclidean distances between each imaging task and the ideal solution Y+or the negative ideal solution Y?.

The formula for calculating the Euclidean distance between each imaging task and the ideal solution is as follows:

The formula for calculating the Euclidean distance between each imaging task and the minus ideal solution is as follows:

According to the above formula, the relative closeness can be defined as follows:

Step 6 Calculate the priority of the imaging tasks.

We can calculate the priority of imaging tasks based on(16).

where

3.3 TT&C requirement priority model

This section establishes a TT&C requirement priority evaluation indicator system,as shown in Table 13.

Table 13 TT&C requirement priority evaluation indicator system

3.3.1 TT&C requirement priority model based on AHP and Delphi method

The impact of each factor in the TT&C requirement priority evaluation indicator system on priority is different.Therefore, each factor should be evaluated.We introduce the weight,which represents the impact degree of each fac-tor.Therefore,this paper establishes the calculation model for priority,which is shown in(19).

Ptt&cindicates the TT&C requirement priority,tt&cAttriindicates the attribute value of each factor, andωiindicates the weight of each factor.

3.3.2 Determining the weight

Since the imaging observation system is a relatively complex system,the managers pay a different attention to each factor. Therefore, in order to describe each factor objectively,and reduce the solution error in the evaluation process,this section uses the analytic hierarchy process(AHP)and the Delphi method to determine the weight.The specific steps are as follows.

Step 1 Extract the factors,and make sure that the factors are consistent with the actual system.

Step 2 Construct the judgment matrix.

We ask some experts to compare the factors based on the nine importance levels and construct their respective judgment matrices.aijindicates the relative importance of the factorxand the factory. The importance level is defined as follows in Table 14.

Table 14 Importance level

Step 3 Use the Delphi method.

In order to fully express the opinions of the experts,and get scientific results, the Delphi method is used to obtain the scores.Steps are as follows.

(i)List all the indicators at a certain level in the indicator set,and ask each expert to give a relative score value based on the nine importance levels.

(ii)Repeat the above process,and stop the scoring process when the following standards are reached.

i)The variance of the score value is less than its preset threshold;

ii) The variance of the adjacent two scores is less than its preset threshold;

iii)The total number of ratings is greater than its default threshold.

Step 4 Conduct the consistency test.

The above method of constructing the judgment matrix can reduce the interference of other factors,and objectively reflect the difference degree of the impact on factors.However,when all the comparison results are combined,it will inevitably contain a certain degree of inconsistency.Therefore,the consistency test of the judgment matrix is required as follows.

(i)Find the maximum eigenvalue,which corresponds to the judgment matrixA.

(ii) Calculate the consistency index CI, CI =

(iii)Look for the corresponding average random consistency indicator RI,as shown in Table 15.

Table 15 RI values

(iv)Calculate the consistency ratioCR,CR=CI/RI.IfCR <0.1, it is considered that the consistency of the judgment matrix is acceptable; otherwise it returns to(ii) to make appropriate corrections until the consistency requirement is met.

Step 4 Solve the weight vector.

(i) After the consistency check, the feature vectorWcorresponding to the maximum eigenvalueλmaxis calculated,and after normalization,the weights of all factors are sorted by each expert.

(ii) By averaging the elements of the corresponding items in all weight vectors,the final weights of each factor are obtained.

3.3.3 Calculating the attribute values

(i)Target

The definition of targe attribute values are shown in(20).

(ii)Control circle

The control circle attribute valuestt&cAttr2are shown in Table 16.

Table 16 Attribute values of control circle

(iii)Resource

The resource attribute valuestt&cAttr3are shown in Table 17.

Table 17 Attribute values of resource

(iv)Station

The station attribute valuestt&cAttr4are shown in Table 18.

Table 18 Attribute values of station

(v)Event

The event attribute valuestt&cAttr5are shown in Table 19.

Table 19 Attribute values of event

(vi)Flight stage

The flight stage attribute valuestt&cAttr6are shown in Table 20.

Table 20 Attribute values of flight stage

(vii)Health level of satellite

After the satellite design is completed, there are certain reliability parameters—the average interval of faults,usually expressed by MTBF.As the satellite’s normal operation time gets closer to MTBF,the likelihood of failure is increasing.Therefore,the health level of the satellite is defined as follows:

NWT indicates the normal operation time of the spacecraft.Therefore,the definition of health level attribute values is shown in(22).

(viii)Available resources

The resources attribute valuestt&cAttr8are shown in Table 21.

Table 21 Attribute values of available TT&C resources

(ix)Execution urgency

The formula for the execution urgency of TT&C is as follows:

ettt&cindicates the ending time,ttt&cindicates the current moment,anddurtt&cindicates the minimum duration required by the TT&C requirement.

Therefore, we can calculate the execution urgency attribute value according to(24).

3.4 Data transmission requirement priority model

This section establishes a data transmission requirement priority evaluation indicator system,which is shown in Table 22.

The impact of the factors in the data transmission re-quirement priority evaluation indicator system on priority is different.Therefore,each factor should be evaluated.We introduce the weight, which represents the impact degree of each factor.Therefore,this paper establishes the priority calculation model for priority,which is shown in(25).

Table 22 Data transmission requirement priority evaluation indicator system

Pdtrindicates the data transmission requirement priority,dtrAttriindicates attribute values of each factor,andωiindicates the weight of each factor.

3.4.1 Calculating the weight

We adopt the same method in Section 3 to calculate the weight.

3.4.2 Calculating the attribute values

(i)Source target

The source targe attribute valuesdtrAttr1are shown in(26).

(ii)Ways of data transmission

The ways of attribute valuesdtrAttr2are shown in Table 23.

Table 23 Attribute values of ways of data transmission

(iii)Receiving station

The receiving stations attribute valuesdtrAttr3are shown in Table 24.

Table 24 Attribute values of receiving stations

(iv)Type

The downstream data type attribute valuesdtrAttr4are shown in Table 25.

Table 25 Attribute values of downstream data type

(v)Number of available resources

The available resources attribute valuesdtrAttr5are shown in Table 26.

Table 26 Attribute values of number of available resources

(vi)Execution urgency

The execution urgency of data transmission requirement is as follows:

etdtrindicates the ending time of the data transmission requirement,tdtrindicates the current moment,anddurdtrindicates the minimum duration,which are required by the data transmission requirement.

Therefore, we can calculate the execution urgency attribute value according to(28).

4.Task priority algorithm for imaging observation

4.1 Priority dynamic scheduling strategy

Most scholars study the imaging tasks scheduling from the perspective of static priority,and only a few from the perspective of dynamic priority.In these algorithms,each task has only one fixed priority.In terms of priority,the emergency tasks are generally higher than the normal tasks. If the emergency tasks arrive temporarily, the normal tasks with a high execution urgency may not be executed and miss the deadline.Therefore,we must take these features into consideration to design the dynamic scheduling strategy.

4.1.1 RHO strategy

The basic idea of the rolling horizon optimization(RHO)strategy is to divide the scheduling process into a set of tasks with a certain degree of overlap, with the advancement of imaging tasks.Only those imaging tasks are scheduled,which are in the current rolling windows.The new tasks are continuously added, and the scheduled tasks are gradually deleted from the rolling window.The RHO strategy decomposes complex dynamic scheduling problems into multiple simple static scheduling problems,and it can reduce the difficulty of the original problem.

4.1.2 Rolling window

The rolling window is used to store the tasks,which are involved in the current scheduling progress.It includes two key elements: the type of the task and the number of tasks.In terms of quantity,the more tasks reach the rolling window,the more comprehensive the task information is,and the more processing time there will be.

4.1.3 Periodic triggering model

Priority is the constraint and important heuristic information in solving the problem of imaging task scheduling.It can reflect the importance of decision makers on indicators. Since the real-time scheduling of priority cannot be achieved in the actual project, we propose a reasonable triggering model based on the actual project situation.

(i)Fixed cycle mode

In Fig. 1, we can see that any other external condition does not change the priority,it only relates to the fixed cycle.Therefore,how to determine a reasonable cycle in this mode is an important topic.With the the cycle lengthTbecoming shorter,the imaging observation results get better.WhenT →0, the system is transformed into a real-time task scheduling system,which is an ideal state.

Fig.1 Fixed cycle mode

(ii)Dynamic changing mode

The priority changes dynamically with the rolling scheduling of emergency tasks. In the satellites scheduling system, measurement and control are the key to restricting the implementation of the new plan. Therefore,the scheduling period mainly depends on the measurement and control requirement. As shown in Fig. 2, the current planpk?1is injected at timet0as a contingency plan,and theKth rolling scheduling is started.At timet1,the tasks that are not successfully scheduled in the planpk?1enter into the current scheduling period.During this period,the new emergency tasks arrive.

Fig.2 Dynamic changing mode

4.2 Design of task priority algorithm

4.2.1 Algorithm framework

The algorithm framework as shown in Fig.3 includes two parts,basic functions and the execution flow as follows.

(i) In the first module, first, we calculate the task priority based on the task priority model,which is to be scheduled.If the condition of the priority rolling change is met,then we recalculate the task priority;otherwise the current task’s priority is temporarily stored.

(ii)In the second module,if the condition of task rolling rescheduling is met, then the solution algorithm is proposed to allocate resources and execution time windows for tasks,and form the corresponding scheduling scheme.For tasks that are not successfully scheduled,they will be scheduled with the new tasks into the next set of tasks.

Fig.3 Algorithm framework

4.2.2 Heuristic algorithm

(i)Optimization objective

In the heuristic algorithm,the imaging observation problem has two objectives. The first objective is the total revenue of the scheduled task, which is represented by fg(s). The second objective is satellite resource load balance,which is represented by fc(s).

where

etwiindicates the ending time instant of tasks.stwiindicates the starting time instant of tasks.

where

ntindicates the total number of tasks;nsatindicates the total number of satellites.

(ii)Solution process

Step 1 Initialize the imaging tasks, and determine the priority of each imaging task.

Step 2 Determine whether the imaging tasks will enter a new rolling scheduling window.If yes,we start the task rolling scheduling, and proceed to Step 3; otherwise, we wait for the new scheduling rolling window.

Step 3 Recalculate the priority of the imaging tasks.

Step 4 Sort the tasks priority in the descending order,and determine the scheduling order of each task.

Step 5 According to the scheduling order of tasks,the windows conflict degree strategy is proposed to assign the corresponding resources and execution time windows to each imaging task.

Step 5.1 Find out time windows.

Step 5.2 According to the result of Step 4, taskiis taken out,and calculate the time windows conflict of it.

Step 5.2.1 Arrange taskiinto one of the time windows,and determine the resource corresponding to this time window.

Step 5.2.2 According to the result of Step 4,take out all the tasks after taski, find out all the visible time window sets{T Wsj}on the resourceSj.

Step 5.2.3 Calculate the number of time windows in the set{T Wsj},which is in conflict with the time windowT Wk.

Step 5.2.4 Determine whether time windows of taskihave been traversed.If yes,go to Step 5.3;otherwise go to Step 5.2.1.

Step 5.3 According to the result of Step 5, assign the time window and corresponding resources to this task,which has the least conflicts.

Step 5.4 Adopt the same method as taskito schedule the remaining tasks.

Step 5.5 Determine whether all the scheduled tasks have been traversed. If they are traversed, go to Step 6;otherwise go to Step 5.2.

Step 6 Generate the plan.

5.Numerical experiments and performance analysis

5.1 Description of functions and parameters

5.1.1 Satellite design

We set all targets to the static point targets.We set all images to the visible light images, and the minimum ground resolution is required to be 1 m.

We set the satellites to AW satellites,all of which adopt sun-synchronous orbits.The orbital height is 800 km,and the intervals are equal.The six orbital planes are arranged uniformly.Each satellite is arranged on each surface.Each satellite is equipped with a visible light sensor.The maximum side swing angle is 45?,and the maximum pitch angle is 45?.The attitude conversion time is 10 s,not considering the power limit.The orbit parameters are shown in Table 27.

Table 27 Orbital parameters

5.1.2 Scenario design

(i) Verification scenes design of the priority model and dynamic schedling strategy

In an actual project, the scheduling period of the task is relatively long, which is usually a few days or a week.In this section, we design six scenes Sceneato Scenef,and there are 300 emergency tasks and 700 normal tasks in each scene. Here are some examples of imaging tasks,which are shown in Table 28.

Table 28 Examples of imaging tasks

(ii)Verification scenes design of the heuristic algorithm

In this section, we design five scenes Scenegto Scenek, and there are 100 emergency tasks in each scenario.The arrival rates are 15 per hour,30 per hour,60 per hour,90 per hour,120 per hour,respectively.The simulation period is set from 2014/07/01 00:00:00 to 2014/07/02 00:00:00.

5.1.3 Test task sets

In this section, we create the normal tasks library Nor Task and the emergency tasks library Emer Task.There are 4 000 normal tasks in library Nor Task, and 6 000 emergency tasks in library Emer Task.

5.2 Experimental results and analysis

5.2.1 Task priority model and dynamic scheduling strategy

Based on the scenes Sceneato Scenef, after 12 sets of experiments,the results are shown in Table 29.The meaning of each character is as follows.

DP: priority is dynamic

SP: priority is static

NTotal:number of normal tasks,which are to be scheduled

ETotal: number of emergency tasks, which are to be scheduled

Total: number of tasks,which are to be scheduled

SUM: number of completed tasks

NC init: number of completed normal tasks

EC init: number of completed emergency tasks

CR: completion rate of normal tasks

ER: completion rate of emergency tasks

In terms of the number of the completed tasks,the emergency tasks are more than the normal tasks, whether it is the dynamic priority strategy or the static priority strategy.Fig.4 shows that the normal tasks are much lower than the emergency tasks in terms of the completion rate. The results are generated based on the descending heuristic rules.The task priority model designed by this article can be effective, which can make sure that most of the emergency tasks have a higher priority than the normal tasks, and it is reasonable to ensure that not all emergency tasks have a higher priority than normal tasks,which is consistent with the actual project.

In addition,Table 29 shows that compared with the static priority model,the total number of the completed tasks has been increased by adopting the dynamic priority strategy.

Fig.4 Scheduling rate of tasks

All the improvements are emergency tasks. The maximum improvement is 21, and the minimum improvement is 2. Therefore, the dynamic scheduling strategy is effective.

5.2.2 Task scheduling algorithm

The meaning of each character is as follows.

Velo: arrival rate

NT: total number of completed tasks

CR: completion rate of tasks

Time: the heuristic algorithm runtime

In Table 30,we can see that the completed rate of tasks in each scenario is relatively high, which is above 70%.When the arrival rate is up to 120 per hour, the completion rate can exceed 80%.In addition,although the scale of the emergency task increases, the heuristic algorithm can schedule tasks in a short time.

Table 30 Results of Scene g to Scene k

The optimal objective must be taken into account. The results are shown in Table 31.

Table 31 Optimal objectives

6.Conclusions

In summary,the following conclusions can be drawn.First,the task priority model in Section 3 is reasonable and effective.Second,the priority dynamic changing strategy based on the rolling window in Section 4 is effective. The application of this strategy can improve the completion rate.Finally,from the running time and target value of the algorithm, the algorithm in Section 4 is reasonable and effective. As the frequency of emergency tasks increases, the advantages of the algorithm become more apparent.