On multiprocessor task scheduling using efficient state space search approaches

Obtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A^* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable.     

多Agent系统中基于招投标的任务分配优化

在利用多Agent系统辅助生产任务分配过程中,为避免仅凭招投标结果来确定任务分配方案时只能获得局部最优的问题,提出了一种生产任务分配全局优化方法。建立了基于招投标结果的生产任务分配优化目标函数,设计了退火进化算法,实现生产任务的综合评标。通过实例验证说明算法求解该问题可行有效,便于获得生产任务分配的全局最优方案。     

Using task migration to improve non-contiguous processor allocation in NoC-based CMPs

In this paper, a processor allocation mechanism for NoC-based chip multiprocessors is presented. Processor allocation is a well-known problem in parallel computer systems and aims to allocate the processing nodes of a multiprocessor to different tasks of an input application at run time. The proposed mechanism targets optimizing the on-chip communication power/latency and relies on two procedures: processor allocation and task migration. Allocation is done by a fast heuristic algorithm to allocate the free processors to the tasks of an incoming application when a new application begins execution. The task-migration algorithm is activated when some application completes execution and frees up the allocated resources. Task migration uses the recently deallocated processors and tries to rearrange the current tasks in order to find a better mapping for them. The proposed method can also capture the dynamic traffic pattern of the network and perform task migration based on the current communication demands of the tasks. Consequently, task migration adapts the task mapping to the current network status. We adopt a non-contiguous processor allocation strategy in which the tasks of the input application are allowed to be mapped onto disjoint regions (groups of processors) of the network. We then use virtual point-to-point circuits, a state-of-the-art fast on-chip connection designed for network-on-chips, to virtually connect the disjoint regions and make the communication latency/power closer to the values offered by contiguous allocation schemes. The experimental results show considerable improvement over existing allocation mechanisms.     

Decentralized task allocation for surveillance systems with critical tasks

This paper considers the problem of assigning a set of tasks to a set of heterogeneous agents under the additional assumptions that some tasks must be necessarily allocated and therefore are critical for the assignment problem, and that each agent can execute a limited number of tasks. In order to solve this problem in a decentralized way (i.e., without any form of central supervision), we develop an extension of an algorithm proposed in the recent literature. After analyzing convergence and communication requirement of the algorithm, a set of numerical simulations is provided to confirm the effectiveness of the proposed approach.     

Decentral task allocation for industrial AGV-systems with resource constraints

Automated Guided Vehicles (AGVs) form a large and important part of the logistics transportation systems in today's industry and are widely used, especially in Europe. Today's AGV-systems offered by global manufacturers almost all operate under some form of centralized control where a single central controller coordinates the entire fleet of AGVs. There is a trend towards decentralized control of these systems where AGVs make individual decisions that promote the flexibility, robustness and scalability of transport. However, its practical implementation seems to be in its infancy. In addition to the lack of practical implementation of decentralized control in industrial AGV-systems, we have observed a research gap in intelligent resource management of AGV-systems, which we have tried to address in previous work by proposing a more intelligent resource management approach. In this paper, we have addressed both the perceived lack of practical decentralized AGV control and the lack of intelligent resource management by proposing a decentralized task allocation algorithm based on sequential single-item auctions, taking into account resource constraints, and in which our intelligent resource management approach from previous work is introduced. We have benchmarked our new approach to a genetic algorithm-based task-allocation solver that uses “threshold-100”-charging as a resource management strategy. The result of the proposal is a decentralized task-allocation architecture under resource constraints that could be used in current AGV-systems to add more decentralized features to the fleet.     

Cost-oriented task allocation and hardware redundancy policies in heterogeneous distributed computing systems considering software reliability

