作业时间随机的基本作战单元使用保障资源优化配置方法

摘要

本发明属于资源优化配置领域，具体涉及一种作业时间随机的基本作战单元使用保障资源优化配置方法，包括如下步骤：(S1)定义资源配置方案的表达与解码；(S2)对初始解进行内层优化，得到当前编码解对应的资源配置方案；(S3)基于改进的粒子群算法，生成新的编码解，即作业的调度方案。本发明的目的在于提供一种方法，基于RACP问题模型，结合分散搜索融合粒子群方法，实现基本作战单元使用保障资源的优化配置。本发明很好地解决了随机RACP问题，为资源优化配置方面的研究提供一个思路。本发明实施例方法提出的步骤简便易行，便于程序化处理，借助于计算机程序，可避免大量复杂的数学运算。

说明书

技术领域

本发明属于资源优化配置领域，具体涉及一种基本作战单元使用保障资源的优化配置方法。

背景技术

资源优化配置是指对于一项任务，优化任务作业的调度方案，使得该项任务能够按期完成并且配置的所有资源总成本最低。装备基本作战单元的使用保障资源配置本质上是资源优化配置问题。虽然国内外关注于使用保障资源配置问题的文献仍然较少，然而探讨一般性的资源配置优化问题的研究并不罕见，这类研究对于开展装备基本作战单元的使用保障资源优化配置提供了有益的借鉴。

在典型的任务想定下，基本作战单元使用保障资源的模型与资源可用量成本问题(Resource Availability Cost Problem，RACP)模型近似，但是更加复杂。这一问题可以被描述为：一项任务的完成时限被预先加以规定，该任务包含一系列任务作业，各个任务作业都需要一定数量的特定资源，且各作业之间存在着严格时序约束，怎样优化任务作业的调度方案，使得该项任务能够按期完成并且配置的所有资源总成本最低。

在实际操作中，由于系统误差、人员熟练度等因素的存在，保障作业的时间难以精确给定，往往以随机分布的形式存在。考虑保障作业的时间随机性后，资源配置优化问题更加复杂。目前，针对作业时间随机的RACP问题的研究还较为少见。

发明内容

本发明的目的在于解决上述问题之一。

为了实现本发明目的，本发明建立了随机RACP问题模型，并采用双层优化算法，外层基于改进的粒子群算法生成作业的调度方案，内层基于生成的调度方案和资源、时间等约束对资源的数量进行配置。

本发明实施例的一种作业时间随机的基本作战单元使用保障资源优化配置方法方法包括以下步骤：

(S1)定义资源配置方案的表达为以下问题：

并对该表达式进行解码得到初始解；

其中，c_k代表第k类资源的成本，分配的第k类资源数量为x_k；

(S2)对编码解进行内层优化。在第一次迭代过程中，给出初始编码解对应的资源配置方案，在后续迭代过程中，优化迭代过程中得到的新的编码解对应的资源配置方案；

内层优化约束条件如下：

其中，第i个保障作业的开始时间为s_i，持续时间为T_i，所需要的第k类资源数量为r_k,i，任务完成时限为D，任务成功概率约束为θ_m，f_i(t)为特定随机分布的概率密度函数；

(S3)进行外层优化，基于改进的粒子群算法生成新的编码解。

在某些实施例中，所述步骤(S1)的具体过程为：

(S11)运用随机键表达方式对问题的解进行编码；

结合时序约束关系和资源配置方案的限制，用一组0到1之间的随机数组成的向量，其维数等于使用保障任务中的作业总数，用以描述使用保障作业的优先级；

(S12)依据使用保障作业完成时间的随机分布函数，通过随机抽样生成各个作业的完成时间；

(S13)依据当前编码解以及资源配置方案进行解码，执行当前使用保障任务并记录此次任务执行时间；

假设执行中作业的集合为Y*，待执行作业的集合为H*；初始化集合对于第i个作业(1≤i≤N)，若作业i没有紧前作业，进入集合H*；

遍历集合Y*，计算该集合中的最早作业结束时间t_f，并删除集合Y*中结束时间为t_f的各项作业，释放其占用的使用保障资源；

遍历集合H*，选择随机键值最高且对应装备处于闲置状态的作业j；将作业j由集合H*移到集合Y*，并占用其所需的资源；同时，若作业j紧后作业满足集合H*的条件，则将其加入集合H*，如此循环；

