６２ Ｉ Ｓｙｓ Ｐｒａｃｔｉｃｅ系统实践 Ｉ 基于蚁群算法的装备维修人力资源优化模型研究 孙文选杨宏伟杨学强 （装甲兵工程学院北京１０００７２） 摘要：针对装备维修中基本保障单元的概念，为保证在维修工作过程中，以最少的人员在固定的时间内完 成预定的维修任务，分析了修理工期与人力资源的关系，建立了固定工期人员最少的“工期人员”数学模型， 并应用基于网格划分策略的连续域蚁群算法的思想对该模型的求解过程进行了研究。 关键词：装备维修；人力资源；优化；蚁群算法 引育 维修保障体系是作战体系的重要组成部分，它对 作战能力的形成和发挥有着很强的支撑和推动作用， 人力资源作为维修资源的主要方面，在维修保障工作 中有着关键的影响。为适应平战一体化建设，在装备维 修领域提出了平战兼容的“基本保障单元”概念，对于 保障力量的平时使用、平战快速转换以及与战时上级 加强力量的运用等方面，具有很强的现实意义。 基本保障单元是指由人员、装备、设备、器材等要 素构成，能够独立完成指定专业维修保障任务的最小 保障单位。在执行维修保障任务过程中，如何配置保障 单元的人力资源，能够以最少人员在规定的时间内完 成修理任务是目前亟待解决的实际问题。在目前常用 的优化模型中有通过缩短关键线路来压缩工期的“工 期模型”；寻求在某一时间点下，总费用最低的“工期费 用”模型和在固定工期下，通过调整各工序的前后施工 顺序以达到资源利用最均衡的“工期资源”模型，而对 于给定工期，求人员最少配置问题还没有成熟的模型， 为此，本文在备品备件等供应充足的前提下，建立“工 期人员”模型对基本保障单元的人员数量进行优化，并 对模型的求解方法进行了分析研究。 一、人力资源优化问置描述 １、修理工期与人员数量的关系 装备维修是一个复杂的过程，在装备的维修过程 中通常涉及多工种，但在实际工作中各工种之间的工 作基本上没有交叉，所以可以将维修项目按工种分解 成若干项工作，每项工作由若干个工序节点组成，工序 节点可根据需要包括的内容可多可少，范围可大可小。 整个项目的修理工期是由各工序节点的修理时间决定 信息系统工程Ｉ ２０１０ １１ ２０ 的，所以首先讨论工序节点的修理时间与人员数量的 关系。 在设施设备完善，备品备件供应充足的条件下，节 点的修理工时是固定值，所以节点的修理时间在某个 范围内随人员数量的增加成近似直线的线性关系，但 节点不可能随人员的无限增加而工期无限缩短，当人 员数量增加到某固定值时，对时间的影响变得很小。因 为人员数量为必须取整数，所以节点修理时间与人员 数量的关系是一些离散的点，根据大量实际工作的统 计，节点的修理时间与人员关系的近似关系可以用图１ 时 问 Ｄ，ｃ 所示： ａ ｂ 人员 圈１ 节点工期与人员关系示意■ 在图中Ｄ。。表示节点的极限时间，即节点可能的最短修 理时间。 ２、工期与人员的优化模型 为了建立“工期人员”的优化模型，本文假定： １．每个节点都只有在其所有的紧前节点都结束后 才能开始，并且节点的修理工作一旦开始，就不得中 断，直至结束。 ２．节点的修理时间都在最小和最大范围内变化 ３．项目的总工期是在各节点持续时间确定的条件 下计算出来的关键线路的长度。 若某修理项目规定必须在工期内完成，要求总人 数最少，可以建立工期固定，人员最少数学模型如下： Ｍｉ ｎ Ｈ ＝Ｆ（ｆ （ｄ１），ｆ２（ｄ ）．．．．．．ｆ （ｄ ）） （１） Ｓ ．．ｔｔ＿． Ｄ ｄ？．＜ｄ．＜． Ｄ＜Ｄ＜ ？ （２） ｔ；一ｔ；＞ｄ； ｉ Ｐ（ｊ） （３） ＴＮ＜Ｔ０ （４） 其中：Ｈ 为项目所需的人数； ｄ．为节点的持续时间； ｆ （ｄ ）为节点所需的人数； Ｆ为项目的总人数与单个节点人数之间的函数关 系： Ｄ 为节点ｉ极限状态下的持续时间； Ｄ 为节点ｉ正常状态下的持续时间； ｔ．为节点的结束时间； ＴＮ为项目的实际工期； Ｔ 为项目的计划工期； Ｐ（ｊ）为节点的紧前工序集合，Ｐ（ｊ）＝｛ｊ Ｉ ｊ工序为工 序ｊ的紧前工序ｌ。 约束（２）是对节点修理时间的约束，保证节点的修 理时间在允许的范围内，约束（３）是工序约束，保证节 点的施工顺序符合逻辑关系。约束（４）是对工期的约 束，因为在求解时约束（４）很难处理，所以引入罚函数 的概念，把工期约束转换为罚函数Ｍ，ｍａｘ ｆ０，Ｔ －Ｔ。】，其 中Ｍ为充分大的正数，于是目标函数转化为： Ｍｉｎ ＨＴ＝Ｆ（ｆ （ｄ ），ｆ２（ｄ ）．．．．．．ｆ （ｄ ））＋Ｍ半（０，ＴＮ－Ｔ。）（５） 式中Ｍ＇ｍａｘｆ０，Ｔ 一Ｔ。）的含义是：当实际工期丁 大 于计划工期Ｔ。时，取值Ｍ水（，ＴＮ－Ｔ。），这样目标函数的值 将会非常大；当实际工期Ｔ 小于计划工期Ｔ。时，取值 ０，Ｍ￣ｍａｘ｛０，Ｔ 一Ｔ。）对目标函数无影响。采用罚函数的 主要目的就是为了避免实际工期大干计划工期的情况 出现ｌ１］。 目标函数中，总人数与各节点人数的函数关系Ｆ 可以利用时标网络计划法进行计算，即编制时标网络 后，通过逐时段人员需要量叠加的方法，确定各时段的 人员需求量，目标函数的取值Ｈ 就是所需人员最多的 时段的人数。 二、优化模型求解算法 １、算法的基本思路 对于“工期人员”模型，本文采用基于网格划分策 略的连续域蚁群算法的思想，转化为类似旅行商问题 （简称ＴＳＰ）。所谓网格划分就是在变量区域内打网格， 在网格点上求约束函数与目标函数的值，对于满足约 束条件的点，在比较目标函数的大小，从中选择较小 者，并把该网格点作为一次迭代结果；然后在求出的点 Ｉ如 系统实践 Ｉ６３ 附件将分点加密，再打网格，并重复前面的计算与比 较，直到网格的间距小于预先给定的精度嘲。 在本文的模型中，假设某一项目有ｎ个节点（节点 ０为虚拟节点，表示项目的开始），将每一个节点时间变 量分成Ｎ等份，这样共有（Ｎ＋１），Ｉｃｎ个子节点，图中每一 个子节点表示一个对应的人数（０对应节点持续时间下 限ｔ Ｎ对应节点持续时间上限ｔ～，在初始状态下分 别等于极限状态下的持续时间和正常状态下的持续时 间），如图２所示。这样，节点ｉ位于第ｋ个子节点时， 对应时间为：ｔｉｋ＝ｔ．Ｎ＋ｈｊ（Ｎ－ｋ），对应的人员数量为：Ｈ． ＝Ｈ ＋ｈｌｌｏ．ＡＨｉ。。ｋ（其中ｈｊ＝ｔ￣一ｔ ． Ｎ，△Ｈ，∞，，是图１中ａｂ段 的斜率，正常为负值）。图２中的边采用三元组表示， （ｉ，ｊ ，ｊ ）表示第ｉ个活动位于第ｊ 个网格点上，第 ｉ＋１个活动位于第ｊ 个网格点上。这样工期人员模型 实际上就是从第０列到第ｎ列找出一条线路，使项目 的总人数最少。 黼０ 商 １节 ｉ ｉ十１ 晾“ ④①①①① ①①①④ｌ ④④④④ｌ：Ｉ ：Ｉ Ｉ：…：ｉ ｌ ● ①①①① 圈２工期人员优化问■的 行青问■寰示 ２、求解的步骤 对于本文“工期人员’模型的改进蚁群算法的步骤 如下： １．确定各节点时间变量的取值范围： ｔｉ ｉ ＜ｔｉ＜ｔｊ （ｊ＝ｌ，２，．．．．．．ｎ）。 ２．将各节点的时间变量分成Ｎ等份， ＋ 一＋ ｈｊ＝ （ｊ １，２，……ｎ）。 ３．若ｍａｘ（ｈ，，ｈ ．．…ｈ ）＜ｓ（其中ｓ为定义的 ‘ －Ｊ．４－ 精度），则算法停止，最优解为ｘ （ｊ＝１，２，…… ｎ），否则跳到第（４）步。 ４．确定最大循环次数Ｎ一和蚂蚁数ｎ，给图２中各 边（ｊ，ｊ ，ｊ ２）的信息素 ，ｊ ，ｊ 赋予相同的初值，采用 随机方法产生初始解。 ５．循环次数Ｎｏ＝Ｎ￣＋Ｉ，为每只蚂蚁搜索出的线路根 据关键线路法（ＣＰＭ）求出项目的工期Ｔ，并根据（５）求出 项目所需的人员数Ｈ，记录人员数最少的蚂蚁路径作为 问题的解。 ６．经过一次循环后，各边的信息素强度按以下公 式更新： ｉＩ ６４ Ｉ Ｓｙ Ｐｒａｃ￣ｃｅ系统实践 Ｔ｜ｊ１ ２（Ｎ。＋１）＝（卜ｐ）・Ｔ ｌｊ． ２（Ｎ。） （６） 工期为１５９０小时，人数为１０人，而极限状态下可能的 最短工期为９６０小时，所需人数为１６人。由于各方面 式中：Ｔｉｉ１ｊ２（Ｎ。），Ｔ ｉｊ，ｊ２（Ｎ ＋１）分别表示第Ｎ。次和第 Ｎ。＋１次循环后各边的信息素强度；Ｐ为［０，１］之间的常 数，表示路径上信息素的挥发因子；ｆ表示此次循环后 的需求，此修理工作要求必须在１２００小时内完成，求 所需的最少人数是多少。 采用Ｍａｔｌ ａｂ仿真进行求解计算，根据图（３）的算 法流程进行编程，并设定算法的参数如下：Ｎ ＝５０， ｎ＝２０，Ｐ＝Ｏ．１，ａ＝１，Ｂ＝１， ＝１０程序运行结果如表１ 的人数Ｈ。若此次循环蚂蚁没有经过边（ｉ，ｊ１，ｊ ２），则值Ｑ／ｆ 为零。 ７．蚂蚁按照留在各边上的信息素强度以及各边的 可见度选择路径。各边的选择概率按下式计算： Ｐ （７） （ＴｉＩ１＇ｋ） （Ｔ１ｉｊｌ，ｋ） Ｋ＝０ 式中：ａ。１３是用于调节信息素与路径可见度之间的 关系的参数， ｊ２为边（ｉ，ｊ１，ｊｚ）的可见度，表示搜索过程中 的局部信息，ｑｉｊｌｊ２＝１／Ｈ ｊ２（Ｈ１．１Ｊ ２表示节点ｉ＋１采用第ｊ２ 个方案时的人数）。 ８．对每只蚂蚁按照（７）选择下一节点，并根据（６） 更新信息量。 ９．若Ｎ。＜Ｎ一，则跳转第（５）步；否则，假定最优路径中每 个活动所对应的时间网格点依次为 ，ｍ …．ｍｒ），缩小变 量的取值范围：ｔ ｎ：ｍａｘ（ｔ ｔ川 ｊ－△）ｈｊ），ｔ －－ｒｌｉｎ （ｔ ＋ ．＋ ｈ ｔ ，（ｊ＝ｌ，２，……ｎ），跳转到第二步。 工期人员优化模型问题的算法流程女１３图３所示： 三、实例应用 假设某一维修工作，其工作节点的逻辑关系及参 数如图４所示，正常人数和正常时间是指正常工作条 件下的参数，在此例中可以得出正常情况下项目的总 信息系统工程２０１０ １１ ２０ 所示： 裹１闫一求解量优结果 工序 程序运行结果（保留一位小数） 人数 人数取整 修理时间（小时） １—２ ２６２ ３ ４ ８ ５ ２ ３ ４６２．０ １．９ ２ ２ ４ ３１４ ９ ２ ８ ３ ２—５ ４４８ ６ ４．８ ５ ３—６ ３７２ ５ ４．９ ５ ４—７ １８２ ８ ２．９ ３ ５—８ ２４８ ６ １．９ ２ ６ ８ ２３５．９ ４．２ ４ ７—９ ３９３．４ ３．９ ４ ８ ９ ２３２ ６ ２．７ ３ 从程序运行结果，根据关键线路法求出该项目的 完成时间为１１９２．１工时，所需最少人数为１３人。 四、结束语 装备维修在现代战争中的地位越来越重要，而在 战时，装备的维修时间是关心的首要因素。本文针对装 备维修的性质，在装备维修网络图的基础上提出了“工 期人员”的优化模型，并应用改进的蚁群算法对要求的 时间内完成规定装备维修任务的最小人数问题提出了 相应的求解方案，对装备维修保障工作具有一定的现 实意义。 鞠 参考文献 ［１］胡华选。网络计划工期费用优化及其蚁群算法 【Ｄ】．大连：大连理工大学，２００７． ［２］段海滨．蚁群算法原理及其应用［Ｍ］．北京：科 学出版社，２ Ｏ０５． ［３】李万庆，孟文清，等．工程网络计划技术［Ｍ］． 北京：科学出版社，２ ００９． ［４］Ｄｅｒｏ Ｊ，Ｓ ｉ ａｒｔｙ Ｐ．Ｃｏｎｔ ｉｎｕｏｕｓ ｉｎｔｅｒａｃｔ ｉｎｇ ａｎｔ ＣＯ１ｏｎｙ ａ １ｇｏｒ ｉ ｔｈｍ ｂａｓｅｄ ｏｎ ｄｅｎｓｅ ｈｅｔｅｒａｒｃｈｙ ［Ｊ］．Ｆｕｔｕｒｅ Ｇｅｎｅｒａｔｉｏｎ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ，２００４，２０ （５）：８４１—８ ５６． ［５］傅英定，成孝予，唐应辉．最优化理论与方法 ［Ｍ］．北京：国防工业出版社，２ＯＯ８． ［６］邢文训，谢金星．现代优化计算方法［Ｍ］．北 京：清华大学出版社，１ ９９９．
