Scheduling task graphs optimally with A*

Scheduling tasks onto the processors of a parallel system is a crucial part of program parallelisation. Due to the NP-hard nature of the task scheduling problem, scheduling algorithms are based on heuristics that try to produce good rather than optimal schedules. Nevertheless, in certain situations it is desirable to have optimal schedules, for example for time-critical systems or to evaluate scheduling heuristics. This paper investigates the task scheduling problem using the A* search algorithm which is a best-first state space search. The adaptation of the A* search algorithm for the task scheduling problem is referred to as the A* scheduling algorithm. The A* scheduling algorithm can produce optimal schedules in reasonable time for small to medium sized task graphs with several tens of nodes. In comparison to a previous approach, the here presented A* scheduling algorithm has a significantly reduced search space due to a much improved consistent and admissible cost function f(s) and additional pruning techniques. Experimental results show that the cost function and the various pruning techniques are very effective for the workload. Last but not least, the results show that the proposed A* scheduling algorithm significantly outperforms the previous approach.     

基于目标信息估计的分布式局部协调任务分配方法

分布式决策是提高群体自主性的关键技术之一.以侦查类无人机(unmanned search aerial vehicles,USAV)和打击类无人机(unmanned combat aerial vehicles,UCAV)执行协同搜索、攻击灰色目标区域问题为背景,建立了一种考虑局部链式通信、无人机飞行性能和任务执行能力等多约束的分布式任务分配模型,基于贝叶斯定理将任务空间的连续/离散不确定量用任务收益值量化描述.然后,提出了一种基于一致性协调算法的在线协同策略,并利用一致协调理论建立了一种冲突调解规则,在此基础上,设计了一种分布式任务分配求解算法,能够实现多USAV,UCAV的协同多任务快速分配.最后,通过数值仿真,验证了本文算法求解不确定空间任务分配问题的可行性和快速性.     

Considering inter-task resource constraints in task allocation

This paper focuses on task allocation with single-task robots, multi-robot tasks and instantaneous assignment, which has been shown to be strongly NP-hard. Although this problem has been studied extensively, few efficient approximation algorithms have been provided due to its inherent complexity. In this paper, we first provide discussions and analyses for two natural greedy heuristics for solving this problem. Then, a new greedy heuristic is introduced, which considers inter-task resource constraints to approximate the influence between different assignments in task allocation. Instead of only looking at the utility of the assignment, our approach computes the expected loss of utility (due to the assigned robots and task) as an offset and uses the offset utility for making the greedy choice. A formal analysis is provided for the new heuristic, which reveals that the solution quality is bounded by two different factors. A new algorithm is then provided to approximate the new heuristic for performance improvement. Finally, for more complicated applications, we extend this problem to include general task dependencies and provide a result on the hardness of approximating this new formulation. Comparison results with the two natural heuristics in simulation are provided for both formulations, which show that the new approach achieves improved performance.     

Representations of task assignments in distributed systems using Young tableaux and symmetric groups

This article presents a novel approach to representing task assignments for partitioned agents (respectively, tasks) in distributed systems. A partition of agents (respectively, tasks) is represented by a Young tableau, which is one of the main tools in studying symmetric groups and combinatorics. In this article, we propose a task, agent and assignment tableau in order to represent a task assignment for partitioned agents (respectively, tasks) in a distributed system. This article is concerned with representations of task assignments rather than finding approximate or near optimal solutions for task assignments. A Young tableau approach allows us to raise the expressiveness of partitioned agents (respectively, tasks) and their task assignments.     

基于多准则的动态任务分配算法的研究

针对目前任务分配算法考虑的因素往往比较固定,可扩展性和灵活性较差等缺点,提出一种基于多准则的动态任务分配算法,对任务参与者的实时情况的跟踪和分析更加精确,对任务的分配更均衡;并给出了详细的任务分配的形式化表示,各评估指标之间相互独立,增强了算法的可扩展性。另外,提出采用计时器的方法来实现推拉式结合的任务分配机制,增强了算法的灵活性,既可以按照员工对任务感兴趣程度去自主选择工作项,又可以保证系统在没有员工自主选择任务项正常运转,在不影响工作正常执行的情况下使工作流管理系统的任务分配更加人性化。     

云计算环境下基于模板的任务调度策略与算法

针对云计算任务调度,提出了一种基于模板的任务调度（Template-based Task Scheduling,TTS）策略。该策略充分考虑了通信开销,在对任务分配进行预处理的基础上实现任务调度,主要分为两步：针对一个任务集合,采用可分任务调度求解子任务大小的方法,求出各个处理机应该分担的任务量模板;根据求出的模板,采用合理的调度算法对任务进行调度,从而得到较优的调度结果。在TTS策略下,对传统贪心算法加以改进,最终提出基于模板的任务调度贪心算法（Template-based Task Scheduling Greedy Algorithm,TTSGdA）。与Min-min算法和遗传算法的对比实验结果表明,TTSGdA能够有效减少任务集合完成时间。     

