面向软数控系统的混合任务调度算法

为减小因软数控混合任务不确定性而引起的加工误差,提出了面向软数控的模糊反馈调度算法和两级结构的调度策略.在分析软数控任务划分和任务模型的基础上,研究了软数控模糊反馈调度算法的结构,并推导出调度算法表.通过对比仿真试验表明:不采用模糊反馈调度,加工误差达11.9%;采用模糊反馈调度,加工误差最大值仅为1.04%.给出了两级调度策略的架构,并对调度算法、任务可调度性及时标间隔进行了研究.所提出的两级调度策略已应用到基于Windows CE.NET的软数控系统中,实测任务运行状态显示,实时任务具有很好的确定性.仿真试验和具体实施的结果表明,提出的两种算法能满足软数控系统的个性化实时应用.     

面向数控系统的容错实时调度算法研究

针对数控系统的混合任务调度以及高可靠性的特点,提出一种基于软件容错模型的实时调度算法(FT-MT)。该算法在系统运行前预先分配替代版本的执行区间,使得替代版本在其截止期内尽可能地推迟执行,为主版本的完成提供了最大的可执行时间。同时,为了避免主版本的早期失败对后续任务的影响,增加了主版本的可执行规则,提高了主版本可执行性的预测精度。仿真实验表明,与同类算法相比,FT-MT算法在提高数控系统容错能力方面更为有效。     

面向数控系统的数据流反馈调度框架

提出一个数据流反馈调度框架(Feedback scheduling framework for data flow,FSF-DF),该调度框架可以预防因数据流中断而导致全软件数控系统加工时间延长与加工质量降低的现象.FSF-DF在数据流上的缓存中设置溢出警戒线,并实时地监测缓存中的数据量是否超出溢出警戒线,以此判断数据流是否有发生数据中断的危险.在数据流将要中断时,调整相关任务的执行频率和优先级,以维持数控系统的稳定性.利用马尔可夫链等统计方法降低执行频率的调整次数,使得FSF-DF具有较低的系统开销.通过建立包括监视器、控制器与基本调度器在内的动态反馈调度框架,使得任务执行频率与优先级的调整规则能够有效地集成在实时操作系统中.在实时操作系统RTAI中实现了FSF-DF,并验证它的有效性.试验结果表明,数据流反馈调度框架可以有效地预防数控系统中的数据流中断现象,能够提高数控系统的整体性能与加工速度.     

一种面向成本优化的生产计划调度算法

建立了一种车间层的生产计划的成本优化模型,该模型是一个在时间约束、可重复使用和不可重复使用资源约束下的多模式项目调度问题;给出了解的定义,设计了一种时间可行的成本优化调度算法,通过改进成本优化调度算法达到时间一成本双优的目的;给出了模拟试验结果。     

基于混合遗传算法的Job-Shop调度问题的研究

Job-Shop调度问题是最困难的组合优化问题之一,由于其固有的计算复杂性,一般无法利用经典解析算法求出最优解。结合实际生产情况,建立了Job-Shop调度问题的模型,并基于遗传算法与局部搜索启发式算法相结合的混合遗传算法的思想给出了求解此模型的算法过程。     

软数控系统混合任务两级调度策略

针对软数控混合任务调度,提出一种两级结构调度策略：对实时周期性任务采用时间触发,实时突发性任务则采用事件触发。建立混合任务模型并定义相关概念,给出调度策略的架构,并对调度算法、任务可调度性及时标间隔进行深入研究。将提出的两级调度策略应用到基于Windows CE.NET的软数控系统中,分析软数控系统结构和任务划分。最后,对调度策略进行试验验证,结果表明该方法能保证混合任务的确定性,从而提高软数控系统的性能。     

多核处理器数控系统的全局调度算法

提出了面向多核处理器系统的限制抢占调度算法,通过在任务的末尾设置高优先级(抢占阈值)的限制抢占区,减少任务运行过程中被抢占的次数,提高调度效率。建立了限制抢占调度的可调度性判定条件和限制抢占区设计方法。仿真结果表明,限制抢占调度的调度性能较抢占调度和延迟抢占调度的调度性能有明显提高。     

工程机械机群多智能主体容错调度研究

以工程机械机群多智能主体系统为例,介绍了在此系统上实现的一种容错调度技术。将大型施工机群的复合主体抽象简化成三个层次的主体,具体设定了各个单机主体的功能,并结合单机智能故障诊断系统提出了以主控主体为核心的混合实时任务容错调度。通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法,有效地减少了单机数,仿真结果证明了算法的有效性。     

求解置换调度问题的改进混合遗传算法

构造了求解极小化总完工时间的置换调度问题的改进混合遗传算法：先采用构造型启发式算法和随机方法共同产生初始种群，然后在选择、交叉和变异等遗传操作之前借助禁忌搜索算法寻找每个个体的局部最优解组成当前种群，再应用种群整体替换策略保存种群中的优秀个体构成新一代种群。改进混合遗传算法有机地结合了禁忌搜索算法的局部搜索性能和遗传算法的全局搜索性能。仿真实验表明，改进混合遗传算法具有比构造型启发式算法和禁忌搜索算法更好的鲁棒性和寻优性能。     

基于过滤定向搜索的Job-Shop调度算法及评价

对以Makespan最小为目标的Job Shop调度问题进行了研究。首先对Job Shop调度问题进行了描述,在此基础上建立了一种求解Job Shop调度问题的启发式优化算法———基于过滤定向搜索的算法,同时结合实例对算法的优化过程作了具体描述。最后通过不同规模的Benchmark实例对该算法进行了仿真评价,结果表明基于过滤定向搜索的算法搜索效率高,解的性能好,是一种有效的优化算法。     

