关于带任务约束条件的设备维修指派模型及算法研究

　　关键词:指派问题　任务约束　多目标优化
　　摘要:本文针对生产中的设备维修管理和战时武器装备维修保障中的一类带任务约束条件的维修指派问题进行了讨论,建立了维修任务指派模型,提出了采用剔除无效元素法构建新的效益矩阵,并结合此类指派问题对多目标模糊匈牙利算法进行了改进,最后通过一个例子对该算法进行了验证。
　　在企业生产过程中的设备维修管理,产品售后的维修服务以及战时军事装备的维修保障中,决策机构经常面临着如何给故障设备(或装备)进行维修任务指派决策,使完成任务的总效益最大(或所需时间和费用最短)的问题。在其具体的决策过程中,决策者往往需要考虑的因素很多,如时间、效益、风险、安全性、机动性等,[1-5]对上述问题提出了解决方法。但上述方法主要针对各个不同的人(或机构)都能够完成不同的任务,然而在实际决策中还要考虑一些任务约束条件,使得最后完成某项任务具有实际意义。比如指派任务时有时间约束、机动性约束,只有符合这些条件的人(或机构)被指派才有意义。因此本文通过对带有一定任务约束条件的任务指派模型的分析,提出了一种解决此类问题的有效方法。
　　1问题描述
　　设有n项任务欲安排n个人(或机构)去做,在指派的过程中需考虑的因素有p个,已知在第k个影响因素条件下,第i个人(或机构)完成第j项任务的目标属性值为任务约束条件是:第j项任务要求第k个目标属性值符合,每个人安排一项任务,每项任务只有一个人完成。试确定各目标均最优的指派方案。其数学模型描述为设决策变量
　　
　　式中,M’对于值越大越优的目标表示最大值,对于值越小越优的目标表示取最小值。
　　由于存在k目标下的任务约束条件,需要对不符合任务约束条件的元素进行剔除,因为如果该项被指派选中,是不具有实际意义的。记不符合k目标任务约束条件的。其代表含义对于目标属性值越小越优的,表示无穷大;对于目标属性值越大越优的,表示无穷小。则原在目标k条件下的属性值矩阵Ck转化为C’k是需要的具有实际意义的k目标属性值矩阵。
　　
　　2求解算法
　　对于求解多目标的任务指派模型,比较有效的解法是模糊指派匈牙利算法。其具体解题思路是:根据矩阵Ck求出在目标k条件下的各属性值对“优”的模糊相对隶属度rijk,对值越大越优和值越小越优的目标分别应用公式(4)(5)[6]:
　　
　　式中ckmax、ckmin分别表示矩阵Ck中元素最大值和最小值。根据以上公式将属性值矩阵Ck变为目标k条件下关于“优”的模糊关系矩阵。假定目标权向量W=w1,w2,…,wp*+,令
　　
　　称rj为综合考虑p个目标后属性值对“优”的合成隶属度。这样n×n个rij组合成多目标模糊关系合成矩阵R,=rij*+n×n。R,的每一个元素rij也可理解为第i个人完成第j项工作时的模糊综合效益,其值越大越优。但是,对于求解本文讨论的带有任务约束条件的多目标指派问题,由于解题时考虑的是符合约束条件、具有实际意义的目标属性值矩阵C’k,C’k中含有无穷小(或无穷大)的属性值,用公式(4)(5)计算模糊隶属度rijk’时,ckmax、ckmin分别表示剔出了不符合约束条件的属性值(无穷小或无穷大)之后的元素最大值、最小值,同时对于属性值矩阵C’k中的!元素,其相对模糊隶属度为无穷小,记为0。最后得到将属性值矩阵C’k变为目标k条件下关于“优”的、有约束条件的模糊关系矩阵R,’k=rijk’*+n×n。由于在进行任务指派时,选中的是具有满足各个任务约束条件的人,而各个任务约束条件相当于一种串联关系,只要一项不符合要求就不能考虑指派其完成任务,因此在采用(6)式计算合成模糊隶属度时,只要存在某一rijk=.0,则rij=pk=1-wkrijk=0.,表示其模糊隶属度为无穷小。此后在利用匈牙利算法进行造“0”矩阵时,0.元素不变化,视其虽然参与了矩阵行、列的加减运算,但其值永远是无穷小。
　　由于最后得到的模糊合成效益矩阵R,’是目标最大化的指派问题,因此采用匈牙利算法求解时,须将目标最大化转变为目标最小化,即将maxni=1-nj=1-r’ijxij转变为求minni=1-nj=1-r’ijxij。其中r’ij=M-r’ij,M为矩阵R,’中最大的元素,而对于.0元素这样处理:M-.0=∞,表示该项代价无穷大,在进行匈牙利算法求解时不可能被选中。
　　3数值例子
　　某维修机构有4个综合维修机动小组(记为A1,A2,A3,A4),现对4个作战单位(B1,B2,B3,B4)进行维修保障支援,由于影响维修保障任务完成的因素很多,这里主要考虑维修小组的维修时间、安全性和机动性等三个影响因素。设在三个影响因素条件下不同的维修机动小组完成不同作战单位维修任务的属性值矩阵分别为T(维修时间)、Q(安全性)和F(机动性),矩阵中行代表某一维修小组完成不同任务的属性值,列代表不同维修小组完成某一任务的属性值,完成B1,B2,B3,B4等维修任务的约束条件分别为tB1≤6,qB1≥0.60,fB1≥0.65;tB2≤11,qB2≥0.65,fB2≥0.70;tB3≤7,qB3≥0.65,fB3≥0.75;tB4≤9,qB4≥0.67,fB4≥0.65。试问如何进行任务指派,才能使总的效益最大并符合约束条件要求。
　　
　　解题思路:本例属于多目标任务指派模型。首先根据约束条件构建新的效益矩阵.T’,Q’,F’/,然后分别求出它们在各目标条件下关于“优”的模糊关系矩阵,R0’T,R0’Q和R0’F(注意:此时tmax=11,tmin=3,而对于!元素的相对隶属度为01,表示为无穷小),再假设各目标权向量取等权重,利用公式(6)求的模糊关系合成矩阵R0’,再将最大目标转化为最小目标R0",最后运用匈牙利算法求得指派矩阵X。即A3完成B1,A4完成B2,A2B3完成,A1完成B4。
　　
　　4结束语
　　本文对一类带有任务约束条件的故障设备(装备)维修指派问题构建了数学模型,提出了一种采用剔除不符合任务约束条件元素的方法,对多目标模糊匈牙利算法进行了改进,有效地解决了传统匈牙利算法求解此类问题得到的不符合约束条件的无效解,思路清晰,方法简便实用,并利用两个数值例子进行了验证。
　　:
　　[1]宋业新,等.多目标广义指派问题的模糊匈牙利算法求解[J].海军工程大学学报,2000(5):77-80.
　　[2]黄德才.求广义指派决策问题最优解的有效算法[J].控制与决策,1999,14(3):272-275.
　　[3]刘晓红,等.基于模糊关系的人力资源管理工作分配算法[J].软,2003,17(4):62-64.
　　[4]花文健.应急机动通信兵力派遣问题的通用模型[J].空军工程大学学报,2003,4(4):38-40.
　　[5]胡劲松.模糊指派问题求解方法研究[J].系统工程理论与实践,2001(9):94-97.
　　[6]陈守熠.系统模糊决策理论与应用[M].大连:大连理工大学出版社,1994.
　　[7]董肇君,等.系统工程与运筹学[M].北京:国防出版社,2003.