Task Offloading and Resource Allocation in NOMA-VEC:A Multi-Agent Deep Graph Reinforcement Learning Algorithm

Vehicular edge computing(VEC)is emerging as a promising solution paradigm to meet the requirements of compute-intensive applications in internet of vehicle(IoV).Non-orthogonal multiple access(NOMA)has advantages in improving spectrum efficiency and dealing with bandwidth scarcity and cost.It is an encouraging progress combining VEC and NOMA.In this paper,we jointly optimize task offloading decision and resource allocation to maximize the service utility of the NOMA-VEC system.To solve the optimization problem,we propose a multiagent deep graph reinforcement learning algorithm.The algorithm extracts the topological features and relationship information between agents from the system state as observations,outputs task offloading decision and resource allocation simultaneously with local policy network,which is updated by a local learner.Simulation results demonstrate that the proposed method achieves a 1.52%∼5.80%improvement compared with the benchmark algorithms in system service utility.

基于异构环境的Out-Tree任务图的调度算法

分布式应用程序的有效调度是异构计算系统中的一个关键问题。目前已有的Out-Tree任务图的调度算法大多基于同构环境而开发,未考虑处理机的异构性,导致调度的效率较低。针对异构计算环境,提出一个基于列表和任务复制的Out-Tree任务图的静态启发式贪心调度算法,其时间复杂度为O(hv2 p),其中h、v和p分别表示任务图的高度、任务个数和调度使用的处理机个数。实验结果表明,相比其他算法,该算法能提供调度长度较短、处理机使用较少的有效调度,其应用性更强。

实时分布系统中Out-Tree任务的调度与检查点策略

针对实时分布系统中的Out-Tree任务,提出了一种启发式的调度算法(HSA—OT),并开发了一种多处理机上的最优检查点策略。该调度算法能够保证任务的调度长度最小,所需处理器数目尽量少,没有处理机间通信开销。该检查点策略没有检查点全局一致性开销,可保证各处理机的失效率最低。

异构环境下Out-Tree任务图的调度算法

Out-Tree任务图是任务调度问题中的基本结构,现有的多数算法在调度该任务图时凸显出处理器浪费的问题,从而导致算法调度效果欠佳。针对该问题,结合任务复制的调度策略,提出一种基于平均值的启发式算法。该算法在不增加算法调度长度的情况下,尽可能将任务调度至已有的处理器中执行,注重平衡处理器的负载,达到减少使用处理器的目的。实验结果表明,与TDS算法相比,该算法使用的处理器个数较少,且效率较高。

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

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

一个调度Out-Tree任务图的新算法

OutTree任务图的调度研究可有效解决分治问题的并行计算。针对该类任务图,提出了一个新的调度算法。首先为各任务引入新定义,然后基于该定义计算各任务的优先级,进行调度。调度中,为节省处理器,在不改变调度长度的情况下,将任务尽可能地分配到已用处理器上。实验表明新算法的调度性能优于其他算法。

ACS-based resource assignment and task scheduling in grid

To solve the deadlock problem of tasks that the interdependence between tasks fails to consider during the course of resource assignment and task scheduling based on the heuristics algorithm, an improved ant colony system （ACS） based algorithm is proposed. First, how to map the resource assignment and task scheduling （RATS） problem into the optimization selection problem of task resource assignment graph （TRAG） and to add the semaphore mechanism in the optimal TRAG to solve deadlocks are explained. Secondly, how to utilize the grid pheromone system model to realize the algorithm based on ACS is explicated. This refers to the construction of TRAG by the random selection of appropriate resources for each task by the user agent and the optimization of TRAG through the positive feedback and distributed parallel computing mechanism of the ACS. Simulation results show that the proposed algorithm is effective and efficient in solving the deadlock problem.

Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks

Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems.Although many scheduling algorithms have been proposed,emergency tasks,characterized as importance and urgency（e.g.,observation tasks orienting to the earthquake area and military conflict area）,have not been taken into account yet.Therefore,it is crucial to investigate the satellite integrated scheduling methods,which focus on meeting the requirements of emergency tasks while maximizing the profit of common tasks.Firstly,a pretreatment approach is proposed,which eliminates conflicts among emergency tasks and allocates all tasks with a potential time-window to related orbits of satellites.Secondly,a mathematical model and an acyclic directed graph model are constructed.Thirdly,a hybrid ant colony optimization method mixed with iteration local search（ACO-ILS） is established to solve the problem.Moreover,to guarantee all solutions satisfying the emergency task requirement constraints,a constraint repair method is presented.Extensive experimental simulations show that the proposed integrated scheduling method is superior to two-phased scheduling methods,the performance of ACO-ILS is greatly improved in both evolution speed and solution quality by iteration local search,and ACO-ILS outperforms both genetic algorithm and simulated annealing algorithm.

