对几种典型分布式任务分配算法的分析和改进

本文先分析了基于图论的分配方法,整数规划方法和试探法等几个典型的分布式任务分配算法的特点、不足和算法复杂度,以及可进一步改进之处。然后给出了一种试探法的改进算法,并讨论了它的特点和性能。     

对几种典型分布式任务分配算法的分析和改进

本文先分析了基于图论的分配方法，整数规划方法和试探法等几个典型的分布式任务分配算法的特点，不足和算法复杂度，以及可进一步改进之处，然后给出了一种试探法的改进算法，并讨论了它的特点和性能。     

一种改进的启发式任务分配算法

文中首先分析了分布式任务分配中的启发式算法的基本思想，特点，不足和算法复杂度，以及可进一步改进之处，然后给出了一种训发式算法的改进算法，并简单讨论了其特点和性能，最后指出了分布式任务分配的发展方向。     

异构分布式控制系统中实时任务的调度算法

分布式控制系统是一种应用极为广泛的异构分布式实时系统，系统中同时存在有多种实时任务，如何将这些任务分配到各个处理器上并保证它们的时限是系统关键技术之一．在结合启发式任务分配算法和单处理器任务调度算法的基础上，提出了一种分布式控制系统的调度算法．该算法考虑了各个处理器的负载均衡，同时又能满足所有任务的时限．仿真结果表明了算法的有效性．     

分布式约束满足问题及其在MAS任务分配中的应用*

针对多智能体系统(MAS)任务分配问题中多个任务与MAS两者的分布式特征,将任务分配问题形式化为分布式约束满足问题(DCSP)进行求解,分别建立了以任务为中心和以agent为中心两种MAS任务分配模型,基于改进的DCSP分布式并行求解算法,提出了基于DCSP的MAS任务分配问题求解框架。该方法适合求解agent间通信有随机延迟以及agent间存在多约束的问题,应用实例的求解表明了其实用性与有效性。     

一种分布式数据库关联规则挖掘算法

现有的数据挖掘算法多是集中式环境下的数据挖掘处理,但目前的大型数据库多以分布式的形式存在,针对分布式数据挖掘算法FDM及其改进算法中存在的频繁项集丢失问题和网络通信开销过高的问题,提出了一种改进的基于关联规则的分布式数据挖掘算法LTDM,LTDM算法引入了映射标示数组机制,可以在保证频繁项集完整性的同时降低网络的通信开销。实验结果证明了算法的有效性。     

复杂约束条件下异构多智能体联盟任务分配

分布式任务决策是提高多智能体系统自主性的关键. 以异构多智能体协同执行复杂任务为背景, 首先建立 了一种考虑任务载荷资源约束、任务耦合关系约束及执行窗口约束等条件的异构多智能体分布式联盟任务分配模 型; 其次, 对一致性包算法(CBBA)进行了扩展, 提出了基于改进冲突消解原则的一致性联盟算法(CBCA), 以实现异 构多智能体协同无冲突任务分配, 并进一步证明了在一定条件下CBCA算法收敛于改进顺序贪婪算法(ISGA). 最后 通过数值仿真, 验证了CBCA算法求解复杂约束条件下异构多智能体联盟任务分配问题的可行性和快速性.     

分布式实时系统中负载平衡任务分配算法

提出了一种以系统负载平衡为目标的分布式实时系统任务分配算法。该算法首先通过对任务分组，减小系统负载，再按照一种新的目标函数，启发搜索任务分配树，来获得系统负载平衡条件下系统负载最小的任务分配方案，有效地减小了启发式搜索算法的计算复杂度。     

Linux群集任务分配算法的探讨

在介绍群集技术和Linux Virtual Server群集的基础上，详细分析了LVS群集目前实现的4种任务分配算法及其不足之处，并给出改进的任务分配算法，最后通过测试实例对改进算法进行了验证。     

基于图象空间分布的Shading算法

本文首先介绍了基于局部光照模型的串行Shading算法，然后对设计分布式Shading算法所用到的动态任务分配、数据适应性任务分配、任务粒度等因素作了较为详细的论述，并给出了所设计的新的数据适应性任务划分算法，最后给出了所设计的分布式Shading算法的描述和实验结果.     

Task assignment for minimizing application completion time using honeybee mating optimization

Effective task assignment is essential for achieving high performance in heterogeneous distributed computing systems. This paper proposes a new technique for minimizing the parallel application time cost of task assignment based on the honeybee mating optimization (HBMO) algorithm. The HBMO approach combines the power of simulated annealing, genetic algorithms, and an effective local search heuristic to find the best possible solution to the problem within an acceptable amount of computation time. The performance of the proposed HBMO algorithm is shown by comparing it with three existing task assignment techniques on a large number of randomly generated problem instances. Experimental results indicate that the proposed HBMO algorithm outperforms the competing algorithms.     

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.     

An effective iterated greedy algorithm for reliability-oriented task allocation in distributed computing systems

