一种任务调度优化模型的优化约束确定方法

摘要

本发明公开了一种任务调度优化模型的优化约束确定方法，包括设备转场约束、剩余观测次数约束、测站进出约束的确定。针对特殊的地面车载测量设备对空间目标观测任务调度问题的最优化模型，确定优化约束，以保证观测方案的可行。

权利要求

1.一种地面车载测量设备对空间目标观测的任务调度优化模型的优化约束确定方法，其特征在于，包括设备转场约束、剩余观测次数约束、测站进出约束的确定；

所述设备转场约束是指观测任务的编排应该将设备的机动时间、展开时间、收拢时间、冷却时间纳入考虑，确保每一设备能够在给定的时间内完成所有必须的动作；

所述设备转场约束的计算步骤包括：

①针对给定的观测方案，梳理出所有涉及到的设备及每一台设备需要实施观测的窗口集合；

②针对方案中的第i台设备，对其需要实施观测的窗口集合中的元素按照时间先后进行排序；

③设排序后第i台设备需要实施观测的窗口集合可表示为 且每个窗口Wi,j,k,q的时间前沿和后沿分别为 则设备转场约束的计算方法为

1)设备由初始位置转场至第1个窗口对应测站实施观测需满足的时间约束为式中，tmove(·)为已知地面上设备的初始位置与终点位置计算机动耗费时间的算子，该过程需考虑设备最大机动速度以及地理信息因素；

2)设备由第α个窗口对应测站转场至第α+1个窗口对应测站实施观测需满足的时间约束为④重复第②、③步，检验观测方案涉及的所有设备转场时间是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足设备转场约束；

所述剩余观测次数约束是指在编排观测任务时，分配给一台设备的观测任务数不应超过其剩余观测次数；

剩余观测次数约束的计算步骤如下

①针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合 由集合可知，分配给第i台设备的观测任务数为αi，则其对应的剩余观测次数约束可表示为αi-Ri≤0     (3)

②重复第①步，检验观测方案涉及的所有设备剩余观测次数是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足剩余观测次数约束；

所述测站进出约束是指观测任务的编排应该将设备进出测站所耗费的展开时间、收拢时间因素纳入考虑，确保每一测站能够有效保障其被赋予的所有观测任务；

测站进出约束的计算步骤如下

①针对给定的观测方案，梳理出所有涉及到的测站及每一个测站需要实施观测的窗口集合；

②针对方案中的第k个测站，对其需要实施观测的窗口集合中的元素按照时间先后进行排序；

③设排序后第k个测站需要实施观测的窗口集合表示为 则测站进出约束的计算方法为

1)如果第k个测站需要实施观测的窗口不超过1个，则该测站不存在测站进出约束；

2)如果第k个测站需要实施观测的窗口不少于2个，则第β个窗口与第β+1个窗口需要满足的测站进出约束为④重复第②、③步，检验观测方案涉及的所有测站进出时间是否冲突，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足测站进出约束。

说明书

一种任务调度优化模型的优化约束确定方法

技术领域

[0001] 本发明涉及优化建模技术领域，尤其涉及一种任务调度优化模型的优化约束确定方法。

背景技术

[0002] 本发明涉及一型地面车载测量设备(以下简称设备)，设备部署于特定的地面测站，在空间目标过顶的一个较短的时间区间内，设备可对其进行观测，该时间区间称为设备对空间目标的观测窗口(观测窗口的计算涉及设备工作机理与空间目标需满足的运动特性、光电特性约束，这一问题并非本发明关注的重点，此处不再赘述)。设备可随载车沿公路机动，往返于车库与测站、测站与测站之间。设备机动到达特定测站后、具备观测状态前需要进行的准备工作的耗时称为展开时间topen，设备完成一次观测后、具备机动状态前需要进行的准备工作的耗时称为收拢时间tclose，设备在同一测站的两次观测之间需要进行的准备工作的耗时称为冷却时间tcool。由于设备使用的观测器件为精密仪器，在若干次观测后，观测器件需要进行必要的校准与调试，此时设备不能正常工作。对于任一设备而言，引入剩余观测次数的概念，当剩余观测次数为0时，认为设备失效。

[0003] 对上述地面车载测量设备的使用涉及一个观测任务调度问题，该问题可描述如下：现有M台观测设备，每一设备的初始位置已知、剩余观测次数已知，所有设备最早可由t0时刻出发，需在t1至t2时间内对N个空间目标进行观测，可供使用的测站有L个，要求给出最优的观测方案。

[0004] 上述问题的本质是一个武器目标分配(Weapon Target Assignment，WTA)问题，在工程实际中，通常采用穷举法或者最优化方法来求解。