(S14)若算法迭代次数到达预设要求，则依据每次迭代计算出的使用保障任务平均完成时间和按期完成的成功概率；否则，返回步骤(S12)。

在某些实施例中，所述步骤(S2)的具体过程为：

(S21)利用各使用保障作业完成时间的期望值和保障任务完成时限计算出各作业的最晚开始时间，生成初始的使用保障资源配置方案以及初始编码解；

(S22)在外层算法框架中直接为当前编码解调取当前最优的使用保障资源配置方案，以提高资源优化配置效率，通过仿真方法评价当前编码解和资源配置方案，得到使用保障任务成功概率，若能够达到当前任务要求，则进入步骤(S24)，若不能，则进入步骤(S23)；

(S23)在外层算法框架中调取各使用保障作业的最晚开始时间，并计算当前编码解在当前资源配置下的平均开始时间，找到平均开始时间延时最大的使用保障作业，批量增加其所需的各类使用保障资源数量，通过仿真方法评价当前编码解和资源配置方案，得到使用保障任务成功概率，若能够达到当前任务要求，则进入步骤(S24)，若不能，重复步骤(S23)。

(S24)自第一类使用保障资源开始依次逐类逐个减少资源数量，依次通过仿真方法评估当前编码解和使用资源配置方案，获得使用保障任务成功概率，直至使用保障资源配置方案无法满足使用保障任务需求；

(S25)保存步骤(S24)中满足使用保障任务要求且成本最优的使用保障资源配置方案，即为当前编码解所对应的最优使用保障资源配置方案，将该使用保障资源配置方案总成本作为当前编码解的目标函数值。

在某些实施例中，所述步骤(S3)的具体过程为：

(S31)利用PSO(Particle Swarm Optimization)演化策略生成新的编码解，通过步骤(S2)中的方法计算新解的目标函数。

粒子群算法参考了动物的群体行为特征，将进化更新过程表示如下：

其中，c₁和c₂是学习因子，用以确定粒子当前位置X、历史轨迹以及当前最优解对粒子演化的影响程度；ω是惯性因子，决定粒子速度V对于运动过程的影响程度；r₁和r₂是0和1之间的两个随机数，分别用以确定解的演化过程中朝向历史轨迹和当前最优解的更新步长；

(S32)利用分散搜索寻优方法寻找新的最优解，若未发现，则进入步骤(S33)；假设参考集中参考解的个数为Psize，参考集中的编码解向量为X_i，其中i＝1,2,…,Psize，X₁为当前最优解。

将参考集中的第j个参考解(2≤j≤Prize)作为执行解X₂。对于第i个参考解(1≤i≤N)，若X₁[i]≠X₂[i]，对X₁和X₂的第i个位置进行交叉，生成新解New_1和New_2。

返回步骤(S2)，计算新解目标函数；

若新解的目标函数值比当前最优解更优，更新最优解；若新解的目标函数值优于当前参考集中的最劣参考解，更新参考集，替换最劣参考解；

(S33)判断仿真次数是否满足结束条件，若不满足，则返回步骤(S31)；若满足，则结束寻优过程并保留当前最优解与对应的资源配置方案。

与现有技术相比，本发明实施例方法基于RACP问题模型，结合分散搜索融合粒子群方法，实现基本作战单元使用保障资源的优化配置。本发明很好地解决了随机RACP问题，为资源优化配置方面的研究提供一个思路。本发明实施例方法提出的步骤简便易行，便于程序化处理，借助于计算机程序，可避免大量复杂的数学运算。

附图说明

图1是本发明实施例方法的流程图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

下文的公开提供了许多不同的实施例或例子用来实现本发明的不同结构。为了简化本发明的公开，下文中对特定例子的部件和设置进行描述。当然，它们仅仅为示例，并且目的不在于限制本发明。此外，本发明可以在不同例子中重复参考数字和/或字母。这种重复是为了简化和清楚的目的，其本身不指示所讨论各种实施例和/或设置之间的关系。此外，本发明提供了的各种特定的工艺和材料的例子，但是本领域普通技术人员可以意识到其他工艺的可应用于性和/或其他材料的使用。另外，以下描述的第一特征在第二特征之“上”的结构可以包括第一和第二特征形成为直接接触的实施例，也可以包括另外的特征形成在第一和第二特征之间的实施例，这样第一和第二特征可能不是直接接触。