Scheduling algorithm based on critical tasks in heterogeneous environments

Heterogeneous computing is one effective method of high performance computing with many advantages. Task scheduling is a critical issue in heterogeneous environments as well as in homogeneous environments. A number of task scheduling algorithms for homogeneous environments have been proposed, whereas, a few for heterogeneous environments can be found in the literature. A novel task scheduling algorithm for heterogeneous environments, called the heterogeneous critical task （HCT） scheduling algorithm is presented. By means of the directed acyclic graph and the gantt graph, the HCT algorithm defines the critical task and the idle time slot. After determining the critical tasks of a given task, the HCT algorithm tentatively duplicates the critical tasks onto the processor that has the given task in the idle time slot, to reduce the start time of the given task. To compare the performance of the HCT algorithm with several recently proposed algorithms, a large set of randomly generated applications and the Gaussian elimination application are randomly generated. The experimental result has shown that the HCT algorithm outperforms the other algorithm.

面向多TASK基于有向图的故障诊断方法研究（英文）

针对飞机故障在系统内、系统间传播的机理,提出面向多TASK的功能有向图故障诊断方法,进行故障诊断优化设计和复训人员的高效培训。首先基于飞机手册建立了航线可更换组件的功能有向图模型,表征了故障传播关系,对其进行矩阵化处理,再利用可达分层法和节点深度结合进行层次化处理,最后基于全局风险影响度给出故障定位与剪枝算法,确定LRU的故障诊断优先级。对故障诊断方法进行实例化,结果表明该方法缩短了诊断的时间。

Dependent task assignment algorithm based on particle swarm optimization and simulated annealing in ad-hoc mobile cloud

In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.

EZDCP:A new static task scheduling algorithm with edge-zeroing based on dynamic critical paths

A new static task scheduling algorithm named edge-zeroing based on dynamic critical paths is proposed. The main ideas of the algorithm are as follows: firstly suppose that all of the tasks are in different clusters; secondly, select one of the critical paths of the partially clustered directed acyclic graph; thirdly, try to zero one of graph communication edges; fourthly, repeat above three processes until all edges are zeroed; finally, check the generated clusters to see if some of them can be further merged without increasing the parallel time. Comparisons of the previous algorithms with edge-zeroing based on dynamic critical paths show that the new algorithm has not only a low complexity but also a desired performance comparable or even better on average to much higher complexity heuristic algorithms.

Modeling and Decoupling of Coupling Tasks in Collaborative Development Process of Complicated Electronic Products

It is important to improve the development efficiency of decoupling a coupling task package according to the information relevancy relation between development tasks in the collaborative development process of complicated electronic products.In order to define the task coupling model in the development process,the weighted directed graph based on the information relevancy is established,and the correspondence between weighted directed graph model and numerical design structure matrix model of coupling tasks is introduced.The task coupling model is quantized,thereby the interactivity matrix of task package is built.A multi-goal task decoupling method based on improved genetic algorithm is proposed to decouple the task coupling model,which transforms the decoupling of task package into a multi-goal optimization issue.Then the improved genetic algorithm is used to solve the interactivity matrix of coupling tasks.Finally,the effectiveness of this decomposition method is proved by using the example of task package decoupling of collaborative development of a radar’s phased array antenna.

Clustering and Scheduling Method Based on Task Duplication

