装备战时基地级维修作业分工优化.docx

《装备战时基地级维修作业分工优化.docx》由会员分享，可在线阅读，更多相关《装备战时基地级维修作业分工优化.docx（6页珍藏版）》请在第一文库网上搜索。

1、装备战时基地级维修作业分工优化凌海风,张 军,张 洋,彭永飞(中国人民解放军理工大学军事装备学,南京210007)摘要:为快速完成装备修理任务,根据装备战时基地级维修的特点,提出了战时基地级装备维修作业分工的数学模型，在多工种多任务维修作业分工问题的基础上给出了带时间窗口的维修作业分工问题求解方案.根据该作业分工模型,利用遗传算法的特性，将问题背景与算法相融合,运用实例进行试验及分析.试验结果表明，本文提出的方法能有效地解决装备战时基地级维修作业分工优化问题.关键词:装备维修;时间窗口；分工优化Equipment in Wartime Depot-Level Maintenance Opera

2、tions Optimization of Division ofLabourLING Hai-Feng, ZHANG Jun, ZHANG Yang, PENG Yong-Fei(School of Military Equipment, PLA University of Science and Technology, Nanjing 210007, China)Abstract: In order to accomplish the task of the equipment repair, according to the distinguishing of depot-levelma

3、intenance of equipment in war, this paper proposes a mathematical model of the division of operations in wartimeequipment maintenance. Based on many types of multi task repair operations division, it puts forwards repair operationsdivision problem solving scheme with time window. According to the mo

4、del, using the characteristics of genetic algorithm,integrating the background of the problem and algorithm, this paper tests and analyzes an instance. The results show thatthe proposed method can effectively solve the wartime maintenance operations and division of optimization problems.Key words: e

5、quipment maintenance; time window; optimization division在遂行作战或应急保障任务时，很多装备需要送到固定的修理基地进行维修.在修理基地,受损装备的维修会被按照不同的工种划分出多个子维修任务，由各专业维修小组承担.当修理基地涉及到多台装备的维修时,就需要为不同工种的各小组分派维修任务，确定各装备每个工种的维修工序,在这个过程中，就涉及到维修作业分工优化问题.进行此类问题的研究较多小久例如单专业多任务作业分工问题研究叫多专业多工种作业分工问题的研究强调维修效能评估方面的研究6久以及强调工序方面问题的研究等.这些问题的研究推进了运筹学在装备维修

6、方面的应用，为装备维修效能的提高作出了重要贡献.但研收稿时间:2014-02-10:收到修改稿时间2)14-03-26究背景都对维修时间作了完全限定，只要求整体完成时间短.而实际情况可能会出现在保证整个维修任务的效率的情况下,对某几台装备有明确的时间要求.研究此类问题即带有时间窗口限制的装备维修作业分工优化问题的文章很少.遗传算法是一类借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法它的主要特点是群体搜索的策略和群体中个体之间信息的交换,搜索本身不依赖于梯度信息.遗传算法在各个领域都得到了广泛的应用，特别是针对离散问题,其特有的模仿生物遗传基因的特色可以发挥出更加好的效用.本文

7、运用了遗传算法对模型进行求解,设计了相为0.为不失一般性，我们还假设每台装备针对某工种的维修作业都只安排一个该工种的维修小组,并假设针对任一维修作业,基地的维修设施设备足以满足任意多的装备并行修理的需要.根据以上条件,优维修作业分配方案要求所有维修任务能够尽快完成，使整个维修任务完成时间短,每个方案需要明确各装备各工种的维2014 年第 23 卷第 9 期http:/www.c-s-应的算法规则，保证了求解的效率及其良好的收敛性.1维修作业分工优化模型. 一 f卜1.1 装备战时基地级维修作业分工优化问题描述后送至修理基地的受损装备，一般为重损备，需要多个维修小组进行不同E种的维穆作业，修理工

8、序多、任务重，而且时间紧，指挥部门需要给出合理的作业分工方案，安排各维修小组的维修任务、制定各装备的维修工序和各维修小组的作业顺序，以提高作业效率，在短时间内完成所有任务.这个问题可看作是车间作业调度与作业工序优化问题的结合体，是一个典型的NP问题，传统的求解方法难于求解.我们将讨论用智能优化算法求解装备战时基地级维修作业分工问题，终给出各维修小组的具体作业方案.1.2 数学模型的建立下面首先介绍基地级维修作业分工优化问誓的若干符号.假设维修任务集1=1,2,.川表示某一时刻其接到台受损装备的维修任务；维修工种集”表可基地将裹备的维修作业分为m个工种；S=1,2,s表示将设s个维修小组；矩阵R

