评价网 > 科教论文 > 毕业论文范文 > 正文

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

2017-08-22 01:25 　　 　　关键词:指派问题　任务约束　多目标优化
　　摘要:本文针对企业生产中的设备维修管理和战时武器装备维修保障中的一类带任务约束条件的维修指派问题进行了讨论,建立了维修任务指派模型,提出了采用剔除无效元素法构建新的效益矩阵,并结合此类指派问题对多目标模糊匈牙利算法进行了改进,最后通过一个例子对该算法进行了验证。
　　在企业生产过程中的设备维修管理,产品售后的维修服务以及战时军事装备的维修保障中,决策机构经常面临着如何给故障设备(或装备)进行维修任务指派决策,使完成任务的总效益最大(或所需时间和费用最短)的问题。在其具体的决策过程中,决策者往往需要考虑的因素很多,如时间、效益、风险、安全性、机动性等,文献[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=∞,表示该项代价无穷大,在进行匈牙利算法求解时不可能被选中。