Task allocation policy and hardware redundancy policy for distributed computing system (DCS) are of great importance as they affect many system characteristics such as system cost, system reliability and performance. In recent years, abundant research has been carried out on the optimal task allocation and/or hardware redundancy problem, most of which took a reliability-oriented approach, i.e., the optimization criterion was system reliability maximization. Nevertheless, besides system reliability, other system characteristics such as system cost may be of great concern to management. In this paper, we take a cost-oriented approach to the optimal task allocation and hardware redundancy problem for DCS, which addresses both system cost and system reliability issues. A system cost model which could reflect the impact of system unreliability on system cost is developed, and by minimizing the total system cost, a satisfactory level of system reliability could be reached simultaneously. In the reliability modeling and analysis of DCS, we take both hardware reliability and software reliability into account. Two numerical examples are given to illustrate the formulation and solution procedures, in which genetic algorithm is used. Results show that based on the developed system cost model, appropriate decision-makings on task allocation and hardware redundancy policies for DCS could be made, and the result obtained seems to be a fairly good trade-off between system cost and system reliability.     

Social-welfare based task allocation for multi-robot systems with resource constraints

This paper aims to propose a distributed task allocation algorithm for a team of robots that have constraints on energy resources and operate in an unknown dynamic environment. The objective of the allocation is to maximize task completion ratio while minimizing resource usage. The approach we propose is inspired by the social welfare in economics that helps extend the combined operational lifetime of the team by balancing resource consumptions among robots. This social welfare based task allocation method positions a robot team appropriately in preparedness for dynamic future events and enables to achieve the objectives of the system flexibly depending on the application context. Our simulation-based experiments show that the proposed algorithm outperforms a typical market-based approach in various scenarios.     

A multi-objective algorithm for task scheduling and resource allocation in cloud-based disassembly

Some manufacturers outsource their disassembly tasks to professional factories, each factory of them has specialized in its disassembly ability. Different disassembly facilities are usually combined to execute disassembly tasks. This study proposes the cloud-based disassembly that abstracts ability of the disassembly factory as the disassembly resource, the disassembly resource is then able to be allocated to execute disassembly tasks. Based on this concept, the cloud-based disassembly system is proposed, which provides the disassembly service according to the user requirement. The disassembly service is the execution plan for disassembly tasks, which is the result of scheduling disassembly tasks and allocating disassembly resources. To formally describe the disassembly service, this paper builds a mathematical model that considers the uncertainty nature of the disassembly process and precedence relationships of disassembly tasks. Two objectives including minimizing the expected total makespan and minimizing the expected total cost of the disassembly service are also discussed. The mathematical model is NP-complete, a multi-objective genetic algorithm based on non-dominated sorting genetic algorithm II is designed to address the problem. Computation results show that the proposed algorithm performs well, the algorithm generates a set of Pareto optimal solutions. The user can choose a preferred disassembly service among Pareto optimal solutions.     

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.     

基于效用函数的多机器人系统任务分配

目前所采用的多机器人系统任务分配方法大多都忽略了任务分配的解质量问题。从定量的角度出发,提出了一种基于效用函数的多机器人系统任务分配策略,在机器人能力向量和子任务要求的能力向量基础上,建立了效用函数的数学模型,根据效用函数大小进行任务分配。仿真实验在足球机器人仿真比赛平台上进行,结果表明该任务分配算法对异构多机器人系统合作具有很好的通用性,且算法快速简单,能够实现任务到机器人的最优映射。     

Particle model to optimize resource allocation and task assignment

This paper presents a novel generalized particle model for the parallel optimization of the resource allocation and task assignment in complex environment of enterprise computing. The generalized particle model (GPM) transforms the optimization process into the kinematics and dynamics of massive particles in a force-field. The GPM approach has many advantages in terms of the high-scale parallelism, multi-objective optimization, multi-type coordination, multi-degree personality, and the ability to handle complex factors. Simulations show the effectiveness and suitability of the proposed GPM approach to optimize the enterprise computing.     

Elastic neural network method for multi-target tracking task allocation in wireless sensor network