在本发明的描述中，需要说明的是，除非另有规定和限定，术语“安装”、“相连”、“连接”应做广义理解，例如，可以是机械连接或电连接，也可以是两个元件内部的连通，可以是直接相连，也可以通过中间媒介间接相连，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。

参照下面的描述和附图，将清楚本发明的实施例的这些和其他方面。在这些描述和附图中，具体公开了本发明的实施例中的一些特定实施方式，来表示实施本发明的实施例的原理的一些方式，但是应当理解，本发明的实施例的范围不受此限制。相反，本发明的实施例包括落入所附加权利要求书的精神和内涵范围内的所有变化、修改和等同物。

下面参照附图来描述根据本发明实施例进行详细描述。

图1为一种作业时间随机的基本作战单元使用保障资源优化配置方法的流程示意图。

该方法主要包括以下步骤：

(S1)定义资源配置方案的表达与求解；

(S2)对编码解进行内层优化；

(S3)进行外层优化，基于改进的粒子群算法生成新的编码解。

该实施例为在生成初始作业调度和资源配置方案的基础上，优化资源配置方案并进行仿真评估，基于改进粒子群算法生成新的调度方案并重复之前步骤，如此迭代，直到仿真次数达到预设限制，得到最优解。

该实施例中，基本作战单元中的所有使用保障作业包含了实际任务中的保障作业1至作业N，虚拟保障作业0与作业N+1，分别表示保障任务的开始与结束。当前面临的主要问题描述如下：基本作战单元由特定总数的同类型装备所组成，其保障系统需要应对若干种不同的典型使用保障任务，且每种任务均有相应的规定完成时限；在每项使用保障任务的执行过程中，基本作战单元内的各装备均需开展特定数量的使用保障作业，且针对单台次装备，各作业的执行需满足特定的时序约束；针对装备执行使用保障作业的过程中需要利用特定种类和特定数量的保障资源，且保障资源在保障作业之间可能存在交叉互用的共享关系；各使用保障作业的持续时间服从特定的随机分布；执行每项使用保障任务的过程需在一定概率范围内按期完成；优化问题的目标在于求得满足上述条件，并最小化保障系统总配置成本的资源配置以及使用保障任务执行方案。

基于上述分析，令c_k代表第k类资源的成本，分配的第k类资源数量为x_k，第i个保障作业的开始时间为s_i，持续时间为T_i，所需要的第k类资源数量为r_k,i，任务完成时限为D_m，任务成功概率约束为θ_m。

因此该优化问题的数学模型如下：

S.T.

该优化模型的目标在于最小化基本作战单元使用保障资源的总配置成本，该目标函数的变量即为配置各类使用保障资源的总数；

其中，(1)式表示使用保障任务中各作业间需满足的逻辑时序约束，其中第i个作业是第j个作业的紧前作业；

其中，(2)式表示任务应当自下达时刻起即刻开始执行，不考虑现有约束条件之外的其他因素使得基本作战单元的保障任务开始时间产生延迟；

其中，(3)式表示任意时刻任意一类使用保障资源的实际使用量均不可超出该类资源的配置总量；

其中，(4)式表示按照当前的使用保障资源配置方案执行使用保障任务，必须满足用户对于特定时限内完成保障任务的成功概率要求；

其中，(5)式表示各项作业的完成时间服从特定随机分布的概率密度函数。

本发明的一个实施例中，作为优选，所述步骤(S1)的具体过程为：

(S11)运用随机键表达方式对问题的解进行编码；

结合时序约束关系和资源配置方案的限制，用一组0到1之间的随机数组成的向量，其维数等于使用保障任务中的作业总数，用以描述使用保障作业的优先级，实现对整个使用保障任务的完成过程的描述。

(S12)依据使用保障作业完成时间的随机分布函数，通过随机抽样生成各个作业的完成时间；

(S13)依据当前编码解以及资源配置方案进行解码，执行当前使用保障任务并记录此次任务执行时间；

假设执行中作业的集合为Y*，待执行作业的集合为H*；初始化集合对于第i个作业(1≤i≤N)，若作业i没有紧前作业，进入集合H*；

遍历集合Y*，计算该集合中的最早作业结束时间t_f，并删除集合Y*中结束时间为t_f的各项作业，释放其占用的使用保障资源；