Large-scale multi-robot task allocation via dynamic partitioning and distribution

This paper introduces an approach that scales assignment algorithms to large numbers of robots and tasks. It is especially suitable for dynamic task allocations since both task locality and sparsity can be effectively exploited. We observe that an assignment can be computed through coarsening and partitioning operations on the standard utility matrix via a set of mature partitioning techniques and programs. The algorithm mixes centralized and decentralized approaches dynamically at different scales to produce a fast, robust method that is accurate and scalable, and reduces both the global communication and unnecessary repeated computation. An allocation results by operating on each partition: either the steps are repeated recursively to refine the generalized assignment, or each sub-problem may be solved by an existing algorithm. The results suggest that only a minor sacrifice in solution quality is needed for significant gains in efficiency. The algorithm is validated using extensive simulation experiments and the results show advantages over the traditional optimal assignment algorithms.     

A novel global harmony search algorithm for task assignment problem

The objective of task assignment problem (TAP) is to minimize the sum of interprocessor communication and task processing costs for a distributed system which subjects to several resource constraints. We use a novel global harmony search algorithm (NGHS) to solve this problem, and the NGHS algorithm has demonstrated higher efficiency than the improved harmony search algorithm (IHS) on finding the near optimal task assignment. We also devise a new method called normalized penalty function method to tradeo^® the costs and the constraints. A large number of experiments show that our algorithm performs well on finding the near optimal task assignment, and it is a viable approach for the task assignment problem.     

改进PSO算法在多无人机协同任务分配中的应用

针对多无人机协同任务分配越来越复杂的问题,采用一种改进的阶层分级粒子群优化算法（HGIWPSO）获得最优分配方案。首先,根据粒子适应度值将种群动态划分为三个不同阶层,依据不同阶层粒子特性选择合适的学习模型,并引入独立权重思想调节惯性权重大小,平衡算法全局与局部搜索能力,提高算法性能;然后,建立协同多任务分配问题模型,采用多余负载竞拍方案减少非法劣解,通过实数编码建立粒子和实际分配方案之间的映射关系,解决实际分配问题。实验结果表明,该算法能够有效解决复杂约束条件下多无人机协同任务分配问题,得到最优分配序列,具有一定的理论以及实际意义。     

Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems

In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.     

基于E-CARGO模型的多任务分配算法

多任务分配是管理和协同工作中的重要问题。采用E-CARGO建模来解决常规多任务分配问题(GMTAP)与组角色多任务分配问题(GRMTAP)。提出了两种算法:(1)通过把GMTAP质量评估矩阵转置转化为组角色分配问题(GRAP),再利用GRAP算法来完成多任务分配;(2)将GRMTAP分配问题转化为常规分配问题(GAP),利用K-M(亦称匈牙利)算法来实现多任务分配。最后,通过实验验证了GMTAP与GRMTAP算法的有效性,即,算法很好地满足了多任务分配问题的需要,也有效地扩展了GRAP算法与K-M算法的应用范围。     

一种基于兴趣约束的新型组播地址分配方法

基于兴趣的约束关系提出了一种新型的组播地址分配方法——建立布种模型,通过布种模型的初始化和推演实现组播地址的静态和动态分配．论文结合二维点阵和PR四分树定义了布种模型的空间数据结构,并提出自适应生长／剪枝算法和检索算法实现组播地址的动态分配和快速搜索．算法分析和性能测试表明该方法效率高,可满足大规模分布式虚拟环境中的组播地址分配和检索．最后简介了该方法在分布式仿真运行平台BH RTI中的实现．     

舰载机多雷达传感器任务分配与采样间隔融合优化算法

针对舰载机协同探测中多雷达传感器资源配置问题,提出一种多目标跟踪场景下的多传感器数据率管理与任务分配融合优化算法.在基于协方差控制的多传感器分配模型基础上,加以目标优先级和传感器效能条件约束,建立一种多传感器数据率管理与任务分配融合优化模型.将驻留时间改进因子引入序贯卡尔曼滤波算法,计算不同采样间隔下传感器组合状态估计...     

Evolutionary Optimization of File Assignment for a Large-Scale Video-on-Demand System

We present a genetic algorithm for tackling a file assignment problem for a large-scale video-on-demand system. The file assignment problem is to find the optimal replication and allocation of movie files to disks so that the request blocking probability is minimized subject to capacity constraints. We adopt a divide-and-conquer strategy, where the entire solution space of file assignments is divided into subspaces. Each subspace is an exclusive set of solutions sharing a common file replication instance. This allows us to utilize a greedy file allocation method for finding a good-quality heuristic solution within each subspace. We further design two performance indices to measure the quality of the heuristic solution on 1.) its assignment of multicopy movies and 2.) its assignment of single-copy movies. We demonstrate that these techniques, together with ad hoc population handling methods, enable genetic algorithms to operate in a significantly reduced search space and achieve good-quality file assignments in a computationally efficient way.     

