基于相关任务分配的网络计划的算法

研究如何把具有紧前紧后关系的工作集分配给现有的人员(或设备),使完成工作集的总工期最短,并在此条件下,使得用于所有工作上的时间之和最少.文中揭示了任意改变一项工作的用时或最早开工时间引起其它工作的最早开工时间的变化规律,并在此基础上借鉴Floyd算法规则,建立了一种获取该问题最优解的迭代算法.这种算法能保证总工期随迭代过程递减,在总工期达到最短时,能保证总工期不变,而总用时随迭代过程递减.使用这种算法,不用绘制PERT图,只需输入每个人承担不同工作的用时以及各工作间的紧前紧后关系,即可算出最优分配方案、总工期及各项工作的最早开工时间和松弛时间.     

WMN中基于链路质量的信道分配算法

针对IEEE 802.11多射频多信道无线Mesh网络,提出一种基于链路质量的分布式信道分配算法,通过信道扫描收集所有信道信息,根据链路质量决定工作信道,同时在网络发生变化时对信道进行动态调整。仿真实验结果表明,与常用的集中式信道分配算法相比,该算法更能有效提升网络容量。     

集群服务器文件动态分配的改进算法

在分析MMPacking算法的基础上，提出了一种改进的文件分配算法。在按照MMPacking算法分配文件时，根据节点的文件累积需求度去完成文件的分配或复制，考虑了节点的剩余能力。文件分配在所有服务器节点中周期性地进行，每进行了一轮文件分配后，都要从第1个节点开始新的一轮分配。在开始新一轮分配前，服务器节点要按照服务器的剩余能力重新进行降序排列。在每轮分配中，每分配一次文件到某个服务器节点后，都要检测当前节点服务器的剩余能力是否大于下一节点的剩余能力，如果满足条件，则将重新开始新的一轮文件分配。改进后的算法降低了由于客户需求或服务器配置变化所要支出的额外成本，有效地达到了负载均衡的目的。仿真结果表明，改进后的算法优于MMPacking 算法。     

MapReduce模型中reduce阶段负载均衡分区算法研究

MapReduce是一种处理大规模数据的并行计算模型,针对传统模型中reduce阶段各个结点负载不均衡的问题,提出一种reduce阶段负载均衡分区算法.算法将map阶段产生的中间数据划分为更多的分区,减少了每个分区的工作量,每次给reducetask分配一个分区,reducetask完成一个分区的工作之后会继续获得新的分区,直到所有的分区都被分配完毕,实现了动态调节reducetask的负载.还改进了MapReduce的通信协议来支持算法并且设计了新的容错机制.最后,通过重写Hadoop平台内核实现了算法并进行了实验分析,结果表明,该算法在不影响MapReduce模型的情况下显著的缩短了任务的处理时间.     

异构多核处理器的任务调度算法

在研究Min-min、Max-min算法和Sufferage算法基础上,针对异构多核处理器的特点,提出一种任务静态调度算法——自适应分段Sufferage算法（Adaptive Segmented Sufferage,ASS）。该算法以最早完成时间和负载均衡为目标进行任务分配,先将任务分配分成两个阶段：在第一个阶段以最少完成时间作为分配原则进行分配,选择单位时间内节省时间最多的任务先分配;在第二个阶段以负载均衡为分配原则进行分配,选择执行时间大的任务先分配。然后选取不同调节参数,对任务进行多次重新分配,以最小的最大完成时间为最后分配结果,实现自适应调节。通过实验验证,该算法在实现最少完成时间的前提下能很好地达到负载均衡。     

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

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

用于OFDMA系统的延迟公平资源调度方法

正交频分复用接入(OFDMA)具有传输速率高,带宽分配灵活等特点。文章提出了一种延迟公平资源调度算法。算法通过控制无线资源的分配来保证所有用户的等效延迟相等,从而使得所有用户在服务质量上保持公平。该算法不需要迭代计算,计算复杂度较低,适用于快速资源的分配应用环境。     

扩声系统中信源对广播分区的计算机分配