[0005] 但是由于涉及到设备、测站与目标三者的映射关系，且需要将准备时间、剩余观测次数等约束纳入考虑，问题的内核较为复杂、维度发散很快，很难利用传统数学模型来求解。为了确定任务调度的优化模型，需先进行优化约束的确定，以保证观测方案的可行。

发明内容

[0006] 本发明旨在提供一种任务调度优化模型的优化约束确定方法，针对特殊的地面车载测量设备对空间目标观测任务调度问题的最优化模型，确定优化约束，以保证观测方案的可行。

[0007] 本发明的技术方案是一种任务调度优化模型的优化约束确定方法，其特征在于，包括设备转场约束、剩余观测次数约束、测站进出约束的确定。

[0008] 进一步的，所述设备转场约束是指观测任务的编排应该将设备的机动时间、展开时间、收拢时间、冷却时间纳入考虑，确保每一设备能够在给定的时间内完成所有必须的动作；

[0009] 所述设备转场约束的计算步骤包括：

[0010] ①针对给定的观测方案，梳理出所有涉及到的设备及每一台设备需要实施观测的窗口集合；

[0011] ②针对方案中的第i台设备，对其需要实施观测的窗口集合中的元素按照时间先后进行排序；

[0012] ③设排序后第i台设备需要实施观测的窗口集合可表示为且每个窗口Wi,j,k,q的时间前沿和后沿分别为 则设备转场约束的计算方法为[0013] 1)设备由初始位置转场至第1个窗口对应测站实施观测需满足的时间约束为[0014]

[0015] 式中，tmove(·)为已知地面上设备的初始位置与终点位置计算机动耗费时间的算子，该过程需考虑设备最大机动速度以及地理信息因素；

[0016] 2)设备由第α个窗口对应测站转场至第α+1个窗口对应测站实施观测需满足的时间约束为

[0017]

[0018] ④重复第②、③步，检验观测方案涉及的所有设备转场时间是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足设备转场约束。

[0019] 进一步的，所述剩余观测次数约束是指在编排观测任务时，分配给一台设备的观测任务数不应超过其剩余观测次数；

[0020] 剩余观测次数约束的计算步骤如下

[0021] ①针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合 由集合可知，分配给第i台设备的观测任务数为αi，则其对应的剩余观测次数约束可表示为

[0022] αi-Ri≤0   (3)

[0023] ②重复第①步，检验观测方案涉及的所有设备剩余观测次数是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足剩余观测次数约束。

[0024] 进一步的，所述测站进出约束是指观测任务的编排应该将设备进出测站所耗费的展开时间、收拢时间等因素纳入考虑，确保每一测站能够有效保障其被赋予的所有观测任务；

[0025] 测站进出约束的计算步骤如下

[0026] ①针对给定的观测方案，梳理出所有涉及到的测站及每一个测站需要实施观测的窗口集合；

[0027] ②针对方案中的第k个测站，对其需要实施观测的窗口集合中的元素按照时间先后进行排序；

[0028] ③设排序后第k个测站需要实施观测的窗口集合可表示为则测站进出约束的计算方法为

[0029] 1)如果第k个测站需要实施观测的窗口不超过1个，则该测站不存在测站进出约束；

[0030] 2)如果第k个测站需要实施观测的窗口不少于2个，则第β个窗口与第β+1个窗口需要满足的测站进出约束为

[0031]

[0032] ④重复第②、③步，检验观测方案涉及的所有测站进出时间是否冲突，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足测站进出约束。

[0033] 本发明的有益效果是：针对一类复杂的地面车载测量设备对空间目标观测任务调度问题，本发明从优化理论的视角进行了探索，提出了观测方案应该满足的优化约束，为优化问题的求解创造了条件，具有重要的工程意义。

附图说明

[0034] 图1为现有的一种观测窗口计算示意图；

[0035] 图2为本发明涉及的优化模型中优化自变量的定义；

[0036] 图3为本发明涉及的观测方案中单台设备典型观测任务流程；

[0037] 图4为本发明涉及的观测方案中单个测站典型观测任务流程。

具体实施方式

[0038] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图，对本发明进行进一步详细说明。

[0039] 由于本发明涉及的优化约束是任务调度优化模型的一部分，为便于理解，下文将建立一个要素齐备的最优化模型，包括优化自变量的定义、优化约束的计算及优化指标的计算。

[0040] 首先确定已知数据：现有M台观测设备Ei，i＝1,2,…,M，设备Ei的初始位置为Pi、剩余观测次数为Ri；所有设备最早可由t0时刻出发，需在t1至t2时间内对N个空间目标Tj，j＝1,2,…,N进行观测；可供使用的测站有L个Sk，k＝1,2,…,L；

