Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel

We consider the problem of scheduling orders on identical machines in parallel. Each order consists of one or more individual jobs. A job that belongs to an order can be processed by any one of the machines. Multiple machines can process the jobs of an order concurrently. No setup is required if a machine switches over from one job to another. Each order is released at time zero and has a positive weight. Preemptions are not allowed. The completion time of an order is the time at which all jobs of that order have been completed. The objective is to minimize the total weighted completion time of the orders. The problem is NP‐hard for any fixed number (≥2) of machines. Because of this, we focus our attention on two classes of heuristics, which we refer to as sequential two‐phase heuristics and dynamic two‐phase heuristics. We perform a worst case analysis as well as an empirical analysis of nine heuristics. Our analyses enable us to rank these heuristics according to their effectiveness, taking solution quality as well as running time into account. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Maximizing project cash availability

Consider a project during the life cycle of which there are cash payouts and in‐flows. To better meet his financial commitments, the project owner would like to meet all deadlines without running out of cash. We show that the cash availability objective is similar to the total weighted flowtime used to measure work‐in‐progress performance in the scheduling and inventory control literatures. In this article we provide several specialized solution methods for the problem of minimizing total weighted flowtime in an arbitrary acyclic project network, subject to activity release times and due dates, where the activity weights may be positive or negative and represent cash in‐ and out‐flows. We describe the structure of an optimal solution and provide several efficient algorithms and their complexity based on mincost and maxflow formulations. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

基于距离加权Bloom filter的网络路由算法

基于分布式哈希表(DHT)的P2P查找经常受到在底层网络中路由时无必要的路径长度增加的影响.另外,DHT在处理复制方面也有一定的缺陷.文中探讨了解决这些问题的方法.对使用Bloom filters作为资源路由的方法做了简要回顾,并较为详细地阐述了在资源分散的覆盖网络中使用距离加权Bloom filter的网络路由算法.对该算法进行了仿真测试,证明了其有效性.     

基于蚁群算法的试验流程优化研究

水中兵器的海上试验涉及许多人员、兵力、被试产品、测量设备等,试验周期长、消耗大,因此如何缩短试验周期是亟待研究解决的问题.文中首先将试验流程优化问题转化为车间调度问题,建立了相应的数学模型,再应用蚁群算法转移规则得到中间结果并进行排队以对各种资源约束进行处理.最后将结果利用局部搜索算法优化后作为蚁群算法信息素更新的基础.实例计算结果表明,该方法优化效果良好.     

Neo-conservation

Africa's wildlife is in danger. The last couple of years have been disastrous for the African elephant as poaching for ivory reached record numbers. Rhinos have been hit hard with several sub-species becoming extinct. The current anti-poaching and anti-trafficking operations lack the sophistication and determination that is found abundantly within criminal organisations immersed in this illicit trade. Terrorism, rebellious elements and corrupt officials all benefit from the destruction of Africa's eco-system and the inaction or lack of efficient action thereof by law enforcement officials. This commentary suggests new courses of action using methods from the fields of counter-terrorism and special operations.     

基于逆向强化学习的舰载机甲板调度优化方案生成方法

针对计算机辅助指挥调度舰载机甲板作业的决策过程无法脱离人参与这一特点,引入基于逆向学习的强化学习方法,将指挥员或专家的演示作为学习对象,通过分析舰载机的甲板活动,建立舰载机甲板调度的马尔可夫决策模型(MDP)框架;经线性近似,采用逆向学习方法计算得到回报函数,从而能够通过强化学习方法得到智能优化策略,生成舰载机甲板调度方案。经仿真实验验证,本文所提方法能够较好地学习专家演示,结果符合调度方案优化需求,为形成辅助决策提供了基础。     

基于HLA的防区外空面导弹攻防对抗仿真

针对HLA/RTI在接口规范、对象模型模板等关键技术建立分布式仿真平台的复杂性,提出了利用数字武器开发平台进行开发的方法,构建防区外空面导弹攻防对抗系统体系结构,实现了该体系结构联邦成员划分、设计联邦/仿真对象模型表等HLA仿真关键技术,并采用面向对象建模与仿真技术建立了各联邦成员的数学模型.该仿真结果表明,各联邦成员的数学模型与底层支撑环境能够相互分离,仿真模型具有良好的交互性和互操作性,可通过添加或删除联邦成员仿真不同的复杂战场想定,并可作为验证不同算例的仿真平台.     

基于行为建模的移动代理性能评估

针对移动代理的分布式应用性能评估需求,建立了移动代理生命周期中主要行为的网络负载模型和时间消耗模型.在3种典型分布式应用想定下,分析了基于C＼S模式和移动代理模式的应用实现基本过程,对两种模式下的网络负载和执行时间进行了仿真比较,结果证明了在访问节点数量较多,网络传输速率较低时,移动代理模式的具有更好性能.     

面向无人环境的机器人生态圈自主任务决策方法

借鉴自然界生态系统的典型特征,提出机器人生态圈概念。通过使集群机器人进行智能协同与复杂演化,涌现自我维持、自我复制与自我进化等生命特征,实现无人条件下的长期生存、繁衍与进化,并执行特定的任务。针对机器人生态圈典型任务场景的自主任务决策需求,分析不同机器学习任务决策方法的特点,建立机器人生态圈自主任务决策的决策树模型和神经网络模型。分析表明,两种模型的正确率均在80%~90%,且均具有良好的稳定性。这说明,机器人生态圈自主任务决策问题可以通过决策树、神经网络等机器学习方法来很好地加以解决,从而为面向无人化场景的任务应用提供技术支持。     

基于飞蛾信息素寻偶机制的无人机集群协同搜索

为了提高无人机集群协同搜索移动目标的效率,提出一种基于飞蛾信息素寻偶机制的无人机集群协同搜索方法。根据飞蛾基于信息素选择飞行方向的寻偶行为,建立信息素图风向模型和飞蛾信息素寻偶模型。考虑无人机机间避撞约束,提出从飞蛾信息素寻偶机制到无人机集群分布式协同搜索的映射,并给出具体实现流程。仿真实验结果表明了所提方法在解决单个移动目标的协同搜索问题时的有效性和稳定性;外场飞行试验表明了所提方法在实际应用中的可行性。