以多Agent系统为架构的实时调度模型

构建了一个适用于柔性作业车间(FJSP)调度的实时模型,将车间加工设备和作业封装为Agent,通过Agent之间的招投标实现实时调度。采用了虚拟货币机制来构造实时调度模型,该机制可使交货期紧张的作业拥有更高的优先级选择加工机器,使调度方案在满足实时性的同时得到优化;模型还引入急件插入机制,在处理紧急任务时可在尽量减少对其他任务干扰的前提下顺利实现对紧急任务的调度。与其他同类调度模型相比,提出的模型在实时性、调度质量上和用户满意度上都拥有其独特优势。     

基于需求优先的多目标柔性车间调度研究

为满足按时提交客户货物的要求,需要优化企业的生产调度,现实的生产调度问题是传统车间调度问题的扩充,具有多目标、柔性等特性。针对柔性作业车间调度的需要,提出了在精益制造下的基于需求优先的多目标柔性车间调度算法。该算法以工件提前／拖期惩罚代价最小,调度最小生产周期为目标,基于规则的改进启发式调度,在调度过程中通过需求日期计算工件的优先级为每道工序分配合适的机器进行加工,可得到满意的较优解。与其他方法进行对比试验的结果表明,该算法在求解柔性作业车间调度问题是有效的。     

基于Petri网的JSP动态优化调度

提出一种在柔性制造系统动态优化调度中处理紧急定单的方法。以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,对系统的设备维护、各种优先级等特性进行描述,利用遗传算法和模拟退火算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等双资源制约条件下的动态优化调度。当有紧急定单需要加工时,该方法把剩余任务和紧急任务作为两个独立的任务分别处理,然后进行集成,在紧急任务为最优调度的基础上选取剩余任务的最优调度,找到兼顾整体和局部的最优解。仿真结果说明了算法的有效性和鲁棒性。     

考虑非确定加工时间的柔性作业车间调度问题研究

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。     

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

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

双资源批量生产柔性作业车间多目标调度方法

针对双资源批量生产柔性作业车间调度问题,提出了一种多目标精细化调度方法。针对双资源批量生产柔性作业车间多目标调度问题特点,建立了一类以制造成本最低和完工时间最短为优化目标的双资源等量分批柔性作业车间调度多目标优化模型;提出了5种双资源批量生产柔性作业车间精细化调度技术;针对模型提出并设计了一种改进的NSGA II算法。通过案例分析验证了该方法的有效性。     

生物地理学算法求解柔性车间作业调度问题

针对加工设备和操作工人双资源约束的柔性作业车间调度问题,建立以生产时间和生产成本为目标函数的柔性作业车间调度模型,提出基于模糊Pareto支配的生物地理学算法,采用模糊Pareto支配的方法计算解之间的支配关系并对Pareto解集排序,进行全局最优值的更新,并采用余弦迁移模型来改善生物地理学算法的收敛速度。将该方法应用于某模具车间的柔性作业车间调度中,仿真结果验证了该方法的可行性和有效性。     

基于区间值模糊集的柔性工作车间调度模型

论文首先描述了现实柔性工作车间调度中的时间参数不确定性问题,并阐述了模糊理论中α截集、区间值模糊集等相关概念;然后给出了以遗传算法为框架的基于区间值梯形模糊数的柔性工作车间调度模型,并且通过实例验证了模型的可行性和有效性。     

一种多用户MapReduce集群的作业调度算法的设计与实现

随着更多的企业开始使用数据密集型集群计算系统如Hadoop和Dryad实现了更多的应用,多用户间共享MapRe-duce集群这种既减少了建立独立集群的代价,同时又使得多用户间可以共享更多的大数据集资源的需求日益增多。在公平调度算法的基础上,结合槽分配延迟和优先级的技术,本文提出了一种改进算法,可以实现更好的数据本地性,改善整个系统的计算性能如吞吐率、响应时间等;同时为了满足差别化的商业服务,通过对用户设置相应的优先级保证紧急任务的完成。     

优先级受限系统中可调度判定方法

在通信、雷达、导航以及各种消费类电子产品等民用和军事领域,嵌入式实时调度已逐渐成为电子电气系统的控制核心。针对同优先级任务使用FIFO调度的静态优先级系统,使用反例指出给定同优先级任务初始执行顺序的前提下,Katcher可调度判定条件的必要性不成立,提出并解析证明了FP可调度的充要条件。随机实验表明,对于高利用率下任务间执行时间差异较大的情况,约有15%的可调度任务集会被Katcher条件错判为不可调度。进一步的仿真和实例分析表明,Liu、Lehoczky、Bini等提出的条件不能判定相同优先级的情况,Katcher条件的必要性不成立,论文提到的条件能够正确判定任务集的可调度性。提出方法为实时系统调度的顶层设计提供了快速离线工具。     