Aiming at the task allocation of collaborative technique in wireless sensor network, a method for optimized task allocation based on elastic neural network is proposed under the background of multi-sensor tracking. First a model of multi-coalition tracking multi-target is designed. Then disjoint fully connected subgraphs of neurons are constructed to solve the problem of optimized task allocation in tracking multi-target and the increment of system energy consumption when dynamic coalitions compete and conflict for the resource of sensor nodes. Compared with the conventional method, simulation results show that the energy consumption of the tracking system is reduced significantly and the tracking accuracy is improved greatly, demonstrating the effectiveness of elastic neural network in handling the optimized task allocation problem of multi-sensor tracking multi-target.     

Locality-sensitive task allocation and load balancing in networked multiagent systems: Talent versus centrality

With the development of large scale multiagent systems, agents are always organized in network structures where each agent interacts only with its immediate neighbors in the network. Coordination among networked agents is a critical issue which mainly includes two aspects: task allocation and load balancing; in traditional approach, the resources of agents are crucial to their abilities to get tasks, which is called talent-based allocation. However, in networked multiagent systems, the tasks may spend so much communication costs among agents that are sensitive to the agent localities; thus this paper presents a novel idea for task allocation and load balancing in networked multiagent systems, which takes into account both the talents and centralities of agents. This paper first investigates the comparison between talent-based task allocation and centrality-based one; then, it explores the load balancing of such two approaches in task allocation. The experiment results show that the centrality-based method can reduce the communication costs for single task more effectively than the talent-based one, but the talent-based method can generally obtain better load balancing performance for parallel tasks than the centrality-based one.     

多信道无线通信功率分配的最优化决策

研究了基于有损Gilbert-Elliott信道的多信道无线通信功率分配的最优化决策问题,利用部分可观测的马尔可夫决策过程（POMDP）和数学语言建立并描述理论模型,提出了具有一般性的功率分配方案,并给出问题的最优决策的各项性质和特征。在三维信道的通信系统上,进一步给出最优决策的空间结构,利用线性规划仿真验证了其正确性,并分析了最优决策随信道转移概率的变化趋势。     

基于机器人效用函数的多机器人系统任务分配

针对现有的多机器人系统任务分配方法只是采用算法进行寻优,而没有将任务分配结果加以量化的缺陷,提出了一种基于机器人效用函数的多机器人系统任务分配新方法。该方法首先定义机器人效用函数,并说明其可解;接着给出了最佳任务分配方案的定义,并证明其存在性和惟一性;最后通过实例对本方法的有效性进行了验证。     

基于信息素的多机器人协作任务分配

针对多机器人系统未知环境下自主任务分配问题,提出了将虚拟吸引信息素和虚拟排斥信息素相结合的多机器人任务分配方法。在动态未知环境下,进行了多机器人协作搜集实验,实验结果表明所提方法既可以避免多个机器人集中在一个空间内造成冲突加剧的现象,又可以实现多机器人自主地进行任务分配目的。     

Efficient allocation of resources in multiple heterogeneous Wireless Sensor Networks

Wireless Sensor Networks (WSNs) are useful for a wide range of applications, from different domains. Recently, new features and design trends have emerged in the WSN field, making those networks appealing not only to the scientific community but also to the industry. One such trend is the running different applications on heterogeneous sensor nodes deployed in multiple WSNs in order to better exploit the expensive physical network infrastructure. Another trend deals with the capability of accessing sensor generated data from the Web, fitting WSNs in novel paradigms of Internet of Things (IoT) and Web of Things (WoT). Using well-known and broadly accepted Web standards and protocols enables the interoperation of heterogeneous WSNs and the integration of their data with other Web resources, in order to provide the final user with value-added information and applications. Such emergent scenarios where multiple networks and applications interoperate to meet high level requirements of the user will pose several changes in the design and execution of WSN systems. One of these challenges regards the fact that applications will probably compete for the resources offered by the underlying sensor nodes through the Web. Thus, it is crucial to design mechanisms that effectively and dynamically coordinate the sharing of the available resources to optimize resource utilization while meeting application requirements. However, it is likely that Quality of Service (QoS) requirements of different applications cannot be simultaneously met, while efficiently sharing the scarce networks resources, thus bringing the need of managing an inherent tradeoff. In this paper, we argue that a middleware platform is required to manage heterogeneous WSNs and efficiently share their resources while satisfying user needs in the emergent scenarios of WoT. Such middleware should provide several services to control running application as well as to distribute and coordinate nodes in the execution of submitted sensing tasks in an energy-efficient and QoS-enabled way. As part of the middleware provided services we present the Resource Allocation in Heterogeneous WSNs (SACHSEN) algorithm. SACHSEN is a new resource allocation heuristic for systems composed of heterogeneous WSNs that effectively deals with the tradeoff between possibly conflicting QoS requirements and exploits heterogeneity of multiple WSNs.     

