一类处理机具有准备时间的恒速机排序问题

讨论任务的加工是不可中断,处理机是恒速机且处理机具有准备时间的排序问题,目标函数是极小化最大完工时间.对于2台处理机的情况,已经有了一个与处理机加工速度有关的排序的界.研究了对于m(m≥2)台处理机的一种特殊情况,给出了一个与处理机加工速度有关的算法的界.     

考虑释放时间和调度顺序的可分任务调度模型

针对处理机具有任意释放时间的异构并行与分布式系统,通过寻找最优的处理机调度顺序和任务分配方案,使得任务的完成时间达到最短.首先,在给定处理机调度顺序的情况下,分析了处理机释放时间对任务完成时间的影响,得到了任务分配方案关于处理机调度顺序和时序约束条件的解析解;然后,以调度顺序和时序约束条件为变量,以任务的最短完成时间为目标,建立了一种新的可分任务调度模型;最后,设计了高效的全局优化遗传算法求解该模型.仿真结果表明所提算法比已有算法完成任务的时间更短.     

具有可变时间的并行排序问题

设有p台处理机要加工n项任务，当每项任务t在时刻i和处理机j上被开始执行时，都有一个不可间断的加工时间l(t，i，j)∈{k1，k2}，我们的目标是要找一个可行方案σ，使得总的完工时间最短．该问题是NP-完备的，本文给出该问题的一个近似算法。     

自动化集装箱码头同轨双堆垛起重机交接缓冲贝位优化

在自动化集装箱码头中,堆场作业效率是评估码头整体运作效率的重要指标.为了提高堆场作业效率,采用同轨双堆垛起重机以借助缓冲贝位同时存储和取回集装箱,其中主堆垛起重机将集装箱堆叠在缓冲贝位,协作起重机将其运送到目标贝位.缓冲贝位的设置能规避双堆垛起重机之间的移动冲突,将冲突转移到缓冲贝位上.制定了一个安全时间间隔以避免双堆垛起重机在缓冲贝位上发生碰撞,以最小化任务完成时间为目标,构建了一个混合整数规划模型决策缓冲区位置和作业最优序列.设计算例和数据集,研究安全时间间隔、起重机移动速度、小车处理时间的敏感性,起重机不借助缓冲贝位和借助缓冲贝位完成任务对任务完工时间的影响以及最优缓冲贝位发生变化对任务完工时间的影响.实验证明,安全时间间隔、起重机移动速度、小车处理时间会影响任务完成时间和缓冲贝位;相较于不借助缓冲贝位完成任务的情况,借助最优缓冲贝位完成任务可以减少11.38%的完工时间;而与最差缓冲贝位相比,最优缓冲贝位可以减少49.40%的任务完工时间.     

并行加工的完工时间

 p台机器完成加工n项任务所需要的时间称为这n项任务的完工时间.首先引入一种参数,即膨胀系数,并设计出一种加工n项任务的算法,然后分别讨论n项任务全都平均分成p份或者全都不分时被p台机器按所设计算法加工的完工时间.     

支持优先级约束任务的容错调度算法

为了解决异构分布式系统中可靠调度问题,提出一种考虑处理机链路通信竞争的,支持优先级约束任务的容错调度(FSPCT)算法。该算法使用通信竞争模型描述处理机之间通信,在备份成本最小化和备份任务最早完成之间寻求平衡点。对主副版本任务的最早开始时间进行分析,并限定了所执行的处理机,在处理机出现故障后任务可以顺利执行。实验结果表明FSPCT算法的综合性能优于现有一些算法。     

异构分布式系统中实时可任意切分任务调度算法

针对异构分布式系统中最大化实时可分任务服务收益和最小化任务完成时间的任务调度问题进行了研究.为在保持较高任务接受率条件下最大化服务收益,提出了三种有效策略:(1)同时考虑服务收益和任务完成截止时间的任务接受/拒绝判断策略;(2)从等待队列里移除任务的策略;(3)考虑收益的最小松弛度优先的排序策略.为最小化任务的完成时间,设计了能够充分利用处理机空闲时间的调度算法以对接受的任务进行调度.仿真实验结果表明,提出的算法能够获得更多的服务收益、任务接受率和较小的任务完成时间.     

异构机群系统中并行任务的分层调度算法

研究在异构机群系统中,使并行任务执行完成时间最短的调度算法．有许多启发式的任务调度算法在同构的分布式计算系统中是很有效的,但在异构机群系统中,由于每个任务在每个处理机上的执行时间不同而失去意义．本文以任务集内任务的拓扑次序为基础,将任务集分层,提出了分层调度算法．它是一个简单而且实用的算法,在某些情况下能达到局部最优,时间复杂度为Ｏ（ｎｍ）,其中ｎ为任务数,ｍ为处理机数．     

分布式实时系统的组资格成员算法

