一种固定优先级实时调度算法的可行性测定

实时调度算法是实时系统的关键技术,验证实时调度算法的可行性是保证实时系统性能的必要手段。不同实时调度算法可行性测定方法不同。在简单实时模型上,针对固定优先级实时调度算法给出通过任务最坏响应时间来测定调度算法可行性的方法,分析了影响任务最坏响应时间的各种因素,修正了响应时间方程,将该方法运用在复杂实时模型中。     

单处理器系统的实时调度算法研究

实时调度算法是实时系统中的关键技术.文章在研究单处理器系统中常用实时调度算法:固定优先级调度算法和动态优先级调度算法基础上,详细分析了常用固定优先级调度算法RM、DM算法和动态优先级调度算法EDF、LLF和MLLF算法的运算过程和使用条件,提出了各个算法在实际应用中存在的问题,为实际应用中选择何种实时调度算法确定了依据.     

一种硬实时调度算法的可行性判定及实现

实时调度算法是实时系统的关键。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。本文针对硬实时调度算法中的最早时限优先(EDF)调度算法,分别介绍在简单模型上和复杂模型上如何判定实时任务的可行性。     

一种混合优先级的防危调度算法

为增强实时系统任务过载时的防危性,提出一种混合优先级的防危调度算法,其优先级由相对截止期优先级和相对松弛度优先级组成,通过相对松弛度预测任务的可完成性,并采用完全抢占方式防止处理器资源的竞争抖动。仿真结果表明,该算法可充分利用处理器资源,能在发生瞬时过载时有效降低任务的截止期错失率。     

CAN总线固定优先级调度算法的应用

分析了CAN总线的最差消息传输模型，提出了一种固定优先级调度算法；针对系统控制实时性的要求及特点，对6自由度平台系统的消息进行调度。实际使用证明，该方法改善了6自由度平台的整体控制性能，提高了网络利用率，消息的截止期得到满足。     

周期多帧任务的固定优先级调度算法的调度分析

实时操作系统的核心问题－－实时任务的调度是实时系统研究的重点之一。主要讨论了周期多帧任务的固定优先级调度算法的调度情况,证明了对于周期多帧任务DM算法不是最优的,同时也证明了对于累积单调周期多帧任务的DM算法是最优的。     

实时协同的调度算法研究

研究了目前流行的实时调度技术,归纳总结了不同调度技术下的典型调度算法,介绍了实时调度算法的调度规则、调度特点、适用场合以及需要解决的问题,分析了典型商业实时操作系统中的调度技术,提出了增强操作系统实时性能需要解决的技术问题,为将优秀的实时调度算法应用在实时操作系统中奠定了理论基础。     

一种新型实时调度算法研究

在许多片上特定应用系统中，任务多且切换频繁，任务切换开销大，有时甚至严重影响系统的可调度性．研究了动态可抢占门限调度算法，它通过初始门限值、动态门限值的计算和优化线程分配，实现了在处理器高利用率下，有效降低任务切换开销的目的，并相应地减少了对内存的需求．动态可抢占门限调度算法是将静态抢占门限算法与动态调度算法有机地结合在一起。完成了由静态到动态无缝转换．     

一种基于优先级表的实时调度方法

针对单处理器实时系统动态调度问题进行了研究,分析任务的到达时间、执行时间、截止时间和空闲时间等任务属性的敏感度和影响度,提出了一种基于优先级表的调度算法PTBM,使相对截止期越小、空闲时间越大的任务优先级越高。对关于实时任务属性敏感度和影响度的结论验证和与传统的EDF、LLF和PTD算法的对比进行仿真实验,仿真结果表明基于优先级表设计的实时调度算法PTBM具有较高的调度成功率。该方法可应用于实时系统的实时任务的动态调度中。     

一种有限优先级的静态优先级分配算法

静态优先级调度在实时系统中得到了广泛应用.然而,静态优先级调度受到系统支持的优先级个数的限制.当任务的个数大于优先级个数时,需要将多个任务映射到同一个优先级.针对优先级个数有限的情况,给出了在截止期限大于周期时任务可调度的充分必要条件,并提出了基于有限优先级的静态优先级分配算法(AGP).AGP算法对于基本任务集合是最优的静态优先级分配算法.其最优性表现在,所需的优先级个数最小,并且若采用AGP算法不可调度某个任务集,则采用其他静态优先级分配算法也不可调度该任务集.模拟结果表明,AGP算法的可调度性要远远大于常量法.AGP算法对于解决在嵌入式实时系统中任务的优先级分配问题具有重要意义.     

一个改进的调配算法