大型扩声系统要完成多信源对多广播分区的分配。通过本文提出的三级分配网络及相应的自动分配算法,可以使用计算机完成这种分配操作。     

基于梳状导频的OFDM系统子载波和功率分配

提出一种根据梳状导频进行信道估计得到带有误差的信道信息,来完成自适应比特装载的算法。把正交频分复用子载波进行分组,利用基于梳状导频的信道估计对信道时变进行跟踪,即时获取信道信息来完成分配算法。将子信道的分配和子信道上的比特、功率分配分离开来,以降低计算复杂度。仿真结果表明与静态信道分配方案的等比特分配算法相比,该算法可以节约发送功率大于10 dB。     

改进二进制粒子群算法及在频谱分配中的应用

收敛速度是衡量算法有效性的重要标准,当前频谱分配算法普遍存在收敛过慢的缺陷。为更高效地完成频谱分配,对二进制粒子群算法的速度和位置更新策略在离散域作了全新诠释,提出了二进制离散速度的概念,并以其作为决定位置参数变或不变的异或因子,更好地平衡了算法的开发性能与探索性能。实验表明,改进二进制粒子群算法能够更高效、快速地完成频谱分配。     

面积最大优先调度的预约回填算法

传统backfilling算法是在先来先服务基础上,将小作业回填到空闲CPU,以提高CPU利用率。该算法偏向小作业,大作业也会因为长期等待出现饥饿现象。当空闲CPU数无法满足算法中小作业回填要求时,系统仍有部分CPU闲置,难以更好地提高CPU利用率。本文中提出的算法以作业所需CPU数及预估运行时间构成的二维面积作为优先调度的条件,引入二级优先级和预约算法消除大作业的饥饿现象,减少回填作业CPU数,相应增加预估运行时间,更好提高CPU利用率。实验证明,该算法比传统backfilling算法在保证用户公平性,缩短作业平均响应时间及CPU利用率方面有所提高。     

一种基于流作业的网格作业调度研究

在基于网格环境的一些网格应用中,用户需要提交一种作业类型,该作业可以被分解为逻辑上独立的元作业,这些元作业不存在依赖和通讯关系,并且它们的执行需要大量的数据移动。针对这种作业类型,本文提出了一种基于流作业的网格调度模型。在该模型中,这些独立的元作业像"流"一样自主地流向各个计算节点去执行,各计算节点接收的流量取决于其计算能力,并避免"断流"问题。同时,该模型还分离了作业流和数据流,实现了作业逻辑控制和数据控制的分离,提高了调度的灵活性。本文将该调度模型应用于药物虚拟筛选应用中,该模型能够充分利用计算节点的计算能力。     

A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time

This paper is about scheduling parallel jobs, i.e. which can be executed on more than one machine at the same time. Malleable jobs is a special class of parallel jobs. The number of machines a malleable job is executed on may change during its execution.In this work, we consider the NP-hard problem of scheduling malleable jobs to minimize the total weighted completion time (or mean weighted flow time). For this problem, we introduce the class of “ascending” schedules in which, for each job, the number of machines assigned to it cannot decrease over time while this job is being processed.We prove that, under a natural assumption on the processing time functions of jobs, the set of ascending schedules is dominant for the problem. This result can be used to reduce the search space while looking for an optimal solution.     

基于ECT的优先权约束作业调度策略研究

为了协调网格计算中异构资源在多用户之间的合理共享,满足不同用户需求,该文提出一种基于ECT的优先权约束作业调度策略。该策略充分考虑不同作业的期望完成时间,并通过为不同级别用户设置优先级,使得高优先权用户的作业优先执行,保证绝大多数作业在期望完成时间之内完成,同时平衡了各种资源的利用率。该策略解决了网格环境下不同类别用户无冲突共享资源问题,提高了用户满意程度,实现了作业与异构资源之间的合理匹配。     

Scheduling n jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs

This study considers the problem of scheduling n jobs, each job having an arrival time, a processing time and a due date, on a single machine with the dual objective of minimizing the maximum lateness subject to obtaining a minimum number of tardy jobs. A simple procedure is introduced to identify two critical jobs from which the maximum lateness is generated for a given sequence. The sequence of jobs between two critical jobs inclusive is called the critical path. On the basis of the critical path, Carlier's binary branching rule is adopted to minimize the maximum lateness. By fixing the position of these two critical jobs for maintaining the minimum maximum lateness, the sequence can further be reordered to reduce the number of tardy jobs. A branch and bound algorithm is presented for this purpose. The algorithm can solve problems with 50 jobs optimally within 5 seconds on a PC Pentium-100.     

Branch and Bound Algorithms for Single Machine Scheduling with Batching to Minimize the Number of Late Jobs

This paper considers the problem of scheduling a single machine to minimize the number of late jobs in the presence of sequence-independent family set-up times. The jobs are partitioned into families, and a set-up time is required at the start of each batch, where a batch is a maximal set of jobs in the same family that are processed consecutively. We design branch and bound algorithms that have several alternative features. Lower bounds can be derived by relaxing either the set-up times or the due dates. A first branching scheme uses a forward branching rule with a depth-first search strategy. Dominance criteria, which determine the order of the early jobs within each family and the order of the batches containing early jobs, can be fully exploited in this scheme. A second scheme uses a ternary branching rule in which the next job is fixed to be early and starting a batch, to be early and not starting a batch, or to be late. The different features are compared on a large set of test problems, where the number of jobs ranges from 30 to 50 and the number of families ranges from 4 to 10.     

A PTAS for parallel batch scheduling with rejection and dynamic job arrivals

In the parallel batch scheduling model, a group of jobs can be scheduled together as a batch while the processing time of this batch is the greatest processing time among its members; in the model of scheduling with rejection, any job can be rejected with a corresponding penalty cost added to the objective value. In this paper, we present a PTAS for the combined model of the above two scheduling models where jobs arrive dynamically. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected ones. Our basic approaches are dynamic programming and roundings.     

Job scheduling in a group technology environment for a single facility

A dynamic programming-based formulation has been developed to schedule jobs effectively in the group technology environment. The jobs may form several distinct groups to be scheduled for processing on a single facility. Switching from group to group requires a major change in the setup of the facility while jobs within a group can be accommodated with minor adjustments which take only small setup times. The group technology concept becomes a simplifying factor in the DP formulation of this scheduling problem facilitating the exact solution faster with more jobs than it was possible ever before. Computational experience with a set of example problems is also provided.     

Measures of the potential for load sharing in distributed computingsystems

We are concerned with the problem of determining the potential for load balancing in a distributed computing system. We define a precise measure, called the number of sharable jobs, of this potential in terms of the number of jobs that can usefully be transferred across sites in the system. Properties of this measure are derived, including a general formula for its probability distribution, independent of any particular queuing discipline. A normalized version of the number of sharable jobs, called the job sharing coefficient, is defined. From the general formula, the probability distribution of the number of sharable jobs is computed for three important queuing models and exact expressions are derived in two cases. For queuing models in which an exact expression for the probability distribution of the number of sharable jobs is difficult to obtain, two methods are presented for numerical computation of this distribution. The job sharing coefficient is plotted against traffic intensity for various values of system parameters. Both of these measures are shown to be useful analytic tools for understanding the characteristics of load sharing in distributed systems and can aid in the design of such systems     

Scheduling deteriorating jobs on a single machine subject to breakdowns

We investigate the problem of scheduling a set of jobs to minimize the expected makespan or the variance of the makespan. The jobs are subject to deteriorations which are expressed as linear increments of the processing requirements. The machine is subject to preemptive-resume breakdowns with exponentially distributed uptimes and downtimes. It has been well known in the classical models that the expectation and variance of the makespan of deteriorating jobs can be minimized analytically by an index policy if no machine breakdowns are involved. Such basic features, however, change dramatically when breakdowns and deteriorations are present together. In this paper, we derive conditions for jobs to be processible in the sense that they will be eventually completed, and the characteristics of the time that a job occupies the machine. We further find that the expected makespan can still be minimized by a simple index policy that is independent of the breakdown process, but this is no longer the case for the variance of the makespan.