Ｖ０１．３８．Ｎｏ．６ 火力与指挥控制 第３８卷第６期 Ｊｕｎ，２０１３ Ｆｉｒｅ Ｃｏｎｔｒｏｌ＆Ｃｏｍｍａｎｄ Ｃｏｎｔｒｏｌ ２０１３年６月 文章编号：１００２－－Ｏ６４０（２０１３）０６－０１５９－０４ 战时装备维修保障资源优化模型 孙宝琛，贾希胜，程中华 （军械工程学院，石家庄０５０００３） 摘要：维修资源在抢修过程中的分配决定了抢修活动的平均处理时间和等待时间，针对抢修实施时维修资源 的分配，研究资源的优化配置使抢修时间最小的问题。在抢修过程中使抢修时间最小的目标和约束条件下，提出了 资源配置优化的排队模型，并结合遗传算法给出了求解最优配置模型的方法，通过实例分析说明了模型和方法的应 用情况。资源配置优化模型和算法已成功应用于集群装备保障决策系统的开发。 关键词：保障决策，资源优化，排队模型，遗传算法 中图分类号：Ｅ２４２ 文献标识码：Ａ Ｓｔｕｄｙ ｏｎ Ｍｏｄｅｌ ｆｏｒ Ｅｑｕｉｐｍｅｎｔ Ｍａｉｎｔａｉｎｃｅ Ｒｅｓｏｕｒｃｅ Ｏｐｔｉｍｉｚａｔｉｏｎ ｉｎ Ｗａｒｔｉｍｅ ＳＵＮ Ｂａｏ－ｃｈｅｎ，ＪＩＡ Ｘｉ－ｓｈｅｎｇ，ＣＨＥＮＧ Ｚｈｏｎｇ－ｈｕａ （Ｏｒｄｎｏｎｃｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｌｌｅｇｅ，Ｓｈｉｔｆ ｈｎａｎｇ ０５０００３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｓｓｉｇｎｍｅｎｔ ｏｆ ｒｅｓｏｕｒｃｅ ｄｉｒｅｃｔｉｌｙ ｄｅｃｉｄｅｓ ｔｈｅ ａｖｅｒａｇｅ ｗａｉｔｉｎｇ ａｎｄ ｄｅａｌｉｎｇ ｔｉｍｅ ｏｆ ｅａｃｈ ａｃｔｉｖｉｔｙ ｉｎ ｂａｔｔｌｅ ｄａｍａｇｅ ｒｅｐａｉｒ．Ｔｏ ｍｉｎｉｍｉｚｅ ｔｈｅ ｒｅｐａｉｒ ｔｉｍｅ ｂｙ ｐｒｏｐｅｒｌｙ ａｌｌｏｃａｔｉｎｇ ｔｈｅ ｒｅｓｏｕｒｃｅ ｉｓ ｓｔｕｄｉｅｄ．Ｆｉｒｓｔｌｙ，ｔｈｅ ｏｂｊｅｃｔｓ ａｎｄ ｃｏｎｓｔｒａｉｎｔｓ ｆｏｒ ｍｉｎｉｍｉｚｉｎｇ ｔｈｅ ａｖｅｒａｇｅ ｒｅｐａｉｒ ｔｉｍｅ ａｙｅ ａｄｄｒｅｓｓｅｄ．Ｔｈｅｎ， ｔｈｅ ｑｕｅｕｅ ｍｏｄｅｌ ｏｆ ｒｅｓｏｕｒｃｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｗｉｔｈ ｔｈｅ ｍｉｎｉｍａｌ ｃｏｓｔ ｔｉｍｅ ｉｓ ｄｅｓｉｇｎｅｄ，ａｎｄ ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｒｅｓｏｌｖｅ ｔｈｉｓ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｓ ｐｒｅｓｅｎｔｅｄ．Ａｔ ｌａｓｔ，ａｎ ｅｘａｍｐｌｅ ｉｓ ｕｓｅｄ ｔｏ ｅｘｐｌａｉｎ ｔｈｅ ｍｏｄｅｌ ａｐｐｌｉｃａｔｉｏｎ．Ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｏｄｅｌ ａｎｄ ａｌｇｏｒｉｔｈｍ ａｙｅ ｄｅｖｅｌｏｐｅｄ ｉｎ ｇｒｏｕｐ ｅｑｕｉｐｍｅｎｔ ｍａｉｎｔａｉｎｃｅ ｓｕｐｐｏ￣ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍ． Ｋｅｙ ｗｏｒｄｓ：ｓｕｐｐｏ￣ｄｅｃｉｓｉｏｎ，ｒｅｓｏｕｒｃｅｓ ｏｐｔｉｍｉｚａｔｉｏｎ，ｑｕｅｎｅ ｍｏｄｅｌ，ｇｅｎｅｔｉｃ ｌａｇｏｒｉｔｈｍ 引 言 置知识的表达、获取、发现，通过属性约简的方法给 出不同条件下的资源配置方案；何健敏等［，］分别建 战时装备抢修实施过程中需要许多不同的活 立了单资源、多资源及资源连续消耗系统的维修资 动组成，同时在活动运行时要消耗一定的资源，如 源优化调度模型，得到的维修资源优化调度方案使 人力、器材、设备等…，因此，在抢修过程的活动中 得维修保障时间最短、出救点最少；孙颖等…考虑 合理地分配资源是保证高效、快速抢修的必要条 需求点的不同重要程度，建立非线性整数规划模型， 件，同时也可提高相关资源的利用率。对保障资源 以最小时间需求为目标对资源进行调度。目前，相关 的配置进行优化，要求抢修活动间的资源需求尽量 文献主要讨论抢修实施过程中逗留时间与资源配置 不产生冲突，活动间的资源需求的耦合性较小，资 数量，任务调度算法等的优化，但对抢修实施的平均 源的需求达到平衡，从而实现各个活动的资源平均 响应时间与资源配置数量的优化研究较少。 等待时间等指标最小的目标。资源的配置优化是典 本文考虑抢修任务的实施过程中，将抢修过程 型的ＮＰ难题，为此国内外学者进行了大量研究，宋 中的各种活动的资源进行优化配置等价为在资源的 光明等 应用粗糙集建立了装备维修保障资源配 时间代价最小的约束下，使抢修点的整体抢修任务 收稿日期：２０１２－０４—１７ 修回日期：２０１２—０６—０１ 作者简介：孙宝琛（１９８０一），辽宁瓦房店人，博士。研究方向：战时装备保障理论与应用。 ・１５９・ （总第３８—１０６２） 火力与指挥控制 ２０１３年第６期 时间最短。所谓资源的时间代价，是指抢修现场出现 缺少某种资源时，获取这种资源的时间，这可以从２ 种隋况考虑：①若抢修地点有资源，则资源时间代价 指资源准备时间；②若抢修地点没有资源，则资源的 时间代价指资源申请、运输、准备等时间之和。 提下进行的，主要是对损坏装备进行分析、定位、隔 离的故障诊断，以及备件请领和进行换件修理的过 程，备件请领主要体现了对备件申请、审批、领取、 登记、送达的请领过程，抢修实施的整体过程如图１ 所示。设过程中需要ｍ类资源参与，包括人员、器 １ 问题描述 对于抢修实施过程，是在人员设备都配齐的前 理人 材、设备、运输车辆等；运送第 类资源的时间为ｄｉ， ｉ＝１，２，…，ｍ；活动Ｐ调用资源 的数目为 过程中 可利用的资源 的最大数为 ——］ 厂—＜ 璺 损装 没备 塑囹— 鬻 鬻］ ． 图１ 装备抢修实施流程图 设为活动在相应的资源 队列中的平均等待 时间；ｐ 表示活动 被执行的概率；活动 执行时 Ｗｉ权平均响应时间的总和，是指各个可执行路径所花 费的总时间和相应加权因子的乘积的总和。 约束条件２：抢修实施过程中的资源配置的总 时间代价不能超过抢修实施过程中资源配置的总 时间代价的上限Ｄ。即资源的申请、运输、准备等时 间之和不能超过资源配置的时限。 约束条件３：每类资源对活动的执行都是独立 间服从指数分布，其参数为 。上图中过程模型包含 不同的可执行路径。令Ｒｉ， ＝１，２，…，ｋ表示其中的 条可执行路径 Ｊ；， ＝ｌ，２，…，ｋ是可执行路径尺ｆ被 执行的概率； 表示可执行路径的平均处理时间； 一为一向量，表示可执行路径包含的活动节点。 受损装备的到达服从参数为人的泊松分布； 表示过程的平均响应时间；Ｄ是中资源配置的总时 间代价的上限。 由此问题可描述为：在资源配置总的时间代价 的，既不出现某一个资源同时服务于两个活动的情 况，且资源对于活动的满足是并行的，同类资源可 同时满足多个活动。 约束条件４：各个活动调用的资源数目不能超 不超过的前提下，通过调整各类资源在活动和可执 行路径中的配置方案来改善过程的时间性能，使平 均响应时间最短。 过过程中可供使用的资源数目的最大值，即 ｉ≤ｕ 。 ３模型建立 在总时间代价不超过Ｄ的前提下，以最大化改 善抢修实施平均响应时间为目标，为过程中的活动 分配人力、器材、设备等等，对这一过程可建立下面 一２ 约束条件 抢修实施过程的平均响应时间，包括资源分配时 间，资源等待时间，资源消耗时间等，通过对过程的各 个活动节点分配不同数量的资源，改善各个活动的工 作情况，从而达到最小化过程的平均响应时间。 由抢修过程的复杂性和差异性，不能得到一个 统一的计算平均响应时间的公式，只能针对具体的 背景进行计算优化，对于优化的约束，也因不同的 环境、不同的任务而不同Ｉ５］。针对本文研究问题的 背景，归纳最小化抢修过程时间的约束条件如下： 约束条件１：抢修实施过程中各个可执行路径 的加权平均响应时间的总和最小。可执行路径的加 组数学模型： 若资源ｅ 被分配，则△Ｆｌ，否则△。＝０，ｉ＝１，２， ，ｍ。…每条可执行路径的平均处理时间为： ｔｒｙ ｉ＝１ ｊ。Ａｉ （１） 其中ｔ 为第 类资源的平均处理时间，ｔ 可以分为２ 个部分：一是第ｉ类资源的平均等待时间Ｗ ，根据约 束的第３条，可将活动对资源的需求看作是Ｍ／Ｍ／ｃ ／。。的排队系统，因此，根据文献［６］中平均等待时 间的推导： （ ＋ ） 二是活动执行时间，即资源消耗时间，由于活 动的执行时间服从参数Ｍ ，的指数分布，，则活动的执 ・行时间为１／ｕ ，则： ＝ ＋１／ （３） ｌ６Ｏ・ 孙宝琛，等：战时装备维修保障资源优化模型 （总第３８—１０６３） 式（２）中，过程中活动的执行概率为： 上 ＝ （Ｐｊ ｅｏ＂ ） （４） ｊ＝ｌ 根据问题的描述和上面的推导过程，则资源调 度优化模型可作如下描述： ． ．ｍｌｎｔａ， ｍｌｎ Ｐｊ。ｔＲｊ Ｊ，， （５）、 ．ｆ．∑△ｆ。 。 ≤Ｄ，ｅｉ≤甜， ｉ＝１ 上面的推导中，式（１）计算了可执行路径 的 平均处理时间；式（２）是可执行路径 中活动在相 应的资源队列中的平均等待时间；式（３）计算了可 执行路径尺 中活动的平均处理时间；式（４）得出可 执行路径Ｒ 中活动被执行的概率；式（５）为目标函 数和约束条件。目标函数是实施过程中可执行路径 Ｒ 的加权值之和，表示最小化实施过程平均响应时 间，它是变量ｅ的函数，变量ｅ为一个候选解向量； 约束条件是对添加资源的总时间代价的约束。 ４基于遗传算法的优化求解 针对本文的优化问题是典型的ＮＰ难问题，用 传统的精确算法难以完成对抢修实施过程中具有 一定规模的资源调度，为此考虑采用智能的遗传算 法（ＧＡ，Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ）进行优化［ 。遗传算法利 用生物进化和遗传的思想实现优化过程，区别于传 统优化算法，它具有以下特点： ０）ＧＡ不受函数约束条件连续性、可导性的限 制； ②ＧＡ的搜索过程是从问题的一个集合开始 的，而不是从单个个体开始的，具有隐含并行搜索 特性，从而大大减小了陷人局部极小的可能； ￣ＧＡ使用的遗传操作均是随机操作，同时ＧＡ 根据个体的适配值信息进行搜索，无需其他信息； ￣ＧＡ具有全局搜索能力，最善于搜索复杂问 题和非线性问题。 根据遗传算法的设计，标准的算法应用步骤分 为： ①根据问题的编码方案，随机产生一组初始个 体构成初始种群； ②根据适配值函数，评价每一个体的适配值， 判断算法收敛准则是否满足。若满足则输出搜索结 果，否则执行以下步骤； ③根据适配值大小以一定方式执行复制操作； ④根据交叉概率ｐｃ执行交叉操作； ⑤按变异概率Ｐ 执行变异操作； ⑥返回步骤②。 上述算法流程中，适配值是对个体进行评价的 一种指标，它与个体的目标值存在对应关系；复制 操作一般采用比例复制，即复制概率正比于个体的 适配值，这意味着适配值高的个体在下一代中复制 自身的概率大，从而提高了种群的平均适配值；交 叉操作通过交换两父代个体的部分信息构成后代 个体，使得后代继承父代的有效模式，从而有助于 产生优良个体；变异操作通过随机改变个体中某些 基因而产生新个体，有助于增加种群的多样性，避 免早熟收敛。算法的标准实施流程如图２所示。 堕 ／厂＿＿了珥丽 笪 堡 些焦 ／ ］ 一一 ．—：豸重垂至垂 堕 一 一— ■ — 制操作 １＿ 输 辇１ ｌ秦寻／ Ｎ Ｎ 算法结束 图２遗传算法标准实施流程 ５ 方法举例 设抢修实施现有人员、设备、器材和运输车辆４ 类资源，受损装备根据受损程度的不同需要分别在 基层一级、基层二级、中继级和基地级４个级别进 行抢修，因此，区分不同级别的修理人员、设备、器 材和车辆，由此资源可以详细分为１６种，设４类资 源其时间代价即资源到达地点的时间为Ｄ＝ ［６，１０，１６，６］，系统中４类可供利用的资源总数为 Ｍ ［１５，６，５０，８］，消耗资源的时间代价限制为９０，现 在需要寻找一个资源分配ｅ方案满足式（５）。根据图 １所示的实施过程，不同受损装备具有相似的实施 过程，只是发生的概率不同，因此，可以将整个过程 看作是并行的４个相同的过程，而图１在一个过程 中存在两个分支结构，由此会有两条执行路径，并 ・１６１． （总第３８—１０６４） 火力与指挥控制 ２０１３年第６期 行的４个过程就有ｌ６条执行路径，设每一条执行 １／６，１／７，１／８，１／９］，由此可以化简式（２）为资源量ｅ 路径发生概率分别为ｐ产［０．２２４，０．０５６，０．０９６，０．０２４， ０．１２６，０．０５４，０．０８４，０．０３６，０．０６，０．０４，０．０６，０．０４，０．０２， 的函数，进而将确定式（５）的目标函数和约束函数。 应用ＭＡＴＬＡＢ优化工具箱中的ｇａｔｏｏｌ工具对 ０．０２，０．０３，０．０３］，由此，根据式（４）即可计算过程中每 类资源被消耗的概率 ＝［０．６，０．２９２，０．１７９，０．０６５］，同 时给出１６种资源的消耗时间分布所服从的参数 为： ＝［１／３，１／４，１／５，１／６，１／２，１／３，１／４，１／２，１／３，１／４，１／５， 最好值：１２ ２１８１平均值：１２ ２３８６ 式（５）进行优化，设初始种群为ｅ ＝［６，３，５，１，３，１，１， １，４，１，５，２，２，３，１，２］，采用比例选择的选择方式， 设交叉概率ｐｃ＝０．８，变异概率ｐｍ０．１，最终遗传算法 优化结果如图３ 图５所示，最优配置方案中变量 取值为ｅ＝［２，５，６，１，２，１，１，２，２，２，３，２，１，２，１，３］， 过程平均响应时间最优值为ｍｉｎｔ ＝１２．２２。 厘 譬 毯 譬 ６ 结束语 本文研究了战时装备抢修实施过程中的资源 优化配置问题，以实施过程整体响应时间最短为约 束，应用排队论的方法建立了资源配置优化模型。 针对模型求解困难的问题，采用遗传算法进行求 解，通过举例分析说明模型和求解算法切实可行。 图３遗传算法得到的过程平均响应时间最优值 该方法和模型以应用在集群装备保障决策系统的 开发中，作为系统的模型支持取得了较好的效果。 参考文献： ［１］赵武奎．装备保障学［Ｍ］．北京：解放军出版社，２００３： １７２－１７５． ［２］宋光明，曹继平，宋建社，等．基于Ｒｏｕｇｈ集理论的装备维 修保障资源优化配置［Ｊ］．计算机工程，２００７，３３（４）： 变量个数（１６－） ２２０—２２１． 图４遗传算法优化的方案中各变量取值 个体间平均距离 ［３］何健敏，刘春林，曹［４］孙颖，池杰，等．应急管理与应急系统［Ｍ］．北 京：科学出版社，２００５：２－６． 宏，贾传亮．多路径下应急资源调度的非线 性混合整数规划模型ＥＪ］．运筹与管理，２００７，１６（５）：５—７． ［５］衣杨，邹腾跃，容福丽．最小化流水时间的工作流资源 优化模型和算法［Ｊ］．系统工程与电子技术，２００８，３０（７）： １２６４—１２６６． ［６］唐应辉，唐小我．排队论一基础与分析技术［Ｍ］．北京：科 学出版社，２００６：９３—９８． 遗传代数 ［７］邹明，姜礼平，苏思．基于遗传算法的航空装备保障 图５遗传算法优化的过程 资源调度［Ｊ１．兵工自动化，２００９，２８（１１）：２５—２７． ，。◆’◆。◆。◆。●’◆。◆’◆。◆。◆’◆。◆。◆。◆‘◆’ 欢迎订阅 擎迎刊登广告 ｛ ，‘ ・１６２・