Policy based resource allocation in IaaS cloud

In present scenario, most of the Infrastructure as a Service (IaaS) clouds use simple resource allocation policies like immediate and best effort. Immediate allocation policy allocates the resources if available, otherwise the request is rejected. Best-effort policy also allocates the requested resources if available otherwise the request is placed in a FIFO queue. It is not possible for a cloud provider to satisfy all the requests due to finite resources at a time. Haizea is a resource lease manager that tries to address these issues by introducing complex resource allocation policies. Haizea uses resource leases as resource allocation abstraction and implements these leases by allocating Virtual Machines (VMs). Haizea supports four kinds of resource allocation policies: immediate, best effort, advanced reservation and deadline sensitive. This work provides a better way to support deadline sensitive leases in Haizea while minimizing the total number of leases rejected by it. Proposed dynamic planning based scheduling algorithm is implemented in Haizea that can admit new leases and prepare the schedule whenever a new lease can be accommodated. Experiments results show that it maximizes resource utilization and acceptance of leases compared to the existing algorithm of Haizea.     

An effective adaptive adjustment model of task scheduling and resource allocation based on multi-stakeholder interests in cloud manufacturing

Cloud manufacturing (CMfg) is a new manufacturing mode emerging in the global manufacturing industry. One of the key issues in CMfg is task scheduling and resource allocation (TSRA), which is to allocate suitable resources for multi-tasks while satisfying the interests of multi-stakeholders. Among them, dynamic TSRA is a challenging but crucial problem to ensure the smooth operation of CMfg system since it involves several exceptions. Under these contexts, this study first analyzes the optimized objectives and conflict situations that may damage the interests of multi-stakeholders in dynamic TSRA process. And then, four adaptive adjustment strategies are designed to deal with these conflict situations and ensure the smooth operation. After that, an adaptive adjustment TSRA model based on multi-stakeholder interests (TSRA-MSI) is proposed. To solve the problem, a multi-objective algorithm called HHO-NSGA2 is proposed by combining the advantages of standard Harris Hawks Optimizer and Non-dominated Sorting Genetic Algorithm-II, which contains several problem-specific optimization strategies. In the numerical experiments, the superiority of HHO-NSGA2 is demonstrated by comparing with other five algorithms in terms of convergence, diversity, and comprehensive performance. Finally, a case study is conducted under the actual auto parts production environment, and the results also demonstrate the effectiveness of the proposed TSRA-MSI model and HHO-NSGA2 algorithm.     

多机器人系统任务分配效用评价算法

为了提高复杂环境中多机器人系统任务分配的决策质量,获取准确、客观的效用评价,提出了一种基于自适应神经-模糊推理系统(adaptive neuro-fuzzy inference system,ANFIS)的效用评价算法ANFIS-UE.设计了基于ANFIS的效用评价网络结构,并采用Q学习对效用评价网络的参数进行学习.利用ANFIS优越的函数逼近能力和泛化能力,提高了效用函数的学习效率,能够对连续的状态输入产生连续的效用评价值.实验结果表明,该算法获得的效用评价相对更准确,从而提高了任务分配方案的质量.