精华内容
下载资源
问答
  • 多无人机(UAV)协同任务分配

    万次阅读 多人点赞 2019-03-22 13:33:53
    1.协同任务规划的功能与结构 ... 通常多无人机任务规划可以分成两大部分:上层的任务分配(Task Assignment or Task Allocation)和下层的路径规划(Path Planning), 任务分配考虑各种约束条件,...

    一.协同任务规划的功能与结构

    多无人机协同任务规划即是根据一组特定条件的约束,以实现某个准则函数的最优或次优为目标,将某项作战任务分解成一些子任务并分配给多无人机系统中的各个无人机分别去完成的过程。 通常多无人机任务规划可以分成两大部分:上层的任务分配(Task Assignment or Task Allocation)和下层的路径规划(Path Planning)

    任务分配考虑各种约束条件,以总体任务有效达成为目标,将具体目标和行动任务分配给各机,而各机根据分配的任务再进行具体的作战路径规划。

    而路径规划的功能是在满足如最大线性速度、最大转角速度、操作的安全性、时间和环境变量等自身或外部限制的前提下在一系列位置之间设计或生成路径。同时,多无人机协同任务规划系统本身又是整个多无人机协同控制系统的重要组成部分。

    二.任务分配

    按照无人机作战任务之间的相关联性,可归类为
    1.独立任务分配
    2.协同任务分配
    按照无人机作战任务所处环境可分为
    1.静态任务分配
    2.动态任务分配
    按照分配方法可分为
    1.集中式任务分配
    2.分布式任务分配
    3.分层式分布任务分配

    协同任务分配

    多无人机协同任务分配的目标是在考虑各种诸如任务执行顺序、时间、无人机自身物理条件等约束条件的前提下,以总体任务效率最优或次优为目标,离线地或实时地将具体目标和行动任务分配给各机。

    三.建模

    以集中式控制系统为基础进行任务分配最常用的模型有
    多旅行商问题(multiple traveling salesman problem,MTSP)模型[13]、
    车辆路径问题(Vehicle Routing,VRP)模型[14]、
    多机路径分配模型(mVRP)[19]、
    混合整数线性规划问题(Mixed-Integer Linear Programming ,MILP,)模型[15]、
    动态网络流优化(Dynamic Network Flow Optimization ,DNFO)模型[16]、
    多处理器资源分配问题模型(Multiple Processsors Resources Allocation ,CMTMP)模型[17]
    除了上述模型外,美国空军研究实验室在无人机任务分配研究中建立了
    带时间窗的不同能力约束车辆路径问题(CVRPTW,Capacitated Vehicle Routing Problem with Time Windows)

    四.方法

    1. 集中式任务分配方法

    集中式控制系统就是编队中的无人机之间的通信、信号的传输和控制均由唯一的一个控制中心来进行。
    常用的模型有MTSP、VRP、MILP、DNFO、CMTAP。

    1.1最优化方法

    (1)穷举法,适用于离散且规模小的情况
    (2)整数规划法(Mixed-Integer Linear Programming,MIP)根据既定的目的和目标,通过建立目标函数和约束条件的方法对规模较小的任务分配问题进行解决的一种最优化方法矩阵作业法、单纯型法、匈牙利法、分支定界法等是比较常用的整数规划方法。
    (3)约束规划(Constaint Programming CP)方法由变量集和约束集两者组成,变量集内的所有变量都有自己对应的值域,且变量的取值也只能从其值域中选取,它是求解组合优化问题的一种通用方法。
    (4)图论方法是通过图示的方法把任务和接受任务的成员特征表述出来,同时在任务和系统成员之间用图论方法建立匹配,以此设计出合理可行的任务分配方案。网络流模型和偶图匹配模型是两种经典的图论任务分配模型。

    1.2启发式算法

    在能够接受的时间范围内求得局部最优解或满意解。
    (1)列表规划(List Scheduling,LS)方法的步骤是首先建立任务的优先权函数,求得任务的处理次序,然后按照求得的任务处理次序将任务分派给系统成员。最常见的列表规划方法有动态列表规划(Dynamic List Scheduling ,DLS)法、多维动态列表规划(Multi-Dimensional Dynamic List Scheduling,MDLS)方法、多优先级动态列表规划(Multi-Priority List Dynamic Scheduling ,MPLDS)等。
    (2)智能优化算法
    ①进化算法EA 遗传算法GA 遗传规划Genetic Programming-GP 进化规划Evolutionary Programming-GP等
    ②群智能算法 PSO ACO
    ③人工免疫、禁忌搜索、模拟退火。

    2.分布式任务分配

    分布式控制系统与集中式控制系统不同的是实现信号传输的方式,前者无人机还可以在编队内进行通信,具有更好的灵活性。分布式控制系统结构相比集中式控制系统结构来说对无人机的要求更高,需要无人机具备独立计算、分析与决策等能力。

    2.1合同网方法

    目前,合同网(ContractNet)是应用范围最广的一种分布式任务分配方法,它的核心是为防止产生冲突,对每个问题的求解用通信的方式协商处理。[25]
    合同网方法有发布者和竞标者两个角色,由“招标- 投标- 中标- 确认”4 个交互阶段组成。在合同网协作方法中,系统成员的角色不用提前规定,任何系统成员可以是管理者,也可以是工作者,区别只在于成员是发布任务通知还是应答任务通知,于是任务能够被层次地分解分派。这种方法的缺点是通信量大、作为发布者的系统成员工作强度大且任务分解分配没有有效融合等。

    2.2 拍卖方法

    拍卖方法是实现资源配置的一种市场机制,指的是买方在清楚了解拍卖规则的前提下,采用竞价的方式决定特定物品的价格,也就是将要拍卖的物品用公开竞价的方式转卖给应价最高( 最低)者的一种交易方式。一个拍卖主要由参与方、拍卖品、收益函数和应价策略4 个要素组成,在无人机任务分配问题中,无人机需要执行的任务可视为拍卖品,无人机的任务分配方和任务接受方共同组成参与者,且双方都有各自对应的收益函数和出价策略。拍卖方法是一种协商协议,因其规则明确且便于操作,近年来受到越来越多学者们的关注。拍卖方法用明确的规则引导买卖双方进行交互,可操作性非常强,能在较短时间内将资源合理分配,得到问题的最优解或较优解。该方法现已广泛运用在无人机作战和传感器等资源分配问题中。

    综述

    文献[1] 将任务分配方法归纳为集中式任务分配、分布式任务分配、分层次分布式任务分配三类,并对方法进行了简单阐述,提出了几个任务分配的可能的未来发展趋势。

    文献[6]归纳和总结了多无人机协同任务规划的国内外研究现状,重点总结了任务分配方法的常见模型和算法,对各种算法的优缺点进行了讨论,得出多智能体的市场机制类算法在空战中将有广泛的应用价值。

    模型

    文献[5]探索了对不同种类的目标进行侦察、打击和评估任务时异构无人机的协同任务分配问题。对于侦察与评估任务中所得到的信息量,运用信息论中熵的变化量对其进行度量,把无人机对不同类型目标的打击能力简化为对目标的毁伤概率,同时把每个任务之间的关联性考虑在内,建立了异构多无人机协同任务分配模型。

    文献[7]建立了以合同网协议和多智能体系统理论为基础的有人机/ 无人机编队MAS(Multi-agent System MAS)结构和基于投标过程的无人机任务分配模型。

    文献[23]提出了集群组网任务分配模型和任务分配求解算法。分析了集群组网的任务分配问题,并剖析了任务分配分层递阶结构;借助层次分析思路,建立了集群组网任务分配模型;结合群体智能优化算法的优势,提出了基于PSO-ICWPA 的集群组网任务分配算法;

    同构

    文献[20]针对较为真实的战场环境,将避障约束、禁飞区约束、任务执行时间窗口约束、任务执行次序约束等加入到CMTAP模型中,建立了较为完整的UAV协同任务分配模型, 但忽略了UAV间的避碰约束、UAV的异构性、任务执行时间约束等。

    1.蚁群

    文献[8]在无人机协同多任务分配的研究中,运用了基于分工机制的蚁群算法进行求解,并给出了基于作战任务能力评估的问题解构造策略和基于作战任务代价的状态转移规则,大幅度提升了算法的性能。

    2.粒子群

    文献[11]设计出一种多无人机任务分配与航迹规划相结合的整体控制架构,假设威胁和障碍区域为合理的多边形模型,使用改进的算法求出两个航迹点之间的最短路径,将此路径当成任务分配过程全局目标函数的输入,然后用粒子群优化任务分配迭代寻优。

    文献[10]在基于任务依赖关系和ISO–DATA(Iterative Self-organizing Data Analysis Technique)算法相结合的基础上设计了新的任务分组方法,在保持无人机负载均衡的基础上,给出了基于资源福利的任务组级组粗粒度的无人机任务分配方法,在任务组内提出了结合粒子群算法的细粒度任务分配算法。

    文献[21]通过综合考虑多无人机任务分配约束条件,以多UCAV 总飞行航程和多UCAV 总飞行时间两个关
    键指标作为任务分配方案的评价标准,构建多无人机任务分配模型,采用改进的QPSO 算法进行优化求解多无人机任务分配问题。

    文献[22],综合考虑了协同多任务分配问题的任务优先级和任务协同约束、任务时间约束,同时针对无人机载弹量有限的实际情况,将无人机的载弹量约束等同于无人机执行攻击任务的最大次数限制,建立了协同多任务分配模型,在算法引入自组织惯性权重和加速系数,增强了算法的全局和局部搜索能力,优于遗传算法的协同多任务分配。

    GA

    文献[20]针对较为真实的战场环境,将避障约束、禁飞区约束、任务执行时间窗口约束、任务执行次序约束等加入到CMTAP模型中,建立了较为完整的UAV协同任务分配模型, 用整数规划法MIP和遗传算法求解。但忽略了UAV间的避碰约束、UAV的异构性、任务执行时间约束等。

    文献[24]针对战场环境的多目标、多任务以及无人机能力有限等特点,设计了一种适应于多目标、多无人机、多任务种类的无人机群协同多任务分配模型。结合该模型以及其中的任务偏序约束、协同任务约束、无人机能力约束等约束条件提出了基于任务序列的遗传算法染色体编码方法,和基于同类任务的遗传算法交叉、变异算子。该方法利用遗传算法的全局搜索优化解特点,对无人机群的协同任务分配进行优化.

    动态及不确定环境下

    文献[12]分析了实际战场上信息的不确定性,同时指出了在此条件下多无人机面临的任务分配问题。将收益毁伤代价指标、目标价值及航程代价指标的不确定信息作为参考依据,在此基础上建立了基于区间
    信息环境下多无人机的任务分配模型,采用随机概率的多属性方案排序(Stochastic Multi-criteria Acceptability Analysis,SMAA)方法,得出不确定环境下多无人机动态任务分配求解方法。

    文献[3]建立了多UCAV任务分配模型,对动态重分配策略进行研究并做出改进,将周期性重调度和事件驱动重调度进行有机结合。提出了一种改进的混合重调度策略.增加了对突发事件的处理能力,并结合粒子群算法和细菌觅食算法的优缺点。提出了混合细菌觅食算法(PBFO)解决多UCAV的动态任务分配问题。

    异构

    文献[9]以异构类型多目标多无人机任务分配问题为原型,设计了一种基于时间窗的多无人机联盟组任务分配方法,此算法使用冲突消解机制来防止无人机实时任务分配过程中出现多机资源死锁,其次通过无人机两阶段任务联盟构成算法,组成了任务联盟,使无人机任务分配的有效性和实时性有了很大的提高。
    文献[18]以多异构无人机执行SEAD任务为背景采用图论的方法完成问题的建模,将无人机本体等效为Dubins Car模型,并对其在相应目标处执行侦查、打击、评估任务时的进入角度进行约束,通过Dubins路径完成对无人机飞行路径的等效,采用分布式遗传算法完成对问题的快速求解.

    文献[4]基于文献[20]的研究成果,将模型适用范围扩展到了异构UAV,但对约束条件的假设仍然相对理想.

    引用文献任务空间特性建模方法约束条件算法求解架构
    [3]同类UAV

    文献

    [1]陈侠,乔艳芝.无人机任务分配综述[J].沈阳航空航天大学学报,2016,33(6):1-7. DOI:10.3969/j.issn.2095-1248.2016.06.001.
    [2]李炜,张伟. 基于粒子群算法的多无人机任务分配方法[J].控制与决策,2010,25(9):1359 -1364.
    [3]杨尚君,王社伟,陶军, 等.动态环境下的多UCAV协同任务分配研究[J].电光与控制,2012,19(7):32-36,79. DOI:10.3969/j.issn.1671-637X.2012.07.008.
    [4]Wang J, Zhang Y F, Geng L, et al. A heuristicmission planning algorithm for heterogeneous tasks with
    heterogeneous UAVs[J]. Unmanned Systems, 2015, 3(3):205-219.
    [5]邸斌,周锐,丁全心. 多无人机分布式协同异构任务分配[J].控制与决策,2013,28(2):274 -278.
    [6]朱毅,张涛,程农,等.多UAV协同任务规划研究[J]. 系统仿真学报,2009(20):194 -199.
    [7]刘跃峰,张安.有人机/无人机编队协同任务分配方法[J]. 系统工程与电子技术,2010,32(3):584-588.
    [8]苏菲,,陈岩,沈林成.基于蚁群算法的无人机协同多任务分配[J]. 航空学报,2008(29):184-191.
    [9]林林,孙其博,王尚广,等.基于时间窗的多无人机联盟任务分配方法研究[J].电子与信息学报,2013,35(8):1983-1988.
    [10]谭何顺,曹雷,彭辉,等. 一种多无人机层次化任务分配方法[J]. 解放军理工大学学报(自然科学版),2014,15(1):18 -24.
    [11]孙小雷,齐乃明,董程,等. 无人机任务分配与航迹规划协同控制方法[J]. 火力与指挥控制,2015,37(12):2772 -2776.
    [12]陈侠,唐婷.不确定环境下多无人机动态任务分配方法.火力与指挥控制[J].2013,38(1):45 -49.
    [13]SECREST. Traveling salesman problem for surveillance mission using particel swarm optimization [D]. wright-PattersonAFB:Air Force Institute of Technologhy,2003.
    [14]O’Rourke K P,Bailey T G,Hill R,et al. Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search[J].Military Operations Research Journal, 2001(6):5 -30.
    [15]ALIGHANBARI M.Task assignment algorithms for teams of UAVs in dynamic environments[D].Cambridge:Massachusetts Institute of Technology,2004.
    [16]NYGARD K E,CHANDLER P R,PACHTER M.Dynamic network flow optimization modles for air vehicle resourceallocation[C]//Proceedingsofthe 2001 American Control Conference,2001,3:1853-1858.
    [17] ALVARO E G .Stability Analysis of Network-based Cooperative Resource Allocation Strategies[D].Columbus:Ohio State University,2003.
    [18]吴蔚楠,关英姿,郭继峰, 等.基于SEAD任务特性约束的协同任务分配方法[J].控制与策,2017,32(9):1574-1582. DOI:10.13195/j.kzyjc.2016.0858.
    [19] Arsie A, Savla K, Frazzoli E. Efficient routing algorithmsfor multiple vehicles with no explicit communications[J].IEEE Trans on Automatic Control, 2009, 54(10):2302-2317.
    [20]Geng L, Zhang Y F, Wang J, et al. Cooperative missionplanning with multipleUAVs in realistic environments[J].Unmanned Systems, 2014, 2(1): 73-86.
    [21]邓可,连振江,周德云, 等.基于改进量子粒子群算法的多无人机任务分配[J].指挥控制与仿真,2018,40(5):32-36. DOI:10.3969/j.issn.1673-3819.2018.05.007.
    [22]梁国强,康宇航,邢志川, 等.基于离散粒子群优化的无人机协同多任务分配[J].计算机仿真,2018,35(2):22-28. DOI:10.3969/j.issn.1006-9348.2018.02.005.
    [23]汪汝根,李为民,刘永兰,刘金松.无人机集群组网任务分配方法研究[J].系统仿真学报,2018,30(12):4794-4801+4807.
    [24]姚敏,王绪芝,赵敏.无人机群协同作战任务分配方法研究[J].电子科技大学学报,2013,(5):723-727. DOI:10.3969/j.issn.1001-0548.2013.05.015.
    [25]SM ITH R G.The Contractnet Protocol :High level Communication and Control in a Distributed problem solver [J]. IEEE Transaction and Computers

    展开全文
  • 团队管理系列-任务分配

    千次阅读 2020-12-18 17:03:53
    团队管理-任务分配 任务分配是团队管理中很重要的工作,做好任务分配才能让队员和自己都工作的更高效 最近读《李元芳升职记》,看到任务分配部分的内容,结合最近工作中出现的问题,感觉到任务分配能力的重要性。 ...

    团队管理-任务分配

    任务分配是团队管理中很重要的工作,做好任务分配才能让队员和自己都工作的更高效

    最近读《李元芳升职记》,看到任务分配部分的内容,结合最近工作中出现的问题,感觉到任务分配能力的重要性。
    中国领导者沟通容易存在问题是经常 “不要让我再说第二遍” “我说过多少遍了?” 这应该是管理沟通中存在的最大的问题。当管理者给团队成员分配任务时,不可以这样。同时,当我们把任务分配给队员,而队员没有按时保质保量完成时,我们也不能将所有责任加之于队员,而是管理人员也同样需要 因人排工。
    按照李元芳升职记书中描述的,分配任务分为以下六部。
    第一步:了解下属的性格和能力:清楚了解每一位下属的性格特点和所具备的能力,根据他们的性格特点和能力素质“因人派事”。
    第二步:与队员明确工作内容,意义,工作时限和合格标准:和队员详细沟通被分派的工作为什么要做,做什么,需要多长时间完成及做到什么程度才算完成。判断下属是否清楚这些信息的唯一标准就是让他们复述,看他们所复述的意思与我们所表达的意思是否一致。
    第三步:明确队员的权利范围和责任:让队员明确,要他们完成这些工作时,他们可以动用的资源,权利及必须承担的责任是什么。
    第四步:确认下属具有完成工作所需要的能力:确认下属具有完成被分派的工作所需要的能力,如果能力不够,一定要及时给与培训和辅导,并且在有其他可选情况下,不可以将该任务分派给不具备能力的员工,否则,后果严重。
    第五步 定期检查和监督下属的工作:通过检查监督,了解工作进展和质量,已经存在的问题,以便有机会及时改进。
    第六步 及时给出评价和奖惩:按事先确定的时间和标准及时给予评价,奖励和惩罚。

    1.因人派事 是让每个人尽量干最适合他的工作;
    2.沟通工作内容工作意义完成时限及合格标准时,一定要让队员复述,不要简单的提“你清楚了吗”这样封闭式的问题。
    3.让员工明确责权利,避免发授权和过多请示;
    4.不要只给任务不给培养;
    5.千万不可放羊。计划执行监督收尾。监督监督监督。 具体的监督是 了解进度状态,代码审查CodeReview.不做代码审查,所有偷的懒都将N倍返还。
    6.信守承诺。

    在工作的开展过程中,我们不能抱怨队员素质不高能力不够执行力不到位,公司大环境不够好,需求任务紧等问题,很多时候是管理者在分配任务时的一个或几个方面的问题造成的。一定要在分配任务上做好,否则,问题会层出不穷。

    展开全文
  • 模拟实现任务分配(模板模式)

    千次阅读 2018-08-14 12:47:59
    在实际应用中有这样一个场景:有m台服务器,有n个任务,需要把这n个任务按一定策略分配给m台服务器来执行,请按以下要求实现该场景: 1、使用List列表代表服务器(列表中每个元素为一个IP地址); 2、使用List列表...

    在实际应用中有这样一个场景:有m台服务器,有n个任务,需要把这n个任务按一定策略分配给m台服务器来执行,请按以下要求实现该场景:
    1、使用List列表代表服务器(列表中每个元素为一个IP地址);
    2、使用List列表代表任务(列表中每个元素为任务ID);
    3、分配的过程就是把IP地址与任务ID映射上的过程;
    4、策略要支持多个,如按IP地址随机、按任务数量平分等,策略需要支持可扩展(扩展时不用修改已经实现好的策略);

    1、实体类定义:

    //服务器实体类
    public class Service {
    	private String IP;
    	private String serviceName;
    
    }
    
    //任务实体类
    public class Task {
    	private Integer taskId;
    	private String taskName;
    }

    2、抽象父类定义(所有的策略实现都需要继承该类)

    public abstract class AbstractTaskAllocation {
    
    	/**
    	 * 具体的整个过程 在这里定义操作实现的步骤
    	 */
    	protected void doTaskAllocation(List<Service> serverList, List<Task> taskList) {
    		// 1、准备阶段,可以进行一些数据初始化的操作
    		this.preparation(serverList, taskList);
    		// 2、把IP地址与任务ID映射上阶段
    		Map<Object, String> serviceTaskMapping = this.setMapping(serverList, taskList);
    		// 3、结果返回阶段
    		this.getResult(serviceTaskMapping);
    	}
    
    	/**
    	 * 1、准备阶段
    	 */
    	public abstract void preparation(List<Service> serverList, List<Task> taskList);
    
    	/**
    	 * 2、把IP地址与任务ID映射上阶段
    	 * 
    	 * @param taskList
    	 * @param serverList
    	 */
    	public abstract Map<Object, String> setMapping(List<Service> serverList, List<Task> taskList);
    
    	/**
    	 * 3、结果返回阶段,分配完后续处理
    	 */
    	public void getResult(Map<Object, String> serviceTaskMapping){
    		// 分配状态查询
    		for (Entry<Object, String> entrySet : serviceTaskMapping.entrySet()) {
    			System.out.println("服务器IP: " + entrySet.getValue() + " === 任务ID: " + entrySet.getKey());
    		}
    	}
    }

    3、平均分配策略:

    public class AverageTaskAllocation extends AbstractTaskAllocation {
    
    	// 进行一些参数校验之类的
    	@Override
    	public void preparation(List<Service> serverList, List<Task> taskList) {
    		if (serverList == null || serverList.size() < 1) {
    			System.out.println("没有可用的服务器!");
    		}
    		if (taskList == null || taskList.size() < 1) {
    			System.out.println("暂无需要处理的任务!");
    		}
    	}
    
    	// 设置服务器和任务之间的隐射关系
    	@Override
    	public Map<Object, String> setMapping(List<Service> serverList, List<Task> taskList) {
    		// map key_value 的形式存储服务器和任务的映射关系 id : ip
    		//Map<Object, String> serviceTaskMapping = new HashMap<Object, String>();
    		Map<Object, String> serviceTaskMapping = new TreeMap<>();
    		// 任务平均分配 参考HashMap 的分配原理
    		int serverCount = serverList.size();
    
    		for (int i = 0; i < taskList.size(); i++) {
    			int taskAddress = i % serverCount;
    			serviceTaskMapping.put(taskList.get(i).getTaskId(), serverList.get(taskAddress).getIP());
    			//serviceTaskMapping.put(taskList.get(i).getTaskName(), serverList.get(taskAddress).getServiceName());
    		}
    
    		return serviceTaskMapping;
    	}
    
    	/*@Override
    	public void getResult(Map<Object, String> serviceTaskMapping) {
    		// 分配状态查询
    		for (Entry<Object, String> entrySet : serviceTaskMapping.entrySet()) {
    			System.out.println("服务器IP: " + entrySet.getValue() + " === 任务ID: " + entrySet.getKey());
    		}
    	}*/
    }

    4、随机分配策略:

    public class RandomTaskAllocation extends AbstractTaskAllocation {
    
    	// 进行一些参数校验之类的
    	@Override
    	public void preparation(List<Service> serverList, List<Task> taskList) {
    		if (serverList == null || serverList.size() < 1) {
    			System.out.println("没有可用的服务器!");
    		}
    		if (taskList == null || taskList.size() < 1) {
    			System.out.println("暂无需要处理的任务!");
    		}
    	}
    
    	// 设置服务器和任务之间的隐射关系
    	@Override
    	public Map<Object, String> setMapping(List<Service> serverList, List<Task> taskList) {
    
    		// map key_value 的形式存储服务器和任务的映射关系 id : ip
    		Map<Object, String> serviceTaskMapping = new HashMap<Object, String>();
    		// 设置的是随机事件 0或者1 各50%,保证随机分配性
    		// 服务器的数量,就是任务分配的概率
    		int serverCount = serverList.size();
    		Random r = new Random();
    		for (int i = 0; i < taskList.size(); i++) {
    			Integer serverId = r.nextInt(serverCount);
    			serviceTaskMapping.put(taskList.get(i).getTaskId(), serverList.get(serverId).getIP());
    		}
    
    		return serviceTaskMapping;
    	}
    	@Override
    	public void getResult(Map<Object, String> serviceTaskMapping) {
    		// 可以覆盖父类,进行一些子类特殊操作
    	}
    }

    5、测试类:

    public class TaskAllocationTest {
    
    	public static void main(String[] args) {
    		List<Service> serverList = new ArrayList<>();
    		List<Task> taskList = new ArrayList<>();
    
    		// 添加服务器
    		for (int i = 1; i < 11; i++) {
    			Service service = new Service();
    			service.setIP("10.1.10.3" + i);
    			service.setServiceName("我是第"+i+"台服务器");
    			serverList.add(service);
    		}
    		// 添加任务
    		for (int i = 0; i < 500; i++) {
    			Task task = new Task();
    			task.setTaskId(i + 1);
    			task.setTaskName("我是第"+i+"个任务");
    			taskList.add(task);
    		}
    
    		// 随机分配策略:
    		AbstractTaskAllocation randomTaskAllocation = new RandomTaskAllocation();
    		randomTaskAllocation.doTaskAllocation(serverList, taskList);
    
    		// 平均分配任务策略
    		AbstractTaskAllocation averageTaskAllocation = new AverageTaskAllocation();
    		averageTaskAllocation.doTaskAllocation(serverList, taskList);
    
    	}
    }

    6、模板模式要点(不熟悉可以去看设计模式那节)

    • 模版方法定义了算法的步骤,把这些步骤的实现延迟到了子类。
    • 模版方法模式为我们提供了一种代码复用的重要技巧。
    • 模版方法的抽象类可以定义具体方法、抽象方法和钩子。
    • 抽象方法由子类实现。
    • 为了防止子类改变模版方法中的算法,可以将模版方法声明为final
    • 模版方法和策略模式都封装了算法,一个用组合(策略模式),一个用继承(模版方法)。

     

    每天努力一点,每天都在进步。

    展开全文
  • 针对武器装备快速扩散制造环境下的任务分配问题,提出了一种基于最小费用网络流的任务分配方法。本方法以完成任务的时间及费用最少为目标,首先计算出各个零件的最大产量,其次根据零件最大产量计算出产品的最大产量...
  • 分支界限法 任务分配问题

    万次阅读 2017-01-19 21:45:36
    分配问题要求将n个任务分配给n给人,每个人完成任务的代价不同,要求分配的结果最优,此题可以使用回溯求解。 2.5.2程序使用说明 Java环境1.8.0_111 IDE:eclipse 需要两个文件Node.java,Assignment.java直接编译两...

    2.5.1题目描述

    分配问题要求将n个任务分配给n给人,每个人完成任务的代价不同,要求分配的结果最优,此题可以使用回溯求解。

    2.5.2程序使用说明

    Java环境1.8.0_111

    IDE:eclipse

    需要两个文件Node.java,Assignment.java直接编译两个文件,然后直接运行Assignment.java文件,在控制台查看结果。

    2.5.3简要分析和设计

    假设存在四个人a,b,c,d,任务1,任务2,任务3,任务4,和对应的代价矩阵如下

     


    图二 矩阵(来源于算法设计与分析基础第三版)

    采用分支界限法,需要计算最优边界Lb,Lb=已分配任务的代价+剩余未分配任务中最小的代价,然后构造状态空间树,上面例子的状态空间树如下:

     

    图三  空间树(来源于算法设计与分析基础第三版)

    开始节点表示还未给任何人分配任务,然后在开始节点的基础上寻找可扩展节点,由于此时a有四种选择,则有四个扩展节点,然后分别计算可扩展节点的lb,如果lb小于cost,则将其加入优先队列,然后从优先队列中选择一个最优的,作为新的扩展节点,然后在当前节点的基础上为继续进行上述步骤,当有一个节点的状态表示为已将四个节点分配完成,且花费的代价小于已有cost,则更新cost值,然后继续从优先队列里增加值和取值,直到优先队列为空,则最小花费即为最优选择。

    2.5.4测试用例

      {{9, 2, 7, 8},

    {6, 4, 3, 7},

    {5, 8, 1, 8},

    {7, 6, 9, 4}}

    结果:

    人员以此选择工作为:2 1 3 4

    最小花费:13

     

    2.5.5源代码

    目录结构:

     

    package three.one;

    import java.util.ArrayList;

    import java.util.Comparator;

    import java.util.PriorityQueue;

    /**

     *

     * @author ym

     *

     */

    public class Assignment {

    //对应花费

    private int[][] cost={

            {9, 2, 7, 8},

            {6, 4, 3, 7},

            {5, 8, 1, 8},

            {7, 6, 9, 4}

        };

    //构造比较函数

    Comparator<Node>  comparator = new Comparator<Node>() {

    public int compare(Node o1, Node o2) {

    return o1.getLb()-o2.getLb();

    };

    };

    //存储优先队列

    PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>(comparator);

    //记录当前最优解

    int results = 0;

    //存储节点

    Node resultNode=null;

    public Node initRootNode(){

    Node root = new Node();

    int lb=0;

    for(int i=0;i<cost.length;i++){

    int min=cost[i][0];

    for(int j=1;j<cost[0].length;j++){

    if(min>cost[i][j]){

    min=cost[i][j];

    }

    }

    lb+=min;

    }

    root.setLb(lb);//设置lb

    return root;

    }

    /**

     * 计算一个初始值上界

     * @return

     */

    public int  mostBound(){

    int bound=0;

    for(int i=0;i<cost.length;i++){

    int max=cost[i][0];

    for(int j=1;j<cost[i].length;j++){

    if(max<cost[i][j]){

    max=cost[i][j];

    }

    }

    bound+=max;

    }

    return bound;

    }

    //设置结果

    public void setResults(int results) {

    this.results = results;

    }

     

    /**

     * 计算lb

     * @param node

     * @return

     */

    public void calculateLb(Node node){

    int lb=0;

    ArrayList<Integer> upperNode =node.getUpperNode();

    int size=upperNode.size();

    for(int i=0;i<size;i++){//计算已选person的界

    lb+=cost[i][upperNode.get(i)];

    }

    for(int i=size;i<cost.length;i++){//计算剩余person的最小界

    int min=cost[i][0];

    for(int j=1;j<cost[i].length;j++){

    if(min>cost[i][j]){

    min=cost[i][j];

    }

    }

    lb+=min;

    }

    node.setLb(lb);//更新节点lb

    }

    /**

     * 计算孩子节点

     * @param node

     * @return

     */

    public ArrayList<Node> getChildNodes(Node node){

    ArrayList<Node> childNodes = new ArrayList<Node>();//孩子节点

    int i=node.getPerson()+1;

    int order=0;

    ArrayList<Integer> upperNode = node.getUpperNode();//获取已经选择的job

    for(int j=0;j<cost[i].length;j++){

    if(upperNode==null||order>=upperNode.size()){

    Node temp =getNode( i,j,upperNode);//设置节点

    childNodes.add(temp);

    }

    else{

    if(order<upperNode.size()&&!upperNode.contains(j)){//构造子节点

    Node temp =getNode(i,j,upperNode);//设置节点

    childNodes.add(temp);

    }

    else

    order++;

    }

    }

    return childNodes;

    }

    /**

     *

     *

     * @param i

     * @param j

     * @param list

     * @return

     */

    public Node getNode(int i,int j,ArrayList<Integer> list){

    ArrayList<Integer> uppers=new ArrayList<Integer>();

    if(list!=null&&list.size()>0){

    uppers.addAll(list);

    }

    uppers.add(j);

    Node temp = new Node(uppers);

    temp.setPerson(i);

    temp.setJob(j);

    calculateLb(temp);

    return temp;

    }

     

    /**

     *

     * @param node

     */

    public void assiginment(Node node){

    setResults(mostBound());//计算最大界

    priorityQueue.add(node);

    while(!priorityQueue.isEmpty()){

    Node currentNode = priorityQueue.poll();

    if(currentNode.getPerson()<cost.length-1){

    ArrayList<Node> childNodes = getChildNodes(currentNode);

    for(Node child:childNodes){

    if(child.getLb()<results){

    priorityQueue.add(child);

    }

    }

    }

    else{

    if(currentNode.getLb()<results){

    results=currentNode.getLb();

    resultNode=currentNode;

    }

    }

    }

    }

     

    public int getResults() {

    return results;

    }

     

    public Node getResultNode() {

    return resultNode;

    }

    public static void main(String[] args){

    Assignment at = new Assignment();

    Node root=at.initRootNode();

    at.assiginment(root);

    ArrayList<Integer> list = at.getResultNode().getUpperNode();

    System.out.println("人员以此选择工作为:");

    for(int i=0;i<list.size();i++){

    System.out.print(" "+(list.get(i)+1));

    }

    System.out.println();

    System.out.println("最小花费:");

    System.out.print(at.getResults());

    }

    }

     

    package three.one;

     

    import java.util.ArrayList;

     

    /**

     * Node类

     * @author ym

     *

     */

    public class Node{

    int person=-1;

    int job=-1;

    int weight=0;

    int lb=0;

    ArrayList<Integer> upperNode;

    public Node(){

    }

    public Node(ArrayList<Integer> upperNode){

    this.upperNode=upperNode;

    }

    public int getPerson() {

    return person;

    }

     

    public void setPerson(int person) {

    this.person = person;

    }

     

    public int getJob() {

    return job;

    }

     

    public void setJob(int job) {

    this.job = job;

    }

     

    public int getWeight() {

    return weight;

    }

     

    public void setWeight(int weight) {

    this.weight = weight;

    }

     

    public int getLb() {

    return lb;

    }

     

    public void setLb(int lb) {

    this.lb = lb;

    }

     

    public ArrayList<Integer> getUpperNode() {

    return upperNode;

    }

     

    public void setUpperNode(ArrayList<Integer> upperNode) {

    this.upperNode = upperNode;

    }

    }

    展开全文
  • 对多agent系统中的任务分配进行形式化描述的基础上, 融合模拟退火算法的优化思想, 提出了一种基于模拟退火遗传算法的任务分配方法, 详细阐述了该算法的基本思想和关键步骤, 并通过仿真实验进行验证。仿真实验结果...
  • 分枝限界法求解任务分配问题

    千次阅读 2020-03-18 10:07:41
    有n(n≥1)个任务需要分配给n个人执行,每个任务只能分配给一个人,每个人只能执行一个任务。 第i个人执行第j个任务的成本是c[i][j](1≤i,j≤n)。求出总成本最小的分配方案。 问题求解 这里采用优先队列式分枝...
  • 将蚂蚁算法用于求解任务分配...文中介绍了任务分配问题和蚂蚁算法,给出了求解任务分配问题的蚂蚁算法的数学描述及求解的算法步骤,在此基础上提出求解任务分配问题的改进蚂蚁算法。两个实例验证了改进蚂蚁算法的优越性。
  • 任务分配问题(匈牙利算法)

    千次阅读 2018-10-20 14:30:03
    【算法题】任务分配问题---匈牙利算法 一、问题描述 问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数...
  • datax(22):任务分配规则

    万次阅读 热门讨论 2021-01-26 23:18:25
    前面学习了一些源码和datax的执行,其中有一个重要的流程任务切分。今天梳理下; 一、概述 Datax根首先据配置文件,确定好channel的并发数目。...、切分任务 JobContainer 的split负责将整个jo.
  • 基于匈牙利算法的任务分配问题的python实现

    万次阅读 多人点赞 2018-05-22 20:35:55
    一、问题描述问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。问题数学描述: 二、实例分析---...
  • 任务分配-匈牙利算法

    千次阅读 2018-09-07 10:03:33
    在文章的开始,首先介绍两个关于匈牙利算法的文章: ... ... 一....问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分...
  • 任务分配问题-匈牙利算法

    千次阅读 2014-03-23 15:45:58
    问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。 问题数学描述:   二、实例分析---...
  • 任务分配问题---匈牙利算法

    千次阅读 2017-01-03 18:01:13
    问题描述:N个人分配N项任务,一个人只能分配一项任务,一项任务只能分配给一个人,将一项任务分配给一个人是需要支付报酬,如何分配任务,保证支付的报酬总数最小。 问题数学描述:   二、实例分析---...
  • Activiti — 动态任务分配

    千次阅读 2016-06-06 16:47:16
    动态任务分配使用的两种方式 一、通过特殊表达式,来获取任务信息 ,在流程 UserTask节点上设置 ${流程变量的Key} 1、流程定义 1 "1.0" encoding="UTF-8"?> 2 ...
  • 一个完整的项目除了包含不同阶段的细分的任务之外,还需要项目负责人\经理为每个任务分配所需要的资源,不限于人力资源,成本或者设备等资源,以此来衡量该项目资源储备是否充足,预算是否超过预期标准,设备是否...
  • 入门学习Linux常用必会60个命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    如果发行版安装了自动挂装包,那么这个步骤可自动进行。在Linux中,如果要使用硬盘、光驱等储存设备,就得先将它加载,当储存设备挂上了之后,就可以把它当成一个目录来访问。挂上一个设备使用mount命令。在使用...
  •  // 线程池的大小会根据执行的任务数量动态分配 注意:创建一个可缓存的线程池。在JAVA文档中是这样介绍可回收缓存线程池的:创建一个可根据需要创建新线程的线程池,但是在以前构造的线程可用时将重用它们。对于...
  • 分布式计算任务调度算法总结

    万次阅读 2019-02-20 17:08:55
    主要有这些因素影响着分布式系统的性能:网络延迟、数据通信效能、计算节点处理能力、任务的分割、无法预算处理时间、任务的颠簸等等。 我们在寻求分布式计算调度算法时,就是有针对性的以解决这些问题为目的,从...
  • 步骤 2:为任务分配人员和其他资源 为任务工时分配人员 将任务添加到日程后,您可以开始分配人员来处理它们。 在甘特条旁边显示任务名称 如果旁边显示任务名称,您可以更轻松地理解甘特条形图。...
  • 5.1.3 主消费者执行分配任务

    千次阅读 2021-04-19 15:08:28
    5.1.3 主消费者执行分配任务 消费者发送的“加入组请求”(Jo1nGroupRequest)的内容包括:消费组编号、消费者成员编号、协议类型、协议内容和元数据(protocolMetadata)。其中,协议内容是分区分配算法的名称,元数据...
  • JAVA上百实例源码以及开源项目

    千次下载 热门讨论 2016-01-03 17:37:40
     Java访问权限控制,为Java操作文件、写入文件分配合适的权限,定义写到文件的信息、定义文件,输出到c:/hello.txt、写信息到文件、关闭输出流。 Java绘制图片火焰效果 1个目标文件 摘要:Java源码,图形操作,火焰...
  • 项目经理如何分配任务

    千次阅读 2013-01-14 16:06:45
    记得自己第一次当PM。那是接手的项目,原来的PM,在项目需求分析做完之后,去接手另一个重要的项目去了。当时我和另外两个小组长,自然就成...而我当时最头疼的就是,我怎么给另外两个小组长分配任务啊。前一天大家还
  • 常用分布式计算任务调度算法

    万次阅读 多人点赞 2019-05-10 10:12:38
    在用于任务分配问题求解的蚁群算法中,每一个人工蚂蚁是具有下述特性的智能体: 当它选择把任务指派给处理器时,它会在连接上留下一种称为痕迹的物质(等价于信息素); 它以一定的概率为一指定任务选择处理器,该...
  • 分支限界法解决作业分配问题 Java

    千次阅读 2019-04-23 10:05:40
    exe4j的使用教程可以看这篇博客:https://blog.csdn.net/jinny_0019/article/details/80065452 目录 一、问题描述 二、要求 、提示 四、运行环境 ...有n份作业分配给n个人去完成,每人完成一...
  • BCD-七段数码管显示译码器

    万次阅读 多人点赞 2015-10-18 14:28:45
    总结:我个人感觉操作的规范化比较重要,如果操作不规范不仅使操作步骤繁琐,也有可能带来错误。其次是理解代码含义,了解BCD-七段数码管显示译码器的作用,清楚共阴极,共阳极的差别。应该可以比较顺利完成任务
  • CCBPM 任务分配流程设计说明

    千次阅读 2015-12-02 15:13:51
    主要特点说明: 1.分流点明细表中的字段作为子线程...第二步,给分流节点创建分配任务明细表。 注意事项:明细表中,必须有编号、处理人两列,用于指定工作处理人。   第步,设计子线程节点。 1.设置表单,将任
  • 【优化算法】简述灰狼优化算法(GWO)原理

    万次阅读 多人点赞 2019-03-25 21:10:34
    GWO 优化过程包含了灰狼的社会等级分层、跟踪、包围和攻击猎物等步骤,其步骤具体情况如下所示。 1)社会等级分层(Social Hierarchy)当设计 GWO 时,首先需构建灰狼社会等级层次模型。计算种群每个个体的适应度...
  • :以下是部署大数据解决方案所遵循的步骤 Ⅰ、数据摄取 部署大数据解决方案的第一步是数据提取,即从各种来源提取数据。数据源可以是像Salesforce这样的CRM,像SAP这样的企业资源规划系统,像MySQL这样的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 188,205
精华内容 75,282
关键字:

任务分配的三步骤