基于状态空间的机械臂轨迹规划

提出一种基于状态空间的机械臂轨迹规划方法,定义并构造了机械臂系统的状态空间,根据内在机构约束与外部环境约束描述出系统状态的可达范围,并给出了任务的可实现条件.对于可实现任务,在状态空间能搜索到任务完成的最优解.如果任务无法完成,则修改系统配置或约束,在新的状态空间确定任务实现的转化条件,并对任务的设计与规划给予指导.研究了障碍约束下两连杆机械臂的点到点任务,实验结果验证了该方法的有效性.     

基于粒子群算法的移动边缘计算任务分配方法

为提高移动终端任务分配效率,降低计算能量损耗,提出基于粒子群算法的移动边缘计算任务分配方法。通过构建异构网络获取完整的需要分配的任务,明确任务分配时所需的特定条件,即分配消耗和时延等。将分配任务转化成寻找分配结果的最优解,构建最优解模型,利用粒子群算法对模型实施求解,经过不断迭代和更新,生成最优边缘计算任务的分配结果。实验结果表明,粒子群方法在分配任务数量为20~100之间时计算时间在1 s~3.3 s;当任务数量为100时,本文方法能耗仅为4107 J;粒子群方法在任务达到率达到100%时,其时延仅为12.5 ms;其任务分配计算时间短、能量消耗小和数据传输的时延短,能较好地满足实际应用需要。     

基于帕累托改进的多机器人动态任务分配算法

针对多机器人系统动态任务分配中存在的优化问题,在使用合同网初始任务分配的基础上提出了一种使用帕累托改进的任务二次分配算法。多机器人系统并行执行救火任务时,首先通过初始化任务分配将多机器人划分为若干子群;然后,每个子群承包某一救火任务,子群在执行任务的同时与就近子群进行帕累托改进确定需要迁移的机器人,实现两子群之间帕累托最优;最后,使用后序二叉树遍历对所有子群进行帕累托改进实现全局帕累托最优。理论分析和仿真结果表明,相较于强化学习算法和蚁群算法,所提算法的救火任务时间分别减少26.18%和37.04%;相较于传统合同网方法,所提算法在时间方面能够高效完成救火任务,在系统收益方面也具有明显优势。     

A genetic algorithm for the project assignment problem

In this paper we present a genetic algorithm as an aid for project assignment. The assignment problem illustrated concerns the allocation of projects to students. Students have to choose from a list of possible projects, indicating their preferred choices in advance. Inevitably, some of the more popular projects become ‘over-subscribed’ and assignment becomes a complex problem. The developed algorithm has compared well to an optimal integer programming approach. One clear advantage of the genetic algorithm is that, by its very nature, we are able to produce a number of feasible project assignments, thus facilitating discussion on the merits of various allocations and supporting multi-objective decision making.     

基于改进粒子群算法的空间众包任务分配模型

如何进行高效合理的任务分配是当前空间众包（SC）研究中的关键问题之一。针对SC分配效能低的问题,建立了最佳质量任务分配模型（maximum quality task assignment model,MQTAM）,并提出了基于改进粒子群算法的空间众包任务分配算法（SCTAM_PSO）。该模型充分考虑了工作者到达工作地点后完成任务的时间延迟、完成任务的可信度等因素,通过SCTAM_PSO算法智能搜索最佳分配方案以最大化提高任务完成质量。实验结果及分析表明MQTAM和SCTAM_PSO具有一定的有效性与可行性。     

基于动态蚁群劳动分工模型的多AUV任务分配方法

多水下自主航行器(autonomous underwater vehicle,AUV)的动态任务分配问题具有高度非线性、动态不确定性以及多模态的特征,对多AUV任务分配方法的自组织性、鲁棒性以及快速性提出了更高的要求.动态蚁群劳动分工(dynamic ant colony''s labor division,DACLD)模型是一种采用分布式框架的群智能算法,众多行为简单的个体相互作用过程中涌现产生的整体智能行为能很好地适应复杂多变的环境,在解决任务分配问题上具有很好的柔性.引入动态蚁群劳动分工中的刺激-响应原理,建立动态蚁群劳动分工与多AUV任务分配问题之间的映射关系,将任务的状态预测纳入响应阈值,研究基于动态蚁群劳动分工模型的多AUV任务分配方法.同时,针对任务分配过程中可能出现的任务冲突现象,提出新的循环竞争方案以实现最大限度地利用AUV资源.仿真结果表明,所提出的方法能高效地完成任务分配过程,具有很好的自组织性、鲁棒性及快速性.