遍历集合H*，选择随机键值最高且对应装备处于闲置状态的作业j；将作业j由集合H*移到集合Y*，并占用其所需的资源；同时，若作业j紧后作业满足集合H*的条件，则将其加入集合H*，如此循环；

(S14)若达到仿真次数到达预设要求，则依据每次仿真计算出的使用保障任务平均完成时间和按期完成的成功概率；否则，返回步骤(S12)。

本发明的一个实施例中，作为优选，所述步骤(S2)的具体过程为：

(S21)利用各使用保障作业完成时间的期望值和保障任务完成时限计算出各作业的最晚开始时间，生成初始的使用保障资源配置方案以及初始编码解；

(S22)在外层算法框架中直接为当前编码解调取当前最优的使用保障资源配置方案，以提高资源优化配置效率，通过仿真方法评价当前编码解和资源配置方案，得到使用保障任务成功概率，若能够达到当前任务要求，则进入步骤(S24)，若不能，则进入步骤(S23)；

(S23)在外层算法框架中调取各使用保障作业的最晚开始时间，并计算当前编码解在当前资源配置下的平均开始时间，找到平均开始时间延时最大的使用保障作业，批量增加其所需的各类使用保障资源数量，通过仿真方法评价当前编码解和资源配置方案，得到使用保障任务成功概率，若能够达到当前任务要求，则进入步骤(S24)，若不能，重复步骤(S23)。

(S24)自第一类使用保障资源开始依次逐类逐个减少资源数量，依次通过仿真方法评估当前编码解和使用资源配置方案，获得使用保障任务成功概率，直至使用保障资源配置方案无法满足使用保障任务需求；

(S25)保存步骤(S24)中满足使用保障任务要求且成本最优的使用保障资源配置方案，即为当前编码解所对应的最优使用保障资源配置方案，将该使用保障资源配置方案总成本作为当前编码解的目标函数值。

本发明的一个实施例中，作为优选，所述步骤(S3)的具体过程为：

(S31)利用PSO(Particle Swarm Optimization)演化策略生成新的编码解，通过“编码解的使用保障资源启发式优化”方法计算新解的目标函数。

粒子群算法参考了动物的群体行为特征，将进化更新过程表示如下：

其中，c₁和c₂是学习因子，用以确定粒子当前位置、历史轨迹以及当前最优解对粒子演化的影响程度；ω是惯性因子，决定粒子速度对于运动过程的影响程度；r₁和r₂是0和1之间的两个随机数，分别用以确定解的演化过程中朝向历史轨迹和当前最优解的更新步长；

(S32)利用分散搜索寻优方法寻找新的最优解，若未发现，则进入步骤(S33)；假设参考集中参考解的个数为Psize，参考集中的编码解向量为X_i，其中i＝1,2,…,Psize，X₁为当前最优解。

将参考集中的第j个参考解(2≤j≤Prize)作为执行解X₂。对于第i个参考解(1≤i≤N)，若X₁[i]≠X₂[i]，对X₁和X₂的第i个位置进行交叉，生成新解New_1和New_2。

返回步骤(S2)，利用编码解的使用保障资源启发式优化方法，计算新解目标函数；

若新解的目标函数值比当前最优解更优，更新最优解；若新解的目标函数值优于当前参考集中的最劣参考解，更新参考集，替换最劣参考解；

(S33)判断仿真次数是否满足结束条件，若不满足，则返回步骤(S31)；若满足，则结束寻优过程并保留当前最优解与对应的资源配置方案。

本发明的一个具体实施例中，优化配置对象具体定义为一个由三辆装备构成的基本作战单元，每辆装备需要进行三步使用保障过程方可投入使用，分别记为作业1、2、3；共有三类保障资源需要优化，记为资源1、2、3，每一类资源的单价如表1所示，保障任务的各种约束条件如表2所示。

表1 使用保障资源单价

表2 保障作业时序及资源约束

该一个具体实施例中，要求基本作战单元能够以至少95％的概率在10分钟内完成使用保障任务，主要目标就是在保证基本作战单元作战任务需求得到满足的前提下，尽可能降低保障装备的配置总成本。

该一个具体实施例中，优化过程具体如下：

(S1)定义资源配置方案的表达与解码

