共查询到20条相似文献,搜索用时 15 毫秒
1.
Qin-Ma Kang Author Vitae Hong He Author Vitae Author Vitae Rong Deng Author Vitae 《Journal of Systems and Software》2010,83(11):2165-2174
This paper deals with the problem of task allocation (i.e., to which processor should each task of an application be assigned) in heterogeneous distributed computing systems with the goal of maximizing the system reliability. The problem of finding an optimal task allocation is known to be NP-hard in the strong sense. We propose a new swarm intelligence technique based on the honeybee mating optimization (HBMO) algorithm for this problem. The HBMO based approach combines the power of simulated annealing, genetic algorithms with a fast problem specific local search heuristic to find the best possible solution within a reasonable computation time. We study the performance of the algorithm over a wide range of parameters such as the number of tasks, the number of processors, the ratio of average communication time to average computation time, and task interaction density of applications. The effectiveness and efficiency of our algorithm are demonstrated by comparing it with recently proposed task allocation algorithms for maximizing system reliability available in the literature. 相似文献
2.
A fundamental issue affecting the performance of a parallel application running on a heterogeneous computing system is the assignment of tasks to the processors in the system. The task assignment problem for more than three processors is known to be NP-hard, and therefore satisfactory suboptimal solutions obtainable in an acceptable amount of time are generally sought. This paper proposes a simple and effective iterative greedy algorithm to deal with the problem with goal of minimizing the total sum of execution and communication costs. The main idea in this algorithm is to improve the quality of the assignment in an iterative manner using results from previous iterations. The algorithm first uses a constructive heuristic to find an initial assignment and iteratively improves it in a greedy way. Through simulations over a wide range of parameters, we have demonstrated the effectiveness of our algorithm by comparing it with recent competing task assignment algorithms in the literature. 相似文献
3.
Gang WU Zhiyong CHEN Jia LIU Donghong HAN Baiyou QIAO 《Frontiers of Computer Science》2021,15(2):152316
Crowdsourcing has become an efficient measure to solve machine-hard problems by embracing group wisdom, in which tasks are disseminated and assigned to a group of workers in the way of open competition. The social relationships formed during this process may in turn contribute to the completion of future tasks. In this sense, it is necessary to take social factors into consideration in the research of crowdsourcing. However, there is little work on the interactions between social relationships and crowdsourcing currently. In this paper, we propose to study such interactions in those social-oriented crowdsourcing systems from the perspective of task assignment. A prototype system is built to help users publish, assign, accept, and accomplish location-based crowdsourcing tasks as well as promoting the development and utilization of social relationships during the crowdsourcing. Especially, in order to exploit the potential relationships between crowdsourcing workers and tasks, we propose a “worker-task” accuracy estimation algorithm based on a graph model that joints the factorized matrixes of both the user social networks and the history “worker-task” matrix. With the worker-task accuracy estimation matrix, a group of optimal worker candidates is efficiently chosen for a task, and a greedy task assignment algorithm is proposed to further the matching of worker-task pairs among multiple crowdsourcing tasks so as to maximize the overall accuracy. Compared with the similarity based task assignment algorithm, experimental results show that the average recommendation success rate increased by 3.67%; the average task completion rate increased by 6.17%; the number of new friends added per week increased from 7.4 to 10.5; and the average task acceptance time decreased by 8.5 seconds. 相似文献
4.
《国际计算机数学杂志》2012,89(11):2221-2243
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. 相似文献
5.
产品开发任务分配问题的多目标优化求解 总被引:1,自引:0,他引:1
针对目前产品开发任务分配问题研究存在的不足,给出了任务分配问题的数学描述和约束条件,提出了任务分配模型中的相关矩阵,并采用权重因子和极差变换法建立了多目标优化的目标函数.针对任务分配过程的动态性和不确定性,提出采用基于时序逻辑关系的动态分配蚁群算法进行优化计算,并分析了该方法的优点,给出了详细的算法步骤.最后通过仿真实验验证了所提出方法的可行性和有效性. 相似文献
6.
基于任务-资源分配图优化选取的网格依赖任务调度 总被引:3,自引:0,他引:3
任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图(T-RAG),在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优. 相似文献
7.
服务器执行任务产生的能耗是云计算系统动态能耗的重要组成部分。为降低云计算系统任务执行的总能耗,提出了一种基于能耗优化的最早完成时间任务调度方法,建立了服务器动态功率计算模型,基于动态功率的服务器执行能耗模型,以及云计算系统的能耗优化模型。调度策略根据任务的截止时间要求和在不同服务器上的执行能耗,选择不同的调度算法,以获得最小任务执行总能耗。实验结果证明,提出的任务调度方法,能够较好地满足任务截止时间的要求,降低云计算系统任务执行的总能耗。 相似文献
8.
传感器网络能源有效任务分配算法 总被引:3,自引:0,他引:3
为了延长网络生命期,传感器网络在设计过程中,通常利用节点本身的处理能力,进行网内处理,以减少通信量,节省能量.在传感器网络内引入处理或计算后,应用可以描述为一个任务集及任务之间的数据依赖关系.不同的任务分配方案导致应用执行所需的通信量和计算量不同,从而影响应用执行的能量消耗.在使用任务图对传感器网络应用描述的基础上,提出了传感器网络任务分配模型.由于应用的任务可划分为感知任务集和处理任务集,因而传感器网络中的任务分配可分成感知任务分配和处理任务分配两个阶段.针对处理任务分配,将其建模为二次0-1规划问题,并提出了分布式逐层优化分配算法OALL.仿真实验验证了分布式算法OALL的有效性. 相似文献
9.
任务调度技术是并行分布式系统中的关键技术之一,对系统的性能起着重要作用,但通常情况下大型系统的任务调度问题属于NP问题。而现代启发式生物进化算法是找出很多NP问题近似解的有效方法。本文将粒子群算法应用于基于可用性的网格系统调度中,提出了一种调度算法,对算法的性能进行了理论分析和模拟实验。结果表明:和最近文献中的基于可用性的调度算法SSAC相比,所提出的新算法在保证系统资源具有同样的可用性条件下,能够产生更好的调度长度。 相似文献
10.
11.
任务分配是群智协同计算和众包中的核心问题之一,即通过设计合理的任务分配策略,在满足任务约束条件下,将群智任务分配给合适的工作者,以提高群智任务的完成效率和结果质量。分析了目前任务分配方法存在的问题,总结并提出了一个通用的任务分配框架,并分别从工作者模型、任务模型、任务分配算法三个方面对国内外相关研究工作进行了分析、归纳和总结。提出了群智协同任务分配研究中的关键问题与今后的研究趋势。 相似文献
12.
针对当前反无人系统无法有效压制无人机的问题,使用多种拦截装备构建一种新的反无人机方法.传统多目标优化算法无法解决动态的任务分配问题,对此,提出一种基于深度Q网络(DQN)的多类型拦截装备复合式反无人机任务分配模型. DQN模块对任务分配问题进行初期决策.为了提高算法收敛速度和学习效率,该方法未采用下一时刻的状态来预测Q值,而是采用当前时刻的状态来预测Q值,消除训练过程中Q值过估计的影响.之后采用进化算法对决策结果进行优化,输出多个拦截方案.以国内某机场跑道周围区域开阔地为防护对象,构建反无人机系统的任务分配仿真环境,仿真结果验证了所提出方法的有效性.同时,将DQN与Double DQN方法相比,所提出改进DQN算法训练的智能体表现更为精确,并且算法的收敛性和所求解的表现更为优异.所提出方法为反无人机问题提供了新的思路. 相似文献
13.
14.
刘家骏 《计算机与数字工程》2015,(6)
建立了任务指派问题的数学模型,采用差异演化算法对其进行求解,给出了差异演化算法求解该问题的具体方案,对不同的任务指派问题算例进行了仿真实验。结果表明,算法可以有效、快速地找到任务指派问题的最优解。 相似文献
15.
An algorithm has been developed to dynamically schedule heterogeneous tasks on heterogeneous processors in a distributed system.
The scheduler operates in an environment with dynamically changing resources and adapts to variable system resources. It operates
in a batch fashion and utilises a genetic algorithm to minimise the total execution time. We have compared our scheduler to
six other schedulers, three batch-mode and three immediate-mode schedulers. Experiments show that the algorithm outperforms
each of the others and can achieve near optimal efficiency, with up to 100,000 tasks being scheduled 相似文献
16.
本文提出了分布式系统中各独立结点根据自身状态和系统反馈进行自适应,以使系统达到最优状态的一种机制。它突破了以往相关工作的一些重要限制,性能得到了很大的改善。 相似文献
17.
工作流系统中任务分配策略将对其系统运行性能有很大的影响,在分配任务时不仅需要考虑执行者对相应任务的熟悉度,还需分析执行者之间配合协作的默契程度.传统研究工作在进行工作流任务分配时缺乏对执行者工作负载、执行者之间协作相容性的综合考虑.为了实现有效的任务分配,首先通过分析历史日志的信息,对执行者间的协作相容性进行分析计算,在此基础上综合考虑执行者当前的任务负载,提出了基于协作相容性的、负载均衡式任务分配模型,并给出了多目标联合优化的任务分配方法,可提高整个流程实例的执行效率,并保持执行者间的负载均衡.提出4种相应的算法,并分析了算法的时间复杂度,进行了系统性的对比实验,评估了所提出方法的正确性和有效性. 相似文献
18.
A variety of problems in digital circuits, computer networks, automated manufacturing plants, etc., can be modeled as min-max systems. The cycle time is an important performance metric of such systems. In this paper, we focus on the cycle time assignment of min-max systems which corresponds to the pole assignment problem in traditional linear control systems. For the min-max system with max-plus inputs and outputs, we show that the cycle time can be assigned disjointedly by a state feedback, if and only if the system is reachable. Furthermore, a necessary and sufficient condition for the cycle time to be assigned independently by a state feedback is given. The methods are constructive, and some numerical examples are given to illustrate how the methods work in practice. 相似文献
19.
Simon Spacey Wayne Luk Daniel Kuhn Paul H.J. Kelly 《Journal of Parallel and Distributed Computing》2013
This paper introduces a method to combine the advantages of both task parallelism and fine-grained co-design specialisation to achieve faster execution times than either method alone on distributed heterogeneous architectures. The method uses a novel mixed integer linear programming formalisation to assign code sections from parallel tasks to share computational components with the optimal trade-off between acceleration from component specialism and serialisation delay. The paper provides results for software benchmarks partitioned using the method and formal implementations of previous alternatives to demonstrate both the practical tractability of the linear programming approach and the increase in program acceleration potential deliverable. 相似文献