9、表示各维修工种对应的维修小组情况,设各工种多配备k个维修小组，当某个工种的维修小组少于攵个时，用()补全矩阵；假设各维修小组由于其技术能力水平的差异，其对各损坏装备的维修作业时间各不相同,不同工种的不同维修小组对每台送修装备的装备维修时间可用3维矩阵T表示，若某台装备不需要某工种进行维修作业，则令该工种的所有维修小组对该装备的维修作业时间计算机系统应用修顺序、各装备各工种的承修小组和各个维修小组的工作次序.此问题的数学表达韭常简单*，设，为第小2口,)台装备的维修完成时间，则该问题的数学模型可表达为:“min f = max(7(z)(1)冏LM装备战时基地级维修作业分工优化是一个典型的COP

10、问题解决这类问题的一个重要思路是运用智能算法求解,而遗传算法适用于求解传统搜索方法所难以解决的非线性组合优化问题.基于此,我们选用遗传算法来求解装备战时基地级维修作业分工优化问题.2算法规则及流程 人 2.1 染色体的编码针对维修作业A工优化问题,我们选择一种基于整数编码方式的多层编码方淳.对于台装备，个工种的维修作业分工问题，对应的编码是一个长度为3*?*的向量P,这个向量由两部分组成，前个元素表示的是整个维修作业的次序,用向量P、，表示,向量元素为1之间的整数，为待修装备的代号，每个数值出现相次，代表其由不同的维修小组进行了 m道工序的维修.后面的个元素由矩阵Pr转化而来，矩阵的每一行有2

11、m个元素，所在的行数表示对应的装备代号，前加个元素表示该装备的维修工序，用1机之间的整数表示，后“个元素表示相对应的维修小组的代号.通过这样的编码方式,可以将各个维修小组的维修方案都表示出来.在Pv和Pr都编码完成后，将其整合成一个总的向量P,具体方法是将Pr的各行按1的顺序依次连接，得到一个的向量P,再与Pv连接，从而得到终的向量P.2.2 种群初始化遗传算法可以执行下去的前提是所有染色体代表的解必须是可行解.因此,在产生初始种群时，也必须要达到这个要求.从上文中的编码方案可知编码分为两部分,因此，种群初始化时，种群大小设为N,也可以分成P、.、Pr两部分进行初始化.2.3 适应度值计算在进

12、行选择操作之前，需要对所有染色体进行适应度值计算，为选择操作提供依据.在这里讨论以下两种情况：1)在对某些装备返回战场时间没有特殊要求的情况下，适应度值可定义为完成所有装备维修任务的时间，则适应度函数可表示为：fitness = max(71：(/) , zel,n (2)其中2为第i台装备完成维修的时间.2)决策人员在进行战时基地级维修作业分工优化的时候，另一种典型的情况是某台装备或者某几台装备Software Technique Algoritlim 软件技术算法 163的维修完成时间有明确的时间限制，要求在某个规定时间内完成，也就是所谓的时间窗口 (Time Window).针对这种情况

13、，可以将这个时间约束以惩罚函数的形式并入到适应度函数中，然后再进行计算.例如,要求装备i在Z时间内完成,则我们可以将适应度函数改为：fitness - max(工(i)+ (max(7(/),7)-7)* 105 (3)其中，(maxd(/)7)-7；)*105为惩罚函数,当装备，的实际维修完成时间超过不时，在惩罚函数的影响下，fitness的值就会变得非常大，使之不会成为优，这样的染色体在选择中就会被淘汰.2.4 选择选择“2,操作对于种群从一代更新到下一代起着重要的作用.这里根据模型特点提出一种选择方案：在初始化结束和交叉、变异运算结束后，对所有父代和子代染色体进行适应度值计算,而后按照适

14、应度值对所有染色体进行排序，预先设定一个选优概率为如果种群大小为N,则首先选中排序结果中的前N*P,个染色体,然后再从剩下的染色体中随机选择(N - N *PJ个染色体，由这些染色体合在一起组成新一代的种群.这样的选择方案,既充分发挥了遗传学中“优胜劣汰”的原则,又保持了 “生物多样性”,以避免算法局部收敛.2.5 交叉交叉时，以一定的交叉概率按照轮盘赌策略选择父代染色体.在具体执行交叉时，依然分Pv和P,两个部分进行.在交叉函数中，将两个编码向量P1和P2按编码整合的相反策略拆分为Pvl Pv2和PrH P2,分别进行交叉运算.交叉方法使用整数交叉,方式为两点交叉的方式，即随机选择一个起始位

15、置和一个结束位置，将P、“和P、，2相应位置间的数值进行互换,完成交叉操作.在交叉结束后，会出现这样一种情况,交叉前染色体中各基因的数量和交叉后的不尽相同.某些装备代号多余,某些缺失,需要对染色体进行检查和调整,将多余的基因变成缺失的基因.例如，有染色体Pvl和Pv2如下：Pvl: 33244211Pv2: 42321341选择第5位到第7位进行交叉，交叉后得到Pvi和Plv2,此时就会发现需要将交叉后的Plvl逐位地与交叉前的P、2进行比较，当P1中的某一位上的代码与PQ中相同时,将这两个代码都变为0.整个对比完成后,两个染色体变为：PPvi： 00000300PPv2：00020000 依次将P%中与PP%中的非0代码相同位置上的代码用 PPv2中的非0代码替换,完成两者交叉运算.对