多处理器混合实时任务调度

比例公平调度PFair(Proportionate-Fair)算法和边界公平调度BFair(Boundary-fair)是多处理器系统上周期性实时任务的最佳全局调度方法,但在实际的实时系统中,实时任务往往是周期任务和非周期任务混合的任务系统,在研究PFair和BFair调度算法的基础上,提出了基于服务器思想的公平调度方案,实现了对混合实时任务的调度,同时保证了任务公平地使用共享资源,使得公平调度算法适用于多处理器系统中的混合实时任务调度,扩展了其适用范围。     

Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling

In this paper combined with the advantages of genetic algorithm and simulated annealing, brings forward a parallel genetic simulated annealing hybrid algorithm （PGSAHA） and applied to solve task scheduling problem in grid computing. It first generates a new group of individuals through genetic operation such as reproduction, crossover, mutation, etc, and than simulated anneals independently all the generated individuals respectively. When the temperature in the process of cooling no longer falls, the result is the optimal solution on the whole. From the analysis and experiment result, it is concluded that this algorithm is superior to genetic algorithm and simulated annealing.     

A Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling

0 IntroductionGrid computingis a hot topic inthe current internet research,and a developing direction of the parallel and distributedprocess[1 ,2].Since the task scheduling in grid computing faces aNP-hard problem[3];it has drawn attention from many scholarsand become the focusinthe field of the current grid computing re-search.In recent years , two global random and opti mal algorithmhave been widelystudiedandappliedinthefield of the gridcompu-ting research: GA(Genetic Algorithm) and SA( …     

基于混合遗传算法的并行多处理器系统的任务调度

针对并行多处理器系统的任务调度问题,提出一个新的混合遗传算法(HGA)．HGA使用拓扑排序表的交叉来保证下代的合法性和搜索空间的全局性,为了提高HGA的收敛速度,根据拉马克进化理论,在交叉算子中使用贪婪策略来提高个体的适应值,模拟结果显示HGA的调度结果和算法的时间复杂性都是令人满意的．     

多处理机调度问题的一种近似算法

对多处理机调度问题Ｐ∥Ｃｍａｘ，给出一种近似算法，大量实例的计算结果表明，本文的算法是非常有效的。     

多处理机实时分类调度算法研究

讨论了在多处理机实时系统中周期任务可调度性的充要条件和非周期任务的分布函数,并进行了任务调度模型设计。通过处理器利用率实现对实时任务的动态分类,并根据这些分类进行处理器分派。仿真结果表明,这种方法能有效提高实时任务的调度成功率;在处理器达到5个时,调度率可达98%以上,基本属于最优调度,平均负载达到最小且趋于平稳。     

基于遗传算法的机床加工任务调度研究

 基于遗传算法,解决车间生产任务调度的问题.生产调度是自动化制造系统能否取得预期经济效益的关键技术之一,目标是缩短制造周期,提高生产资源利用率,保证生产任务按时完成.其中把加工刀具的分配作为首要约束条件,同时考虑加工工序的前后顺序,利用顺序交叉(OX)方法和顺序变异方法分别完成交叉变异过程.本文所编写的算法使任务调度程序与刀具管理相结合,调度结果更接近实际情况.另外根据刀具使用情况、刀具数量和加工任务以及加工任务的交货期,在出现多个任务竞争一把刀具时,解决刀具的分配问题,并根据工序加工时间和交货时间建立调度优先级.通过实际生产应用证明,优化计算结果具有较好实际应用价值.本文利用Visual Basic软件和SQL数据库作为工具,研究并开发了调度管理系统,主要包括任务编排,生产调度,刀具管理等功能.     

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

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

自适应遗传算法在飞机调度问题中的应用

基于自适应遗传算法，实现了单跑道降落飞机调度问题的求解，算法以所有飞机的排列次序做为个体编码，解码时用移动方法确定飞机的降落时间，适应度函数的构造综合考虑了飞机的提前和延迟带来的损失，选择算子采用期望值方法，交叉算子用顺序交叉，变异算子用倒位变异，为提高算法的执行效率并避免早熟收敛，对交叉和变异概率均采用自适应策略，仿真结果表明了自适应遗传算法用于飞机调度问题的有效性。     

一种求3机Flow—shop调度问题的遗传算法

提出一种遗传分枝定界算法求解3机Flow-shop调度问题，该算法似于常用的遗传局部算法和遗传动态规划算法，用随杨方法生成测试例子，通过与著名的Taillard的禁忌搜索算法和Reeves的遗传算法进行比较，实验结果证实了遗传分枝定界算法的有效性。     

作业车间调度的非合作博弈模型与混合自适应遗传算法

采用博弈理论,建立了一种基于非合作博弈的作业车间任务调度模型.在该任务调度模型中,将源于不同客户的制造任务映射为非合作博弈模型中的局中人,并将与制造任务包含的工序集所对应的可选加工设备映射为可行方案集,使各制造任务的加工完成时间和成本组合形成的多目标综合指标映射为收益函数,从而将对任务调度模型的求解转换为寻求非合作博弈模型的Nash均衡点.通过设计的爬山搜索混合自适应遗传算法、自适应交叉和变异算子,实现了对该任务调度非合作博弈模型的Nash均衡点的有效求解,同时算例仿真结果也验证了所提出的调度方法的正确性.     

基于免疫遗传算法的网格任务调度

研究了网格环境下任务调度问题,提出了一个任务调度机制:基于任务图将每一个可能的任务调度方案表示成一个任务-资源分配图,将网格任务调度问题转化为任务-资源分配图优化选取问题.提出了一种基于免疫遗传算法的、实现任务-资源分配图优化选取的任务调度算法.该算法将任务-资源分配图的最长路径作为抗原,每一个任务-资源分配图对应一个抗体.实验结果表明这个算法在全局优化能力及收敛速度上均有显著提高.     

基于遗传模拟退火算法的任务分配与调度

网格将多种资源组织在一个统一的框架下,为各种复杂的计算任务提供资源。因此计算任务在各种资源之间的调度成为了一个关键的问题。结合遗传算法GA和模拟退火算法SA的优点,提出了一种全局遗传模拟退火算法GGSAA,并将算法应用于网格计算任务调度问题的求解之中。最后给出了GGSAA算法的仿真结果。     

一种改进的车辆调度问题的遗传算法

车辆调度问题是一个NP-难问题,不存在多项式时间算法.针对这个问题本文使用集合分划的方法把较为复杂的车辆调度问题分解为相对简单的多旅行商问题,提出求解该模型的两阶段法并且运用新的编码和解码方式;另一方面,结合遗传算法对一些测试数据进行仿真试验,并得出了理想的结果.     

RM算法中减少抢占开销的任务微调算法

在基于嵌入式实时操作系统的实时应用中,由于任务抢占导致的切换开销对于整个系统是不可忽略的.提出了一种减少抢占发生的RM任务微调算法,通过对固定优先级调度抢占行为可推迟时间的量化分析,推导出受低优先级任务阻塞而造成的受阻任务集,以及在任意抢占时刻,推迟高优先级实时任务执行避免抢占发生的判定条件.仿真实验表明该算法在保证可调度任务集中所有任务满足时限约束的前提下,延迟高优先级任务的执行,减少抢占发生次数,通过减少抢占开销提高RM算法在实际应用中的可调度利用率.     

一种具有免疫机制的车间调度遗传算法

利用人工免疫机制中的克隆选择原理的相关优点，并在遗传算法中融入具有动态、自组织等特征的免疫机制，建立了人工免疫遗传算法。相比单独使用遗传算法，该方法对车间生产调度的优化效果起到进一步改善的作用，最后通过实例加以验证。     

基于时限单调算法的混合任务实时调度算法的研究与设计

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向。针对现代嵌入式实时系统的任务特性,和经典实时调度算法只调度周期任务的特点,提出一种新的静态优先级调度算法——混合任务时限单调算法(Periodic and Aperiodic Deadline Monotonic,PADM)。该方法结合时限单调(DM)算法和先来先服务(FCFS)算法,将非周期任务量化为周期任务,且非周期任务在其裕度为零时优先级最高。通过理论分析和具体实验比较,在任务集轻载情况下,PADM算法尽可能地保证周期任务的完成率和非周期任务的时限,同时所带来的额外开销小,计算复杂度低,实现方便,是一种有效的混合任务调度算法。     

用 遗 传 算 法 求 解 调 度 问 题

给出用遗传算法解决典型调度问题的方法, 并用遗 传算法实现了车间作业调度. 实验结果表明, 遗传算法在寻求调度问题的全局最优解方面具 有较高的效率.     

求解流水车间调度问题的一种混合式遗传算法

讨论了如何将邻域搜索与遗传算法相结合求解流水车间调度问题,提出了一种邻域结构,使之更适合求解流水车间问题,设计了一种基于扩展采样空间的混合式遗传算法的框架,并通过计算机模拟验证其有效性。     

基于粒子群优化的多处理器任务调度算法

对于NP(Non-Polynomial)完全问题,现有的算法主要是启发式算法,性能还有待提高。基于粒子群优化智能算法,提出一种新的任务调度算法,目标是在满足任务之间优先关系的条件下,使所有任务整体完成时间最小。算法将粒子位置和任务高度作为任务的优先级,通过表调度技术生成有效的调度方案,并将调度方案对应的调度长度作为粒子的适应值。首先随机产生一群粒子,然后通过使用全局模型的粒子状态更新策略不断迭代,获得可以接受的任务调度方案。仿真实验结果表明,与遗传算法相比,调度长度提高14.7%,运行时间缩短近一半,特别适合于求解规模较大的多处理器任务调度问题。