图中路径的基本优化策略有两种最短路径和最大权值最小路径。前者的求解有著名的Dijkstra算法;后者的求解通过先构造图的最小生成树MST,再截取其上两端点间的唯一路径就是最大权值最小路径。但是,尚未有文献提出算法同时争取两方面的优化。本文采用Dijkstra算法构造路径时不断递增的基本思想,提出MSPT算法。MSPT算法是在求得最短
路径的同时最大限度地争取最大权值最小。其算法时间复杂度和空间复杂度均与Dijkstra算法相同,但比Dijkstra算法横向上增加了一层优化,更切合实际问题的需要。同时,该文给出了MSPT算法的实际应用模型。     

多进程动态调度方法

文章对相关进程的典型关系进行了描述,并讨论了进程中有序和同步问题的实现方法。     

An Optimization-Based Approach for Design Project Scheduling

Concurrent engineering has been widely used in managing design projects to speed up the design process by concurrently performing multiple tasks. Since the progress of a design task often depends on the knowledge about other tasks and requires effective communication, tasks and communication activities need to be properly coordinated to avoid delays caused by waiting for information or the need for rework. This paper presents a novel formulation for design project scheduling with explicit modeling of task dependencies and the associated communication activities. General dependencies are modeled as combinations of three basic types representing sequential, concurrent, and independent processes. Communication activities are also modeled as tasks, and their interactions with design tasks are described by sets of intertask constraints. The objective is to achieve timely project completion with limited resources. To improve algorithm convergence and schedule quality, penalties on the violation of constraints coupling design tasks are added to the objective function. A solution methodology that combines Lagrangian relaxation, dynamic programming, and heuristic is developed to schedule design and communication tasks, and a surrogate optimization framework is used to overcome the “inseperability” caused by nonadditive penalties. A heuristic procedure is then developed to obtain scheduling policies from optimization results and to dynamically construct schedules. Numerical results show that the approach is effective to handle various task dependencies and the associated communication activities to provide high-quality schedules.      

An Agent-Based Approach for Scheduling Multiple Machines

We present a new agent-based solution approach for the problem of scheduling multiple non-identical machines in the face of sequence dependent setups, job machine restrictions, batch size preferences, fixed costs of assigning jobs to machines and downstream considerations. We consider multiple objectives such as minimizing (weighted) earliness and tardiness, and minimizing job-machine assignment costs. We use an agent-based architecture called Asynchronous Team (A-Team), in which each agent encapsulates a different problem solving strategy and agents cooperate by exchanging results. Computational experiments on large instances of real-world scheduling problems show that the results obtained by this approach are significantly better than any single algorithm or the scheduler alone. This approach has been successfully implemented in an industrial scheduling system.     

一种基于调度簇树的周期性分布实时任务调度算法

本文针对现有的基于任务复制的静态调度算法在调度周期性分布实时任务时存在的缺点,提出了一种称之为调度簇树（SCT）的新的结构并研究了其特性,在此基础上给出了一种基于SCT树的周期性分布实时任务调度算法（SAS）。通过与OSA算法进行比较的实验结果表明,SAS算法可实现调度长度向上最接近分布实时任务周期,最大程度减少所需顸留处理器数目,大大提高分布实时系统的处理器利用率,同时并不增加调度算法的复杂度。     

基于混合蛙跳和遗传规划的跨单元调度方法

针对运输能力受限条件下的跨单元问题,提出了一种基于混合蛙跳与遗传规划的超启发式算法.将改进的混合蛙跳算法作为超启发式算法的高层框架,为跨单元调度问题搜索启发式规则,同时利用遗传规划产生可以兼顾多因素的优质规则,用于扩充超启发式算法的规则集.实验表明,提出的算法可以有效地搜索出优异的规则组合,并且通过遗传规划产生的规则可以在很大程度上改善候选规则集,提升算法性能.     

一种解决车辆调度问题的算法研究

针对运输费用的逐年提高,企业配送环节的成本大幅度增加的问题,为降低物流成本,提高企业利润,研究了一种解决车辆调度问题的算法。在考虑实际需求的基础上,建立了单配送中心的配载车辆调度模型,满足基本的约束条件。同时,论述了节约算法的基本原理并采用改进的节约算法对配载车辆调度问题进行求解,即在基本的节约算法中加入时间窗约束条件。通过各种数据的实验验证,此算法都能得到较满意的解,既能节约时间,又能够节约运输里程和费用。     

人工蜂群算法在并行测试任务调度中的应用

并行测试是下一代自动测试系统的关键技术之一,而并行测试任务调度是并行测试的核心内容;首先建立并行测试调度的数学模型,根据人工蜂群算法解决动态调度优化问题的优势,提出基于人工基于蜂群算法的并行测试任务调度方法;并给出应用实例,仿真实验表明:该算法收敛快、准确率高,能有效解决并行测试调度优化问题。     

基于改进的RA算法的混合Flowshop调度问题的求解

针对混合Flowshop系统的最小化Makespan调度问题,提出基于改进的RA斜度指标的启发式算法来对工件进行排序,采用FAM算法来分配设备并给出其最优值的下界检验该算法。仿真结果表明该方法优于目前最好的启发式算法能较好地解决混合Flowshop的调度问题。