A new heuristic approach that resembles the evolution of interpersonal relationships in human society is put forward for the problem of scheduling multitasks represented by a directed acyclic graph. The algorithm includes dynamic-group, detachgraph and front-sink components. The priority rules used are new. Relationship number, potentiality, weight and merge degree are defined for cluster＇s priority, and task potentiality for tasks＇ priority. Experiments show the algorithm could get good result in short time. The algorithm produces another optimal solution for the classic MJD benchmark. Its average performance is better than five latter-day representative algorithms, especially six benchmarks of the nines.

Time optimization for workflow scheduling based on the combination of task attributes

In order to reduce the scheduling makespan of a workflow,three list scheduling algorithms,namely,level and out-degree earliest-finish-time(LOEFT),level heterogeneous selection value(LHSV),and heterogeneous priority earliest-finish-time(HPEFT)are proposed.The main idea hidden behind these algorithms is to adopt task depth,combined with task out-degree for the accurate analysis of task prioritization and precise processor allocation to achieve time optimization.Each algorithm is divided into three stages:task levelization,task prioritization,and processor allocation.In task levelization,the workflow is divided into several independent task sets on the basis of task depth.In task prioritization,the heterogeneous priority ranking value(HPRV)of the task is calculated using task out-degree,and a non-increasing ranking queue is generated on the basis of HPRV.In processor allocation,the sorted tasks are assigned one by one to the processor to minimize makespan and complete the task-processor mapping.Simulation experiments through practical applications and stochastic workflows confirm that the three algorithms can effectively shorten the workflow makespan,and the LOEFT algorithm performs the best,and it can be concluded that task depth combined with out-degree is an effective means of reducing completion time.

A Hybrid Task Scheduling Algorithm in Grid

Task scheduling in Grid has been proved to be NP-complete problem. In this paper, to solve this problem, a Hybrid Task Scheduling Algorithm in Grid (HTS) has been presented, which joint the advantages of Ant Colony and Genetic Algorithm. Compared with the related work, the result shows that the HTS algorithm significantly surpasses the previous approaches in schedule length ratio and speedup.

Collaborative task planning for an internet based multi-operator multi-robot system

In an Internet based multi-operator and multi-robot system (IMOMR), operators have to work collaboratively to overcome the constraints of space and time. Inherently, the activities among them can be defined as a computer-supported cooperative work (CSCW). As a practical application of CSCW, a collaborative task planning system (CTPS) for IMOMR is proposed in this paper on the basis of Petri nets. Its definition, components design, and concrete implementation are given in detail, respectively. As a result, a clear collaboration mechanism of multiple operators in an IMOMR is obtained to guarantee their task planning.

基于邻域采样的多任务图推荐算法

近年来,图神经网络(GNN)成为解决协同过滤的主流方法之一。它通过构建用户-物品图,模拟用户与物品的交互关系,并用GNN学习它们的特征表示。尽管现有在模型结构上的研究已取得了较大进展,但如何在图结构上更有效地进行负采样仍未有效解决。为此,提出一种基于邻域采样的多任务图推荐算法。该算法提出了一种基于GNN的邻域采样策略,该策略以每个用户为中心构建子图,将次高阶物品作为用户邻域采样的负样本,可以更有效地挖掘强负样本并提高采样质量。通过GNN对图结点进行信息聚合与特征提取,得到结点的最终嵌入表示。设计一种余弦边际损失来过滤部分冗余负样本,以有效减少采样过程中的噪声数据。同时,该算法引入了多任务策略对模型进行联合优化,以增强模型的泛化能力。在3个公开数据集上进行的大量实验表明,该算法在大多数情况下明显优于其他主流算法。

面向无人机海上侦察任务的自适应粒度分解策略研究

无人机海上侦察作战任务自动规划的前提是任务分解,分解策略的通用性和分解粒度的合理性直接影响任务规划的速度和实际效果。对无人机海上侦察任务具有随机性强、复杂度高、动态性明显等特点,提出了一种基于军事领域知识库的无人机海上侦察任务自适应粒度分解策略,构建了无人机海上侦察领域知识图谱和自适应粒度任务分解模型,并以海上编队护航背景下的无人机侦察任务为例,实施了任务分解策略验证,结果表明分解策略较传统任务分解方法具有更佳的稳定性和适应性。