[0041] 然后通过下述方法选取优化自变量，(1)利用已有的观测窗口算法，计算t1至t2时间内，设备部署在Sk测站对Tj目标的观测窗口集合Wj,k,q，q＝1,2,…,qjk，由表达式可知，该集合中窗口个数共有qjk个；

[0042] 其中对于介绍设备对空间目标的观测窗口算法，本发明给出一种简单的观测窗口算法，对于其它复杂算法，本发明同样适用。

[0043] 现有常见的一种观测窗口算法，在一次观测中，设备与空间目标的几何关系如图1所示，设备位于地面测站S，空间目标T以特定的轨迹飞过设备头顶，考虑设备的观测器件为简单圆锥光学传感器且其指向始终垂直于当地水平面，则其观测范围为锥角固定的一束圆锥，一旦目标飞入圆锥，则设备可对其实施观测，一旦目标飞离圆锥，则设备不再对其实施观测。因此，设备观测窗口算法可由下式表示

[0044] W＝[t|γt(T,S)＜γ0]   (1)

[0045] 式中，γ0为设备光学传感器锥角，γt(T,S)为计算t时刻目标T对测站S锥角的算子。由上式可知，观测窗口实际上就是目标满足设备观测约束的时刻的集合。

[0046] (2)遍历L个测站和N个目标，计算t1至t2时间内，设备部署在所有测站对所有目标存在的观测窗口全集Wj,k,q，j＝1,2,…,N，k＝1,2,…,L，q＝1,2,…,qjk，由表达式可知，该全集中窗口个数共有qtotal个， (3)引入一个长度为qtotal的一维数组，数组中的第x个元素对应于第x个观测窗口，其取值y为0到M之间的整数，表示将第x个观测窗口分配给第y台设备去执行观测任务。

[0047] 接下来介绍优化约束的计算方法。

[0048] 进一步的，所述设备转场约束是指观测任务的编排应该将设备的机动时间、展开时间、收拢时间、冷却时间纳入考虑，确保每一设备能够在给定的时间内完成所有必须的动作；

[0049] 所述设备转场约束的计算步骤包括：

[0050] ①针对给定的观测方案，梳理出所有涉及到的设备及每一台设备需要实施观测的窗口集合；

[0051] ②针对方案中的第i台设备，对其需要实施观测的窗口集合中的元素按照时间先后进行排序；

[0052] ③设排序后第i台设备需要实施观测的窗口集合可表示为且每个窗口Wi,j,k,q的时间前沿和后沿分别为 则设备转场约束的计算方法为[0053] 1)设备由初始位置转场至第1个窗口对应测站实施观测需满足的时间约束为[0054]

[0055] 式中，tmove(·)为已知地面上设备的初始位置与终点位置计算机动耗费时间的算子，该过程需考虑设备最大机动速度以及地理信息因素；

[0056] 2)设备由第α个窗口对应测站转场至第α+1个窗口对应测站实施观测需满足的时间约束为

[0057]

[0058] ④重复第②、③步，检验观测方案涉及的所有设备转场时间是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足设备转场约束。

[0059] 进一步的，所述剩余观测次数约束是指在编排观测任务时，分配给一台设备的观测任务数不应超过其剩余观测次数；

[0060] 剩余观测次数约束的计算步骤如下

[0061] ①针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合 由集合可知，分配给第i台设备的观测任务数为αi，则其对应的剩余观测次数约束可表示为

[0062] αi-Ri≤0   (4)

[0063] ②重复第①步，检验观测方案涉及的所有设备剩余观测次数是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足剩余观测次数约束。

[0064] 进一步的，所述测站进出约束是指观测任务的编排应该将设备进出测站所耗费的展开时间、收拢时间等因素纳入考虑，确保每一测站能够有效保障其被赋予的所有观测任务；

[0065] 测站进出约束的计算步骤如下

[0066] ①针对给定的观测方案，梳理出所有涉及到的测站及每一个测站需要实施观测的窗口集合；

[0067] ②针对方案中的第k个测站，对其需要实施观测的窗口集合中的元素按照时间先后进行排序；

[0068] ③设排序后第k个测站需要实施观测的窗口集合可表示为则测站进出约束的计算方法为

[0069] 1)如果第k个测站需要实施观测的窗口不超过1个，则该测站不存在测站进出约束；

[0070] 2)如果第k个测站需要实施观测的窗口不少于2个，则第β个窗口与第β+1个窗口需要满足的测站进出约束为

