本发明属于卫星任务规划调度领域，尤其涉及一种面向动态到达任务的在线调度方法。
背景技术：
近年来，中国航天事业进入快速发展阶段，在我国政府大力推动、科研单位苦心钻研下，在轨卫星数量每年均在迅速增加。卫星在轨运行过程中需要使用地面测控设备对卫星飞行状态、系统运行状态等卫星运行情况进行跟踪和监视，利用测控设备为卫星上注新的航天任务。受到地面测控设备能力，卫星能力，太空环境限制，测控设备所能完成的测控任务是有限的。卫星在轨数量增多随之而来的是完成测控任务更大的难度。充分发挥地面测控站和卫星效能，提升卫星系统运行效率有着迫切的实际需求。
随着国际局势趋于复杂，各种类型的应急任务请求时有发生，相应地，应急测控请求也经常由各类卫星用户提出。应急测控请求在卫星调度中意味着新的测控任务产生，需要完成新测控任务的调度。为了保证新测控任务请求的完成需要对原有任务执行方案进行调整，通过调整保证新的测控请求顺利加入到任务执行方案中，顺利执行新测控请求。对原测控任务执行方案调整会导致原有的部分测控任务由于违反约束条件而被迫从原方案中删除，如果没有合适的调度策略，很容易导致大量的测控任务被删除，也就是说为了完成新测控任务需要付出很大的代价。大幅度的任务方案调整可能会导致很多原有任务无法顺利完成，这是卫星管控单位和用户无法接受的结果。通过较少的方案调整做到既满足新测控任务的同时也很少出现任务被删除取消才是应急常态化趋势下发展我国航天测控领域的必要途径。
在现有卫星管控模式下，卫星管控部门采用按照一定时间范围周期性生成测控任务执行方案，当收到新的测控任务请求时，将新的任务在收集汇总到一定数量后临时性的将新测控任务加入到原任务序列中并重新生成规划方案。这种任务处理方式在很多情况无法直接得到新任务执行方案，需要经过大量的人工调整，约束检查才可以得到最终方案。这种新任务调整方法，由于缺少缺乏自动化处理流程，需要消耗调度人员大量精力反复调整任务执行方案，调整流程复杂，存在众多的人机交互操作，极易出现错误操作。随着任务不确定性程度增加，应急任务数量增多，地面卫星管控将面临大量的调度方案调整压力。这种规划方案调整方式一方面难以满足方案中存在多个新到达的任务同时调整要求，一个任务的推后执行可能导致该任务之后的大量任务与资源需要进行重新匹配，人工分析调整已不具有可行性；另一方面，调整可能导致现有任务的大幅度改动，这种规划方案难以满足管控方和用户需求，造成大量的卫星资源浪费。此外，这种调整方法难以保证规划方案的质量。现有卫星管控模式反映出了与卫星应用需求之间的差距，需要设计无需大量任务调整，同时处理多个新任务需求的测控调度方法。
应急测控需求不但作为新测控请求在方案调整上存在很大的难度，同时还有很强的快速响应，短时间内完成的要求。只有做到新测控任务请求快速响应，将任务请求转化为调度所需要的数据信息，利用调度算法得到新的任务执行方案。响应和处理的时效性要求为我国下一代测控系统建设提出了很高的目标，需要根据我国测控系统运行模式进行优化调整，提出适应应急常态化、处理高效化的新型调度框架，做到新测控任务需求实时产生和到达测控系统、及时调度，得到合适的新测控任务执行方案。对于我国下一代测控系统，还有保证不确定性任务调度效率的同时兼顾调度方案质量的更高要求。如何在保证对于应急任务快速响应的同时保证对原有计划方案尽可能小的影响并兼顾规划方案的效果，充分发挥卫星和地面站的效能，是我国航天领域亟待解决的问题。
技术实现要素：
本发明要解决的技术问题是：对于动态到达的应急任务怎样在对原执行方案影响较小的情况下，快速处理新测控任务，提出了一种面向动态到达任务的在线调度方法。
为解决该问题，本发明所采用的技术方案是：
一种面向动态到达任务的在线调度方法，包括以下步骤：
步骤1：在系统运行时间范围内，将系统运行过程分为多个运行阶段，在每一个运行阶段中有系统执行的任务序列，相邻运行阶段之间不存在交叉的任务；
步骤2：将所述每个运行阶段分为稳定运行阶段和决策调度阶段，在所述稳定运行阶段，系统执行上一运行阶段中决策调度阶段决策的任务序列，在所述决策调度阶段，将在当前运行阶段处于稳定运行阶段中系统收集到的新测控任务请求，插入到下一稳定运行阶段的原任务序列中形成新任务序列，并对新任务序列进行在线调度；
步骤3：在下一稳定运行阶段执行调整后的所述新任务序列，完成动态到达任务的在线调度。
进一步地，所述决策调度阶段包括预调度阶段和调度阶段，在所述预调度阶段对前一个稳定运行阶段中收集到的新测控任务请求进行预处理，在所述调度阶段，将经过预调度的新测控任务插入到下一稳定运行阶段的任务序列中形成新的任务序列，并对新任务序列进行调整。
进一步地，所述将经过预调度的新测控任务插入到下一稳定运行阶段的任务序列中形成新的任务序列的方法是快速插入方法。
进一步地，所述快速插入方法是：
步骤2.1：在所述运行阶段时间范围内，判断新测控任务是否可以插入到下一稳定运行阶段的任务序列中，如果可以直接插入则将新测控任务插入到原任务序列中形成新的任务序列后输出；
步骤2.2：如果不能直接插入，则将任务序列中所有持续时间短于新测控任务的任务，按照持续时间长短从小到大进行排列，依次累加直至多个任务持续时间和超过新测控任务的持续时间，将此时累加的多个任务的重要性程度求和，并将多个任务的重要性程度求和结果作为所述新测控任务的最小重要程度和；
步骤2.3：比较新测控任务的最小重要程度和与超过新测控任务持续时间的最短原任务重要性程度，选择值较小的作为被替换任务，将被替换的任务放入被删除的任务集合；
如果被替换的任务为超过新任务持续时间的最短原任务，则转步骤2.4；
如果被替换的任务为计算新测控任务的最小重要程度和的多个任务，则转步骤2.5；
步骤2.4：将新测控任务的开始时间设定为超过新测控任务持续时间的最短原任务的开始时间；
步骤2.5：将多个任务中处在最前位置的任务开始时间作为新测控任务的开始时间，按照满足最小间隔时间要求顺序移动序列内排在新测控任务之后的原有任务。
进一步地，步骤2中对新任务序列进行在线调度的方法是邻域搜索方法。
进一步地，所述邻域搜索方法为：
1)邻域搜索算法待优化的任务集合包括两部分，一部分是从任务序列中删除被替换的任务构成需要修复的任务集合
2)依次将待修复集合
3)在完成将待修复集合
进一步地，相邻运行阶段之间设置触发条件，满足触发条件时卫星测控系统将从一个运行阶段转入另一个运行阶段。
进一步地，本发明还提供了一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述在线调度方法的步骤。
进一步地，本发明还提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述在线调度方法所述的步骤。
与现有技术相比，本发明所取得的有益效果是：
本发明一种面向动态到达任务的在线调度方法，通过将测控调度系统的运行阶段进行划分，在每一个运行阶段中明确系统执行的工作，阶段与阶段之间不存在交叉的情况，为阶段之间的转换设置触发条件，满足触发条件时卫星测控系统将从一个运行阶段转入另一个运行阶段。由于在每一个运行阶段都有要执行的任务序列，也有调度阶段，对下一阶段进行调度，由于新的测控任务请求在系统运行的任何时刻均有可能发生，而在线调度过程只能在上一阶段测控任务计划已经完成而下一阶段测控任务计划尚未开始前完成。系统运行过程中同样需要设置预调度阶段，在预调度阶段只将收集到的新测控任务请求预处理而不进行调度和方案调整。在全部新测控任务请求处理完成后开始进入调度阶段，调度阶段使用在线调度算法完成新任务插入和任务序列调整。本发明一种系统稳定运行阶段与决策阶段交替运行的在线运行策略，在决策阶段触发在线调度过程，通过任务快速插入与邻域搜索算法使得任务能尽可能的插入到任务序列中，任务快速插入设计了直接插入和替换插入策略。本发明通过充分的实验证明了本方法针对任务动态到达的卫星测控在线调度问题而提出的算法具有很好的任务快速处理和序列优化效果，可以有效满足实际在线测控调度的使用需要，并且对原执行方案影响较小。
附图说明
图1为卫星测控系统的在线运行策略；
图2为本发明系统流程图；
图3直接插入示意图；
图4比较最小重要程度和与最短原任务重要性程度，取值较小的进行替换示意图；
图5为任务序列修复过程示意图；
图6为200个原任务实验场景下不同新任务数量的实验结果示意图；
图7为300个原任务实验场景下不同新任务数量的实验结果示意图。
具体实施方式
卫星测控系统按照由鲁棒性调度算法调度后的测控任务执行方案执行卫星测控任务。通过鲁棒性调度算法可以对可以预知的测控任务进行有针对性的改进方案。这种前瞻策略只能应对有规律可循的新任务。测控系统在实际运行过程中存在不可预知的新测控任务到达的可能。新测控任务一般是由于某些突发性事件而产生的应急任务。这些新的测控任务请求往往是难以提前预知的，不适应通过前瞻策略进行解决。应对这类新到达的测控任务请求，测控调度系统需要设置合理的短视策略(short-sightedstrategy)，即设置任务在线调度的触发机制，在不影响测控任务计划按时执行的前提下短时间内快速处理新任务请求。在线调度过程首先通过调度算法将新测控任务加入到原任务序列中，但是由于原任务序列中已经存在任务，可能存在新加入任务违反约束条件的情况。通过调度算法对任务序列的调整，优化任务执行位置达到在线调度的预期效果。新测控任务动态到达的在线调度问题需要提出在系统在线运行策略和调度算法。
下面通过一个实施例来说明本发明一种面向动态到达任务的在线调度方法，包括以下步骤：
步骤1：在系统运行时间范围内，将系统运行过程分为多个运行阶段，在每一个运行阶段中有系统执行的任务序列，相邻运行阶段之间不存在交叉的任务；本实施例中，相邻运行阶段之间设置触发条件，满足触发条件时卫星测控系统将从一个运行阶段转入另一个运行阶段。触发条件根据地面时间窗的分布来决定。本实施例中以存在空闲时触发。
本实施例通过将测控调度系统的运行阶段进行划分，在每一个运行阶段中明确系统执行的工作，阶段与阶段之间不存在交叉的情况，为阶段之间的转换设置触发条件，满足触发条件时卫星测控系统将从一个运行阶段转入另一个运行阶段。由于在每一个运行阶段都有要执行的任务序列，也有调度阶段，对下一阶段进行调度，由于新的测控任务请求在系统运行的任何时刻均有可能发生，而在线调度过程只能在上一阶段测控任务计划已经完成而下一阶段测控任务计划尚未开始前完成。系统运行过程中同样需要设置预调度阶段，在预调度阶段只将收集到的新测控任务请求预处理而不进行调度和方案调整。在全部新测控任务请求处理完成后开始进入调度阶段，调度阶段使用在线调度算法完成新任务插入和任务序列调整。
步骤2：将所述每个运行阶段分为稳定运行阶段和决策调度阶段，在所述稳定运行阶段，系统执行上一运行阶段中决策调度阶段决策的任务序列，在所述决策调度阶段，将在当前运行阶段处于稳定运行阶段中系统收集到的新测控任务请求，插入到下一稳定运行阶段的原任务序列中形成新任务序列，并对新任务序列进行调整；
本实施例中，所述决策调度阶段包括预调度阶段和调度阶段，在所述预调度阶段对前一个稳定运行阶段中系统收集到的新测控任务请求预处理，在所述调度阶段，将经过预处理的新测控任务插入到下一稳定运行阶段的任务序列中形成新的任务序列，并对新任务序列进行调整。对于任务调度来说，调度算法设计主要考虑两个内容，一个是新任务的加入方式，另一个是新任务序列中任务位置的调整。新任务加入体现了调度算法对新测控任务请求的响应，满足测控应急常态化需求。任务位置调整体现了调度算法对新生成的任务序列的调整与优化，在满足约束条件的基础上得到好的任务执行方案。
如图1所示，每一个小圆点表示新任务到达卫星测控调度系统，此时调度系统并不会立刻触发在线调度，而是当系统稳定运行阶段结束时触发在线调度。在线调度包括预调度阶段和调度阶段，共同构成了决策阶段。在系统稳定运行阶段，测控系统将根据上一个决策阶段生成的新任务执行方案执行该阶段的测控任务，系统稳定运行时将收集来自用户提出的新测控任务请求，但是这些任务在当前阶段将暂不进行预调度，这是由于系统在当前稳定运行阶段受到系统处理速度、指令生成速度的限制已经无法插入到任务序列中完成，最多只能保证任务在下一个稳定运行阶段中执行。系统稳定运行阶段是卫星测控系统执行新生成测控任务序列，保证新任务顺利完成的重要阶段，直至进入决策阶段系统才开始任务预调度和任务调度。
本实施例中，将新测控任务插入到下一稳定运行阶段的任务序列中的方法是快速插入法。将新的测控任务插入原任务序列中体现了算法对于新任务的快速响应和处理。如图2所示，给出了任务快速插入以及邻域搜索的具体流程图，快速插入的具体步骤是：
步骤2.1：在所述运行阶段时间范围内，判断新测控任务是否可以插入到下一稳定运行阶段的任务序列中，如果可以直接插入而不删除其他任务的位置，则将新测控任务插入到原任务序列中形成新的任务序列后输出，如果存在多个可以插入的位置，则将任务插入到第一个可以执行任务的位置；
如图3所示，图中方块长度表示任务持续时间，序号为1的新任务具有三个可以选择插入的位置，根据步骤2.1，选择序号为①的空闲时间窗将任务插入，其他两个可以使用的时间窗位置依然保持空闲可用状态，允许其他新任务插入。
步骤2.2：如果不能直接插入，则将任务序列中所有持续时间短于新测控任务的任务，按照持续时间长短从小到大进行排列，依次累加直至多个任务持续时间和超过新测控任务的持续时间，将此时累加的多个任务的重要性程度求和，并将多个任务的重要性程度求和结果作为所述新测控任务的最小重要程度和；
步骤2.3：比较新测控任务的最小重要程度和与超过新测控任务持续时间的最短原任务重要性程度，选择值较小的作为被替换任务，将被替换的任务放入被删除的任务集合；
如果被替换的任务为超过新任务持续时间的最短原任务，则转步骤2.4；
如果被替换的任务为计算新测控任务的最小重要程度和的多个任务，则转步骤2.5；
如图4所示，图中每一个方块表示一个测控任务，第一个数字表示任务的持续时间，括号内的数字表示任务的重要性程度。假设新任务的持续时间为12，使用最小重要程度和计算方法得到的替换任务集合，图中用白色方块表示。这两个任务的持续时间为7 9＝16，重要性程度和为8 7＝15。序列中满足各项条件的超过新任务持续时间的最短原任务持续时间为13，重要性程度为9，图中用黑色方块表示。根据启发式规则2，由于9<15，因此删除超过新任务持续时间的任务持续时间为13的原任务。
步骤2.4：将新测控任务的开始时间设定为超过新任务持续时间的最短原任务的开始时间；
步骤2.5：将多个任务中处在最前位置的任务开始时间作为新测控任务的开始时间，按照满足最小间隔时间要求顺序移动序列内排在新测控任务之后的原有任务。
由于新任务和原任务序列中的任务存在任务执行相互交叉，违反约束条件的情况，因此需要对序列中的其他任务进行顺序移动，满足最小时间间隔要求即可，保证执行方案的可行性。
本实施例中，快速插入算法设计的核心思想是通过简单的规则，检查新任务插入情况，快速完成任务插入和原序列任务删除，使得算法完成插入过程所耗用的时间尽可能短，为后续的修复和搜索优化算法预留充足的运行时间，满足时间限制的基础上提升算法的优化表现。任务快速插入算法同时考虑了新测控任务可以直接插入任务序列的情况和无法直接插入任务序列的两种情况，如果具有足够的时间窗资源可以直接供新任务使用，则比较容易即可完成新任务的加入，如果无法直接插入任务则需要使用多种判断条件将原任务序列中的部分任务从序列中删除，为新测控任务提供足够的时间窗资源。如果在任务插入过程中存在原序列中任务被删除的情况，则需要进入邻域搜索算法部分，通过邻域搜索进一步优化任务序列；如果没有被删除的任务则直接将当前任务执行方案输出作为下一测控调度系统稳定运行阶段的任务执行方案。
在将新测控任务插入到原任务序列后，需要将由于新测控任务插入而被删除任务重新加入任务序列并且搜索被删除任务可以执行的位置，得到新的任务执行方案，本实施例中，对任务序列进行调整的方法是邻域搜索算法。
邻域搜索算法主要完成将被删除任务重新加入任务序列和搜索被删除任务可以执行的位置，得到新的任务执行方案，包括修复过程和邻域搜索过程两部分，将被删除任务重新加入的过程也可以称为修复过程。修复过程将包含新测控任务的任务序列和被删除的任务序列构成一个全新的任务序列，并在得到的新任务序列中完成后续的搜索优化。
邻域搜索的具体过程为：
1)邻域搜索算法待优化的任务集合包括两部分，一部分是从任务序列中删除被替换的任务构成需要修复的任务集合
以一段任务序列为例，修复过程如图5所示，图中黑色方块的5、6表示需要修复的任务，1、2、3、4表示使用插入算法后得到的任务序列。通过修复过程，将蓝色方块的5与6放在序列的最前位置，即编号为1任务的前侧位置。
2)依次将待修复集合
本实施例中，目标函数：
g表示决策阶段数量，f(x,y)表示每一阶段优化的目标函数
由于系统运行过程中多个决策阶段之间是相互独立的，所以目标函数1可以转化为优化每一个决策阶段的目标函数，具体如公式2至4所示。
其中，n表示地面站时间窗数量，m'g表示新任务的数量，mg 1表示原任务的数量，pi'表示新任务重要性程度，pi表示原任务重要性程度。xij和xi'j为决策变量，用于表示任务是否执行，当xij,xi'j＝1时表示任务被执行，否则xij,xi'j＝0。y为辅助决策变量，用于表示新任务是否全部完成，当新任务全部完成时，y＝1，否则y＝0。
约束条件
新任务开始时间需要与任意原任务的结束时间满足转换时间要求；
新任务结束时间需要与任意原任务的开始时间满足转换时间要求；
其中，si表示任务i的开始时间，由规划调度算法确定任务具体的开始时间，di表示任务i的持续时间，由用户所提出的任务请求确定，测控任务需要达到该时间长度；t＝{t1,t2,...,tm}，表示原任务集合。i'表示新任务开始时间、
3)在完成将待修复集合
步骤3：在下一稳定运行阶段执行调整后的所述新任务序列，完成动态到达任务的在线调度。
邻域搜索主要是为了减少新任务执行方案中原有任务的改动量，尽可能做到原有任务可以正常执行，降低原任务序列由于新测控任务所导致的损失，起到优化目标函数的效果。
本发明使用任务快速插入和邻域搜索算法，既保证了新到达系统的测控任务请求可以顺利完成，又可以将新任务插入序列对原序列中任务的影响降低。优先确保新任务顺利执行是由于新任务的重要性程度相比其他任务而言更高，一旦任意一个新任务未能顺利执行则意味着对于新任务处理的失败。邻域搜索改变序列已有的邻域结构，通过生成新的邻域结构搜索更优的任务执行方案。
本发明由于重点考虑面向新测控任务到达的在线调度问题，需要排除外界因素对系统运行的影响，将重点放在在线调度问题上，因此本发明的在线调度做了以下假设：
1)卫星测控系统在0时刻处在即将执行任务计划的状态，该系统稳定运行阶段的任务为预先已知的，不需要调整；
2)卫星系统阶段是已经提前确定的，任务执行方案在系统正式运行前已经确定且不会发生再改变；
3)卫星测控调度系统在用户提出请求后可以迅速获取相关信息，不考虑卫星测控调度系统收到新任务信息延迟的情况；
4)已有的卫星测控任务执行方案中任务不存在变更任务请求，如变更任务完成期限、临时取消任务的情况；
5)卫星测控设备对新测控任务与原有测控任务的各类执行要求保持一致，即需要同样满足任务、设备等各方面的约束条件；
6)新任务在到达系统前属性未知，当到达系统后任务属性确定且不再发生变化；
7)系统对新任务进行调度的过程中，如果存在决策阶段中调度过程所属时间范围内到达的新任务不在当前决策阶段处理，而是并入下一个决策阶段统一处理；
8)调度算法生成新的任务执行方案后可以顺利转化为任务指令，将每次从任务到指令生成的时间假定为一个确定值。
下面通过实验验证本发明所提方法的有效性。
本发明选择了两种对比算法，一种为最小后悔值算法(minimumregretvaluealgorithm，mrva)，另一种为贪婪搜索算法(greedysearchalgorithm,gsa)。两种对比算法均为在线调度问题研究中常用算法。最小后悔值算法是一种基于让未完成任务所造成损失最小思路而产生的搜索算法，每一个任务根据重要性程度和持续时间分别给定一个后悔值，当该任务未能成功执行，该后悔值将产生影响，优化目标则转为使得任务序列所造成的总后悔值尽可能的小，通过优化转化后的目标得到最后的方案，得到最终的目标函数值。贪婪搜索算法基于贪婪地思想每次从任务序列中选中两个位置的测控任务，将这两个位置的测控任务在任务序列中相互对调位置。在完成任务位置对调后计算新任务序列优化的目标函数值并与当前最优目标函数值进行比较，如果新任务序列的目标函数值超过当前最优目标函数值则将当前目标函数值替换最优函数值，根据新的任务序列得到的任务执行方案作为最优任务执行方案。如果新任务序列的目标函数值小于当前最优目标函数值则将任务序列还原到任务位置对调前的状态。
实验以一天，即0到86400秒作为在线调度的时间范围，选择一天作为实验时间范围可以看出所提出方法对多个稳定运行和决策阶段的场景适应性，如果只是单一决策阶段并不能完整反映算法效果。一般来说，以一天为单位作为时间范围较为合适，一周的计划是以天为单位构成，通过有效编排每日测控任务计划可以得到一个合适的周计划方案。在一天的范围内，将一天划分为6个系统稳定运行阶段和5个系统决策阶段，平均每个阶段在两个小时左右，具体时间因任务密集程度而有所差异。
为了验证在线调度方法的可行性，需要设定合理的实验场景。本实验选择采用原有200、300个任务经过调度方法优化后的的两个实验场景作为在线调度的初始场景。在100个原任务的实验场景中，分别设置每一个决策阶段需要处理2、3、4、5个不同数量的新任务，共需要处理10、15、20、25个新任务，每一种数量下包含10个具有不同属性的算例。在200个原任务的实验场景种，分别设置每一个决策阶段需要处理7、8、9、10个不同数量的新任务，共需要处理35、40、45、50个新任务，同样的，每一种数量下分别生成了10种不同属性的算例。
动态到达系统的新任务在每一个系统稳定运行阶段产生，需要在下一个决策阶段执行方案调整，并限制在下一个系统稳定运行阶段执行任务。如表1所示，表中展示了5个新到达系统的任务的相关属性。
表1动态到达的任务示例
如表1所示，动态到达的任务包括
在算法执行的搜索次数方面，任务应急插入算法由于不存在对任务序列的遍历、搜索、比较，无需设定算法的搜索次数。对于本发明提出的任务快速插入与邻域搜索算法和贪婪搜索算法、最小后悔值算法为了保证算法测试的公平性，任务快速插入算法的搜索次数作为贪婪搜索算法从第一次成功执行全部新任务的方案开始后的算法搜索次数。
实验部分主要验证在线调度算法在调度时间和优化效果方面的表现。首先，对本文提出的快速插入与邻域搜索ti ns算法，与最小后悔值算法mrva和贪婪搜索算法gsa在200个任务场景下进行算法运行时间对比，实验对每一个决策阶段进行比较和分析，在每一个决策阶段中需要处理的新任务数量分为2、3、4、5四类，每一阶段中的任意任务数量均包含有10个随机生成的算例。考虑到仿真实验环境处于一种理想环境，与实际情况存在一定偏差，算法实际使用中可能受到各类因素的影响，本文将运行时间的10倍作为实际算法运行所用时间。对于同一场景下具有相等任务数量的不同算例，分别记录算法运行的最短时间(min),平均时间(mean)和标准差(std)。100个原任务场景下算法运行结果如表2所示。
表2200个原任务场景下算法运行结果
单位：秒(s)
从表2可以看出，在200个任务场景下，ti ns相比于mrva和gsa可以在更短的时间内完成在线调度，在最短时间、平均时间和标准差三个方面均有着很好的表现。进一步分析可以发现，本发明提出的算法对相同任务数量情况下不同决策点的处理时间较为接近，反映出本发明方法在不同的运行阶段有着相近的处理速度，受决策点的影响较小。当每一个决策阶段新到达任务数量为2时，5个决策阶段中的4个阶段所得到的最短时间均为3.28s，这是由于当新任务数量较少时可以通过很少的插入和搜索操作即可完成在线调度。此外，本发明方法在不同算例搜索优化过程中所用的时间波动性较小，算法较为稳定。将原任务数量增加到200后验证算法运行时间，结果如表3所示。
表3300个原任务场景下算法运行结果
单位：秒(s)
从表3可以看出，当原任务数量为300时，ti ns相比于mrva和gsa两种对比算法的运行时间优势更加明显。这是由于当原任务数量增多后，任务密度增大，给新任务的加入造成了一定的困难，只有高效搜索才可以缩短调度所用的时间，明显的时间优势证明了ti ns中插入和搜索策略的有效性。相比于每一个阶段2-5个新任务，7-10个任务对算法运行时间的影响更大，算法需要执行更多次数的搜索优化过程，消耗了更多的时间。分析在不同任务场景不同任务规模下的算法综合表现，本发明对每一个任务数量下的不同决策阶段以平均的形式表示，结果如表4所示。
表4200、300个原任务场景下不同任务规模算法运行结果
单位：秒(s)
从表4中可以看出，原任务数量为200个的实验场景的算法运行时间整体要长于原任务数量为100个的实验场景算法运行时间。在每一种实验场景中，随着新任务数量的增加，算法的最短时间与平均时间相应增加。无论是原任务数量增加还是新任务数量的增加，本发明提出的ti ns算法相比于两种对比算法而言具有更强的运算时间优势，ti ns算法可以更好地应用于较大规模的调度场景。综上所述，本文提出的ti ns算法在运算时间上相比于对比算法有着更好的表现。
在完成运行时间的实验和分析后，验证本发明方法在目标函数优化中的表现。为了直观验证目标函数优化效果，对200个原任务实验场景下不同新任务数量的实验结果以带均值标准差的折线图表示，该折线图可以同时在一张图中表示算法运行的平均效果，波动情况等信息。200个原任务实验场景下不同新任务数量的实验结果如图5所示。图(1)-(4)分别表示新任务数量分别为10、15、20、25的实验结果。
从图6中可以看出，当新任务数量为10、15、20、25个时，本发明提出的ti ns算法从算法平均表现和算法波动性两个方面均优于两种对比算法。在图5-(1)中，在决策阶段1、2中出现了算法优化后目标函数值低于1的情况，即由于执行新任务对原任务序列有着很大程度的调整，这是由于新任务数量较少，确定执行时间等各方面有着严苛的要求，导致了原任务序列中多个任务未能顺利执行，造成了一定程度的任务重要性程度损失。当新任务的数量增加后，新任务重要性程度和在任务序列中的比重增加，原任务序列中未能执行的任务所造成的影响程度降低。考虑调度算法在更多新任务、更大规模实验场景中的表现，将新任务数量增加到35-50个，原任务序列包含300个任务，实验结果如图6所示。图(1)-(4)分别表示新任务数量为35、40、45、50个的情况。
从图7中可以看出，相比于200个原任务序列的实验场景，在300个原任务实验场景中ti ns算法可以得到更优的目标函数值，获得更好的优化效果。在300个任务的实验场景中，ti ns算法与其他两种对比算法之间的差距更为明显，mrva算法在收益平均值和稳定性上表现最差。决策阶段5的三种算法波动性均较小是因为，决策阶段5接近于一天的结束，该阶段后的系统运行阶段原需要执行的任务数量较小，不同算法通过搜索优化均可以得到较好的优化效果。
综合以上实验结果可以看出，本发明提出的ti ns算法可以很好地应用于面向任务动态到达的在线调度问题，无论是在时间上还是优化目标上均有着相比于对比算法可以得到更好的优化效果，并且当新任务序列或者原任务序列中任务数量较多时可以得到更为理想的结果，并且对原执行方案影响较小。
本发明还提供了一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述在线调度方法的步骤。
本发明还提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述在线调度方法所述的步骤。
以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。
1.一种面向动态到达任务的在线调度方法，其特征在于，包括以下步骤：
步骤1：在系统运行时间范围内，将系统运行过程分为多个运行阶段，在每一个运行阶段中有系统执行的任务序列，相邻运行阶段之间不存在交叉的任务；
步骤2：将所述每个运行阶段分为稳定运行阶段和决策调度阶段，在所述稳定运行阶段，系统执行上一运行阶段中决策调度阶段决策的任务序列，在所述决策调度阶段，将在当前运行阶段处于稳定运行阶段中系统收集到的新测控任务请求，插入到下一稳定运行阶段的原任务序列中形成新任务序列，并对新任务序列进行调整；
步骤3：在下一稳定运行阶段执行调整后的所述新任务序列，完成动态到达任务的在线调度。
2.根据权利要求1所述的方法，其特征在于，所述决策调度阶段包括预调度阶段和调度阶段，在所述预调度阶段对前一个稳定运行阶段中系统收集到的新测控任务请求进行预处理，在所述调度阶段，将经过预处理的新测控任务插入到下一稳定运行阶段的任务序列中形成新的任务序列，并对新任务序列进行调整。
3.根据权利要求2所述的方法，其特征在于，所述将经过预处理的新测控任务插入到下一稳定运行阶段的任务序列中形成新的任务序列的方法是快速插入方法。
4.根据权利要求3所述的方法，其特征在于，所述快速插入方法是：
步骤2.1：在所述运行阶段时间范围内，判断新测控任务是否可以插入到下一稳定运行阶段的任务序列中，如果可以直接插入则将新测控任务插入到原任务序列中形成新的任务序列后输出；
步骤2.2：如果不能直接插入，则将任务序列中所有持续时间短于新测控任务的任务，按照持续时间长短从小到大进行排列，依次累加直至多个任务持续时间和超过新测控任务的持续时间，将此时累加的多个任务的重要性程度求和，并将多个任务的重要性程度求和结果作为所述新测控任务的最小重要程度和；
步骤2.3：比较新测控任务的最小重要程度和与超过新测控任务持续时间的最短原任务重要性程度，选择值较小的作为被替换任务，将被替换的任务放入被删除的任务集合；
如果被替换的任务为超过新任务持续时间的最短原任务，则转步骤2.4；
如果被替换的任务为计算新测控任务的最小重要程度和的多个任务，则转步骤2.5；
步骤2.4：将新测控任务的开始时间设定为超过新任务持续时间的最短原任务的开始时间；
步骤2.5：将多个任务中处在最前位置的任务开始时间作为新测控任务的开始时间，按照满足最小间隔时间要求顺序移动序列内排在新测控任务之后的原有任务。
5.根据权利要求2所述的方法，其特征在于，步骤2中对新任务序列进行调整的方法是邻域搜索方法。
6.根据权利要求5所述的方法，其特征在于，所述邻域搜索方法为：
1)邻域搜索算法待优化的任务集合包括两部分，一部分是从任务序列中删除被替换的任务构成需要修复的任务集合
2)依次将待修复集合
3)在完成将待修复集合
7.根据权利要求4所述的方法，其特征在于：步骤2.1中，如果存在多个可以插入的位置，则将任务插入到第一个可以执行任务的位置。
8.根据权利要求1-7中任一项所述的方法，其特征在于，相邻运行阶段之间设置触发条件，满足触发条件时卫星测控系统将从一个运行阶段转入另一个运行阶段。
9.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至8中任一项所述方法的步骤。
10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至8中任一项所述的方法的步骤。
技术总结