This paper investigates the problem of allocating parallel application tasks to processors in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation for more than three processors is known to be NP-hard in the strong sense. To deal with this challenging problem, we propose a simple and effective iterative greedy algorithm to find the best possible solution within a reasonable amount of computation time. The algorithm first uses a constructive heuristic to obtain an initial assignment and iteratively improves it in a greedy way. We study the performance of the proposed algorithm over a wide range of parameters including problem size, the ratio of average communication time to average computation time, and task interaction density. The viability and effectiveness of our algorithm is demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature.     

Task assignment in heterogeneous computing systems

The problem of task assignment in heterogeneous computing systems has been studied for many years with many variations. We consider the version in which communicating tasks are to be assigned to heterogeneous processors with identical communication links to minimize the sum of the total execution and communication costs. Our contributions are three fold: a task clustering method which takes the execution times of the tasks into account; two metrics to determine the order in which tasks are assigned to the processors; a refinement heuristic which improves a given assignment. We use these three methods to obtain a family of task assignment algorithms including multilevel ones that apply clustering and refinement heuristics repeatedly. We have implemented eight existing algorithms to test the proposed methods. Our refinement algorithm improves the solutions of the existing algorithms by up to 15% and the proposed algorithms obtain better solutions than these refined solutions.     

一个调度Out-Tree任务图的启发式算法

任务调度问题是并行分布式计算中的挑战性问题之一。大多数实际的调度算法是启发式的因而常常具有改进的余地。针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的处理器最少。因而,该算法提高了系统的利用率,避免消耗过多的资源,实际应用性更好。     

Upper and lower bounds for dynamic cluster assignment for multi-target tracking in heterogeneous WSNs

In this paper, we consider the problem of cluster task assignment to maximize total utilities of nodes for target coverage in heterogeneous Wireless Sensor Networks. We define this problem as assigning the tasks of Cluster Head (CH) and Cluster Members (CM) to nodes for each target and requiring communication connectivity between every CH with its members. The utility of each node for each target is defined as a function of its distance to the target and its remaining energy. We propose an upper bound based on Lagrangian Relaxation (LR) and a lower bound by Linear Programming (LP) relaxation with a combination of Randomized Rounding (RR) and a greedy-based heuristic. Furthermore, we propose a distributed heuristic algorithm based on matching and a general assignment problem. Dynamic movements of targets are taken into account by intra/inter-cluster task reassignments. Simulation results, compared with optimal values, reveal that the LR upper bound performs better than the bound reached by pure LP relaxation. The lower bound obtained by LP relaxation combined with the RR technique provides close results in comparison with the distributed heuristic algorithm. Furthermore, the results of the distributed heuristic algorithm remain between the upper and lower bounds and close to optimal values.     

Task swapping networks in distributed systems

In this paper we propose task swapping networks for task reassignments by using task swappings in distributed systems. Some classes of task reassignments are achieved by using iterative local task swappings between software agents in distributed systems. We use group-theoretic methods to find a minimum-length sequence of adjacent task swappings needed from a source task assignment to a target task assignment in a task swapping network of several well-known topologies.     

A two-phase approach to interactivity enhancement for large-scale distributed virtual environments

Distributed virtual environments (DVEs) are distributed systems that allow multiple geographically distributed clients (users) to interact simultaneously in a computer-generated, shared virtual world. Applications of DVEs can be seen in many areas nowadays, such as online games, military simulations, collaborative designs, etc. To support large-scale DVEs with real-time interactions among thousands or even more distributed clients, a geographically distributed server architecture (GDSA) is generally needed, and the virtual world can be partitioned into many distinct zones to distribute the load among the servers. Due to the geographic distributions of clients and servers in such architectures, it is essential to efficiently assign the participating clients to servers to enhance users’ experience in interacting within the DVE. This problem is termed the client assignment problem (CAP) in this paper. We propose a two-phase approach, consisting of an initial assignment phase and a refined assignment phase to address the CAP. Both phases are shown to be NP-hard. Several heuristic assignment algorithms are then devised and evaluated via extensive simulations with realistic settings. We find that, even under heterogeneous environments like the Internet where accurate input data for the assignment algorithms are usually impractical to obtain, the proposed algorithms are still beneficial to the performances of DVE.     

无线Mesh网络中基于局部信息的自适应信道分配策略

在多无线接口多信道的无线Mesh网络中,信道分配问题将影响网络的整体性能。为充分利用无线Mesh的资源优势,已提出了许多信道分配策略。然而,大部分的研究假设都隐含需要全网拓扑或者流量模型等信息,这在分布式网络中很难准确获取。为此,本文提出基于局部信息的自适应信道分配策略LICA,在仅使用局部拓扑和节点间信道使用情况等启发式信息的基础上,动态指导信道分配。模拟实验结果表明,LICA算法能显著提高信道利用效率和端到端的数据吞吐量,且具备较低的时间复杂度和良好的可扩展性。