首先，随机生成一组随机键值，本实例中共有9个作业，因此生成一个9维的向量用以表示使用保障任务的完成过程(S11)。初始值为随机生成的0-1之间的随机数，如下所示。

k1k2k3k4k5k6k7k8k90.42180.91570.79220.95950.65570.03570.84910.9340.6787

在一次仿真中，对每一个保障作业，根据其持续时间的分布，生成作业持续时间(S12)。如下所示。

之后生成一组初始的资源配置方案，本实例中共有3类资源，生成的初始资源配置方案如下所示。此时目标函数值为810。

r1r2r3362

根据当前作业调度方案和资源配置方案进行解码(S13)，得到当前方案下保障任务的完成时间为11.485分钟，之后生成新的一组作业持续时间，继续进行下一次仿真，直到仿真次数达到设定的上限(S14)。得到当前方案的平均完成时间为11.024分钟，任务完成概率为0.725，不满足要求，因此进入下一步s2，首先进行资源配置方案优化。

(S2)对编码解进行内层优化

根据上述方案，找到延迟最大的作业为作业3，因此增加其所需的资源(S22)，分别为1个单位的资源1，2个单位的资源3，此时再利用(S13)的方法进行评估，保障任务的完成时间为8.97分钟，满足要求，因此进入下一步(S33)。从第一类使用保障资源开始依次逐类逐个减少资源数量，该过程不做具体描述，得到能够完成保障任务的成本最低的资源配置方案如下所示。此时，目标函数值为840，即为当前调度方案下的最优资源配置方案。

r1r2r3643

当前方案下，平均完成时间为9.875分钟，任务完成概率为0.96，满足任务要求。

(S3)基于改进的粒子群算法，生成新的编码解(作业的调度方案)

设定粒子群算法的参数为c1＝c2＝0.75,ω＝1.5,vmax＝0.5,vmin＝-0.5，利用改进的粒子群算法的演化过程(S23)，生成了一组新的随机键值，用以表示新的作业调度方案，如下所示。

k1k2k3k4k5k6k7k8k90.09710.82350.69480.31710.95020.03440.43870.38160.7655

利用s2的方法，评估得到当前调度方案下的最优资源配置方案如下，目标函数值为850。

r1r2r3544

当前方案下，平均完成时间为9.935分钟，任务完成概率为0.955，满足任务要求。进入(S24)，在当前方案下，利用分散搜索策略没有找到新的最优解，进入(S25)。

之后利用外层的改进粒子群算法不断生成新的随机键值，在S2与S3步骤进行循环迭代，直到粒子群算法达到执行次数上限。得到的最优调度方案和最优资源配置方案如下：

k1k2k3k4k5k6k7k8k90.61330.89630.82910.40480.49890.70160.16640.56310.7418

r1r2r3616

当前方案下，平均完成时间为8.687分钟，任务完成概率为0.95，满足任务要求，且是成本最低的资源配置方案。

由此可见，本发明实施例首先运用随机键表达方式对问题的解进行编码，并定义资源配置方案的解码方法，然后通过抽样生成的资源配置初始解进行内层优化，得到当前编码解对应的资源配置方案，再基于改进的粒子群算法，生成新的编码解，即作业的调度方案，经过往复迭代最终得到最优资源配置方案。通过上述步骤，本发明实施例基于RACP问题模型，结合分散搜索融合粒子群方法，很好地实现了基本作战单元使用保障资源的优化配置。

流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备(如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统)使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，"计算机可读介质"可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。计算机可读介质的更具体的示例(非穷尽性列表)包括以下：具有一个或多个布线的电连接部(电子装置)，便携式计算机盘盒(磁装置)，随机存取存储器(RAM)，只读存储器(ROM)，可擦除可编辑只读存储器(EPROM或闪速存储器)，光纤装置，以及便携式光盘只读存储器(CDROM)。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列(PGA)，现场可编程门阵列(FPGA)等。

本技术领域的普通技术人员可以理解实现上述实施例方法携带的全部或部分步骤是可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，该程序在执行时，包括方法实施例的步骤之一或其组合。

此外，在本发明各个实施例中的各功能单元可以集成在一个处理模块中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。所述集成的模块如果以软件功能模块的形式实现并作为独立的产品销售或使用时，也可以存储在一个计算机可读取存储介质中。

上述提到的存储介质可以是只读存储器，磁盘或光盘等。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同限定。