[0071]

[0072] ④重复第②、③步，检验观测方案涉及的所有测站进出时间是否冲突，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足测站进出约束。

[0073] 确定优化约束以后再确定优化指标，优化指标包括总机动距离、总观测时长、观测目标数目。

[0074] 总机动距离刻画了一个观测方案中所有设备需要机动的距离的总和，为了降低观测方案的成本，总机动距离应该尽可能小；

[0075] 总机动距离的计算步骤如下

[0076] ①针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合 则第i台设备的机动距离可表示为

[0077]

[0078] 式中，dmove(·)为已知地面上设备的初始位置与终点位置计算机动距离的算子，该过程需考虑地理信息等因素；

[0079] ②总机动距离可表示为

[0080]

[0081] 式中，需要指出，对于观测方案中没有分配观测任务的设备，其机动距离取为0；

[0082] 总观测时长刻画了一个观测方案对所有空间目标观测的时间窗口长度的总和，为了提高观测方案的效益，总观测时长应该尽可能大；

[0083] 总观测时长的计算步骤如下

[0084] ①针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合 则第i台设备的观测时长可表示为

[0085]

[0086] ②总观测时长可表示为

[0087]

[0088] 式中，需要指出，对于观测方案中没有分配观测任务的设备，其观测时长取为0；

[0089] 观测目标数目刻画了一个观测方案能够覆盖的所有空间目标的数目，为了提高观测方案的效益，观测目标数目应该尽可能多。观测目标数目的计算方法为，针对给定的观测方案，梳理出所有涉及到的空间目标的个数Ninvol即可。下面结合一个具体实施例来进一步说明。本实施例依托Satellite Tool Kit(STK)软件来实现。

[0090] 首先给定初始条件，取t0、t1、t2时刻分别为

[0091] t0＝(24 May 2018 00:00:00 UTCG)

[0092] t1＝(1 Jun 2018 00:00:00 UTCG)

[0093] t2＝(8 Jun 2018 00:00:00 UTCG)

[0094] 取观测设备载车的最大机动速度是60km/h，观测设备的展开时间、收拢时间、冷却时间分别为

[0095] topen＝3h,tclose＝1h,tcool＝1h

[0096] 假设有6台观测设备，其基本信息如表1所示

[0097] 表1观测设备初始条件

[0098]

[0099] 假设需对4个空间卫星目标实施观测，其在t1时刻的经典轨道根数如表2所示[0100] 表2空间卫星目标在t1时刻的经典轨道根数

[0101]

[0102]

[0103] 假设可供使用的测站有4个，其基本信息如表3所示

[0104] 表3测站初始条件

[0105] 编号 位置纬经高(deg/deg/km)S1 (43.8/87.583/0)
S2 (36.617/101.767/0)
S3 (25.9394/107.002/0)
S4 (38.041/114.479/0)

[0106] 下面对本实施例使用的设备观测窗口算法与设备机动算法做一说明。

[0107] 本实施例利用了STK软件的卫星过境计算工具Access来计算设备观测窗口，针对每一测站，分别添加一个传感器对象Sensor，将Sensor类型设为简单圆锥型，锥角取20deg，使用Access工具可以获得测站对目标的观测窗口。对于更加精密的观测窗口算法，本发明的技术方案仍然适用。

[0108] 本实施例利用了地球圆球模型来计算设备的机动距离与机动时间，也即假设对于球面上任意两点，设备以匀速沿球面劣弧由起点机动至终点。对于更加精密的设备机动算法，本发明的技术方案仍然适用。

[0109] 表4给出了利用Access工具计算得到的所有测站对所有目标的观测窗口的集合。

[0110] 表4所有测站对所有目标的观测窗口全集

[0111]

[0112]

[0113]

[0114]

[0115] 由表4可知，在本实施例中，观测窗口全集共有31个元素。因此，本实施例建立的最优化模型的自变量为长度为31的一维数组。下面给出一组自变量，分别计算其对应的优化约束和优化指标。

[0116] 自变量取为[0,3,0,0,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0]

[0117] 自变量对应的探测方案如表5所示

[0118] 表5自变量对应的观测方案

[0119]

[0120]

[0121] 自变量对应的优化约束如表6所示

[0122] 表6自变量对应的优化约束

[0123]

[0124] 由表6可知，该组自变量可以满足所有优化约束，为可行观测方案。

[0125] 自变量对应的优化指标如表7所示

[0126] 表7自变量对应的优化指标

[0127]总机动距离(km) 总观测时长(s) 观测目标数目
5117.215 123 4

[0128] 当然，本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。