基于有向无环图网格独立任务调度算法*

提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时, MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的MinMin 算法。     

云计算中基于优先级和费用约束的任务调度算法

针对云计算中的服务质量保证问题,提出一种基于优先级和费用约束的任务调度算法。该算法通过计算任务优先级和资源服务能力,分别对任务和资源进行排序和分组,并根据优先级高低和服务能力强弱建立任务组和资源组间的调度约束关联;再通过计算任务在关联资源组内不同资源上的完成时间和费用,将任务按优先级高低依次调度到具有任务完成时间和费用折中值最小的资源上。与Min-Min和QoS-Guided-Min算法的对比实验结果表明,该算法具有良好的系统性能和负载均衡性,并降低了服务总费用。     

面向物联网终端的任务相关性调度策略

对于具有相关性的任务,调度顺序不合理将影响任务的执行时间和实时性。结合物联网终端任务间依赖关系复杂的特点提出了一种利用任务相关性的调度策略。该策略设计了以作业轮询组为主体的任务模型,根据任务时限建立了优先级因子矩阵作为任务调度的凭据,对于周期任务,在每个任务执行完毕后生成,以任务相关性为参数的增量矩阵用以动态修改任务优先级,使前驱任务能优先执行;对于非周期任务采用了构建临时作业轮询组的方式进行抢占调度。测试结果表明,该策略能够有效减少具有相关性的周期任务集执行时间和调度失败次数,缩短非周期任务响应时间。     

遥感影像并行处理中基于优先级的任务分配策略

对集群环境下大规模遥感影像并行计算中任务分配效率低、负载不均衡的问题进行分析讨论,在此基础上建立多机任务分配模型,提出一种基于计算节点优先级的任务分配算法。该算法综合考虑计算节点的负载和性能,在任务分配时实时地收集各个节点的信息,计算出各个计算节点的优先级,按照优先级的高低分配任务,保证在满足集群间负载均衡的前提下能合理地将任务分配到计算节点。实验结果表明,该算法能快速实时地进行任务分配,任务的分布更加合理和均匀,并且当任务个数增多时,算法的执行效率要比轮转调度算法高出约2倍。     

On-line scheduling of scalable real-time tasks on multiprocessor systems

The computation time of scalable tasks depends on the number of processors allocated to them in multiprocessor systems. As more processors are allocated to a scalable task, the overall computation time of the task decreases but the total amount of processors’ time devoted to the execution of the task, called workload, increases due to parallel execution overhead. In this paper, we propose a task scheduling algorithm that utilizes the property of scalable tasks for on-line and real-time scheduling. In the proposed algorithm, the total workload of all scheduled tasks is reduced by managing processors allocated to the tasks as few as possible without missing their deadlines. As a result, the processors in the system have less load to execute the scheduled tasks and can execute more newly arriving tasks before their deadlines. Simulation results show that the proposed algorithm performs significantly better than the conventional algorithm based on a fixed number of processors to execute each task.     

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

符合OSEK的uC/OS任务调度策略

根据OSEK OS规范,对实时操作系统uC/OS II的任务调度策略进行改进。提出一种符合OSEK OS规范的任务管理机制,修改uC/OS II的优先级判定方法,以使数值0代表优先级最低,数值越大优先级越高。测试结果表明,修改uC/OS II后的操作系统支持同优先级多任务,同优先级队列中的任务按FIFO顺序调度。     

基于多参数的μC/OS-Ⅱ任务优先级和调度方法

在μC/OS-Ⅱ进行实时任务调度时，可以使用单一的调度算法分配任务优先级。优先级判定标准的片面性、“错过率”较高的截止期，影响了μC/OS-Ⅱ的实时调度性能。该文提出了多参数任务优先级分配策略和μC/OS-Ⅱ任务的调度方法，实验证明，该方法截止期的平均错过率为60.1%，有效地改善了μC/OS-Ⅱ的实时调度性能。     

多特征参数的任务模糊调度算法

针对任务具有特征参数多和特征参数不确定性的特点,提出了一种基于模糊理论的任务调度算法。利用模糊集合来描述任务的不确定性特征;使用多层模糊综合评判和最大隶属度原理来综合考虑任务的多个特征参数并确定任务的优先级;采用动态构建多层评判模型的调度策略来减小任务优先级评判的失效率。仿真表明,该算法提高了任务调度的成功率,降低了任务截止期的错失率和任务优先级评判的失效率。该方法可应用于优先等级有限的实时系统任务动态调度中。