从满足分布实时系统容错要求的角度出发 ,基于 TDM广播网 ,提出了分布式实时系统中的一个处理机组资格成员算法 ;只要系统中故障处理机数目不超过半数 ,该算法就能在其发生周期之后最多不到 2个周期的时间内检测出系统中的处理机故障 ,并维持一个正确的处理机状态视图 ;对算法的正确性给予了证明 .     

多处理机系统的高效实时容错调度算法

在容错调度算法副版本后调度算法的基础上,提出一种高效实时容错调度算法。对于具有容错需求的实时任务而言,由实进容错调度算法所产生的调度可保证在多处理机实时系统中一个处理机失效时,实时任务仍然可在截止时限内完成。在ＥＢＫＣＬ算法中,如何两个实时任务的基版本分配在不同的处理机Ｐｉ和Ｐｊ上,且这两个实时任务的副版本被调度到同一个处理机Ｐ’上,则两个副版本之间允许有时间上的重叠。     

三台平行机上四个约束链的排序问题

考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.     

网格环境下的静态启发式任务调度算法

针对网格环境中,任务调度的目标系统通常为任意连接的网络,程序大多数为密集型的并行分布式应用程序,提出了一个新的基于复制的启发式任务调度算法,该算法减少了任务在执行过程中重复查找最佳处理器的时间花费,可以同时执行多个应用程序,缩短了应用程序总的执行时间,并且平衡了处理器间的负载。实验结果表明:该算法能很好地符合网格的复杂环境,也能够更好地满足不同用户的实际需要。     

Makespan and reliability driven scheduling algorithm for independent tasks in Grids

In the dynamic,complex and unbounded Grid systems,failures of Grid resources caused by malicious attacks and hardware failures ale inevitable and have an adverse effect on the execution of tasks.To mitigate this problem,a makespan and reliability driven(MRD)sufferage scheduling algorithm is designed and implemented.Different from the traditional Grid scheduling algorithms,the algorithm addresses the makespan as well as reliability of tasks.The simulation experimental results show that the MRD sufferage scheduling algorithm can increase reliability of tasks and can trade off reliability against makespan of tasks by adjusting the weighting parameter in its cost function.So it Can be applied to the complex Grid computing environment well.     

面向Deadline约束的网格QoS任务调度

根据调度算法中对QoS的匹配需求,提出了一种基于QoS优先级分组的网格任务调度思想,并且在此基础上引入任务的Deadline约束,综合考虑任务的可接受率以及系统的makespan性能,提出一种面向Dead-line约束的网格任务调度策略QD-Sufferage.实验表明,该算法在makespan、吞吐率等方面的综合性能较以往的算法有较大的提高.     

并行流程式生产线调度问题的概率分析求解算法

并行生产线调度问题兼有并行机器和流程车间调度问题的特点 ,是一类新型的调度问题·针对工件在各工序具有任意加工时间的一般并行生产线调度问题 ,构造了整数规划模型 ,设计了基于概率分析的求解算法·对随机生成的测试问题进行求解的实验结果表明了算法的有效性     

异构计算的一种可移植编程模型及实现

介绍了异构计算的一种编程模型．该模型处理的对象是任意非一致的求解任务映射到任意非一致的系统结构上．文中分别给出了任务图的分簇算法,系统图的分簇算法和映射算法及实例．利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行     

基于任务复制的进化调度算法

并行程序任务调度是NP完全问题。已有的进化调度算法不能很好利用任务复制这一重要手段。为此，利用染色体直接编码和间接编码的优点，并结合任务图的知识，使进化调度算法的搜索能力得到增强，同时染色体的解码过程也得到简化。通过与同类算法的性能比较，表明了本算法在调度问题中的有效性。     

工件尺寸不同的并行机批调度问题

考虑并行批加工机上不同尺寸工件的调度问题；目标是极小化最大完工时间.给出了一个(2+ε)-近似算法，ε＞0可以任意小.     

The origin of bursts and heavy tails in human dynamics

The dynamics of many social, technological and economic phenomena are driven by individual human actions, turning the quantitative understanding of human behaviour into a central question of modern science. Current models of human dynamics, used from risk assessment to communications, assume that human actions are randomly distributed in time and thus well approximated by Poisson processes. In contrast, there is increasing evidence that the timing of many human activities, ranging from communication to entertainment and work patterns, follow non-Poisson statistics, characterized by bursts of rapidly occurring events separated by long periods of inactivity. Here I show that the bursty nature of human behaviour is a consequence of a decision-based queuing process: when individuals execute tasks based on some perceived priority, the timing of the tasks will be heavy tailed, with most tasks being rapidly executed, whereas a few experience very long waiting times. In contrast, random or priority blind execution is well approximated by uniform inter-event statistics. These finding have important implications, ranging from resource management to service allocation, in both communications and retail.