优先约束的混合实时任务动态调度算法

为了对较大规模问题在短时间内给出满意的解并调度随机到达的非周期任务,提出了一种动态混合调度算法。在第一个截止期限错失时刻,通过分析系统的运行情况,推导出具有优先约束的实时任务可调度的充分条件。在系统运行前,判定周期任务的可调度性,预分配足够的处理机。当非周期任务到达系统时,在保证周期任务可调度的前提下重新给周期任务和非周期任务分配处理机。该算法具有多项式时间复杂性,适合解决较大规模的多处理机调度问题。实验结果表明,该算法有效提高了处理机的利用率和非周期任务的接收率。     

基于约束满足的车间调度算法综述

为了说明如何利用启发式信息构造车间调度的约束满足求解算法,首先概述了常规约束满足求解技术,进而介绍了车间调度问题的约束传播算法、树搜索算法和启发式修复算法的构造原理及适用性.在此基础上,针对目标优化问题,给出两种求解框架.最后,指出近期的研究趋势和进一步的研究工作.     

求解同顺序加工调度问题的一种启发式方法

为了更加有效地求解同顺序加工调度问题,分析了现有启发式求解方法,发现影响解的质量的主要因素是调整近似解的方法和初始解,其中调整近似解的方法对解的质量影响较大。对此,提出了一种新的启发式方法。新方法中的调整方法考虑了调整对最短总加工时间的影响,调整任意给定的近似解不会降低解的质量,经过迭代运算,可以逐步改善近似解;新方法采用了多起点策略,利用调整方法调整不同初始解,选取最好的近似解作为问题的解,从而减小了初始解对问题解的质量的影响。实验结果表明,这种方法是有效的。     

基于混合量子进化算法的自动化制造单元调度

为解决传统智能优化算法在求解自动化制造单元调度问题时易出现早熟、陷入局部最优等问题,提出了混合量子进化算法.该算法采用序列染色体和量子染色体相结合的混合编解码策略,利用构造启发式算法生成初始种群,避免了不可行解的大量产生;为提高算法的优化性能,进化过程中采用序列染色体和量子染色体同步交叉变异策略,并引入了基于图论的不可行解修复策略.通过与遗传算法、基本量子进化算法的对比实验,验证了算法的有效性.     

群控电梯目的地调度系统

为解决现有群控电梯外召板呼梯系统存在的响应效率低、调度不合理等弊端,实现群控系统的优化调度,将一种个性化的基于目的地调度的技术运用于电梯群控系统。开展了系统结构和工作原理的分析,建立了各模块问的关系和各模块间的通讯过程,提出了优化调度算法和调度策略。基于群控系统基本功能和目的地优化调度算法的实现,在型号为DMT80480T070—18WT的迪文公司生产的触摸屏上对事先利用触摸屏DGUS配置工具设计的按键界面进行了呼梯测试,利用OSBuilder软件编写的汇编程序进行了界面显示,在设计的群控模块上对用KeiluVision4编写的控制系统整体运行的程序进行了试验。研究结果表明,群控电梯目的地调度系统能方便乘客操作,且操作界面新颖;电梯响应实时性强,稳定性好,对现有群控技术具有重要的意义。     

自动化制造单元最小完工时间调度问题的混合启发式算法

自动化制造单元最小完工时间调度问题属于NP-hard难题,目前尚缺乏有效的调度方法。为此,提出基于遗传和禁忌搜索的混合启发式算法,用以搜索一组最满意的机器人搬运作业排序。以遗传算法为基本结构,在初始种群产生和交叉、变异操作中引入禁忌搜索技术,以提高优化质量。基于搬运作业规则的初始种群构造算法和两阶段交叉、变异算子克服了传统算子对可行搬运作业排序的破坏,而邻域移动算子则保证了禁忌搜索的多样性和集中性。最后,随机实验结果验证了算法的有效性。     

禁忌-并行遗传算法在作业车间调度中的应用

根据并行遗传算法与禁忌搜索算法的优点,提出了一种禁忌一并行遗传算法。该算法能够避免早熟,不仅保证了算法的全局收敛,而且提高了算法收敛速度和解的质量,特别是在求解大规模问题上具有优势。仿真结果证明了该算法的有效性。     

面向价格动态变化的云工作流调度算法

为解决资源价格变动环境中云工作流任务调度开销优化的问题,提出一种基于动态规划的云工作流资源调度算法.该算法将云工作流中的任务分为多个串行任务组,然后利用动态规划算法对每组任务进行调度,计算在该任务组规定完成时间内开销最低的调度方案.通过实验,与状态图搜索算法进行了比较,在被调度的资源的价格为可变函数时,计算了四种工作流模型的调度结果.结果表明,所提动态规划算法比考虑资源平均价格的状态图搜索算法有更好的表现.     

基于DBR—GA的混合流水车间调度方法

针对带有并行机与批处理机的混合流水车间调度问题,提出一种基于“鼓-缓冲器-绳子”一遗传算法的调度方法。首先建立了识别瓶颈工作站的步骤,开发了相应的启发式算法,进行了问题初始解的求解,在此基础上应用改进遗传算法对作业在瓶颈工作站上的加工顺序进行优化,并利用缓冲机制决定了作业的投放策略,同时对非瓶颈设备运用优先级规则进行了作业的排程。最后通过算例实验和性能分析,验证了所提调度方法的有效性与实用性。