航天器发射多任务并行调度模型及算法

航天器发射高频度常态化和航天产品可靠度的增加,客观上要求航天器发射采用并行调度模式以提高发射资源利用率。针对工序迭代可能引发的航天器发射系统死锁,构建了死锁预测和损失评价机制,建立了最小化任务时间和最小化加权滞后时间综合的目标函数,设计了多任务并行调度模型,开发了多类agent协同工作的优化算法,并使用调度实例验证了模型和算法的可行性和有效性。模型和算法在“天宫一号”和“神舟八号”发射任务中得到初步应用,效果较好。     

基于混合遗传退火算法的并行测试任务调度优化

并行测试任务的优化调度是并行测试技术的核心问题之一。可以充分利用混合遗传退火算法优异的全局最优搜索能力来寻找具有最大并行率的并行任务序列。首先,建立了并行测试任务调度问题的数学模型;给出了并行率的定义,设计了一种满足资源约束与任务时序约束的基因编码方法及相应的遗传退火操作方案。最后,对实例进行仿真实验,结果验证了该算法的有效性及优越性。     

基于蚁群算法的并行测试任务调度

并行测试的任务优化调度是并行测试技术的核心问题.提出了一种用于解决并行测试任务调度问题的改进蚁群算法,通过该算法可以获得测试时间最短的任务调度序列.给出了并行测试任务调度问题的数学模型,设计了启发式函数和状态转移概率的计算公式.采用动态标注方法在搜索过程中加大可行解间的信息素差别,避免算法早熟.给出了应用实例,实际应用表明该算法是有效的,能很好地解决此类多维动态组合优化问题.     

基于HLA的维修保障仿真保守时间推进算法研究

高层体系结构(HLA)中的保守时间推进机制是以并行离散事件仿真(PDES)的保守算法为基础,而考虑不全面的时间推进算法会导致死锁。在维修保障仿真中,维修单元成员常常由于不满足保守算法而引起整个仿真系统无法向前推进。针对具有确定维修任务完成时间的成员不遵循本地因果约束条件的情况下,提出了强制时间同步法;针对具有不定维修任务完成时间的成员违反可预测性的情况下,提出了空事件法和任务阶段法。最终,通过实例验证了算法的正确性和有效性。     

时间Petri网与遗传-蚁群算法相结合的并行测试研究

自动测试系统中并行测试任务调度方案一直是尚未解决的难题.在基于Petri网理论的基础上,建立了并行测试的时间Petrl网模型,并且首次将遗传-蚁群算法引入到时间Petri网的变迁序列的寻找过程中,快速地求得了最优调度方案.仿真结果表明,该算法能够以较大的收敛概率快速地收敛,最终得到最优变迁序列.     

基于自然数编码遗传算法的并行测试技术

针对并行测试任务调度复杂、难以优化的问题,提出了一种基于自然数遗传算法的任务调度优化算法。该算法将并行测试任务调度转化为对串行测试任务序列的搜索,为了提高搜索效率,引进自然数编码遗传算法搜索最优解或近似最优解,将串行测试序列作为染色体,进行选择、交叉、变异等操作。通过仿真证明该算法能够迅速得到并行测试任务调度的最优解或近似最优解。对自然数编码遗传算法的各个算子对模式的作用进行了理论分析,并得到了对应的模式定理,从理论上说明了该方法的合理性。     

单向单交叉并行链优先约束的可靠性系统测试优化

针对具有单向单交叉并行链优先约束的可靠性系统的最优测试序列问题,提出了一种最优测试原则,该测试原则的约束条件更接近复杂的实际情况。通过证明三个相关的定理,分别解决了单向单交叉并行链优先约束的问题转化形式,相交单元在最优测试序列中测试的先后顺序,以及反“Y”形优先约束问题的最优测试序列。利用这一测试原则,可使此类系统获得总期望测试成本最小。通过一系列证明,给出了该原则的求证过程及具体步骤。     

CTCH网的死锁分析

在给出批处理生产系统的过程调度的赋色时间限制混合(CTCH)Petri网模型的基础上，分析了影响CTCH网活性的基本结构，给出了该结构产生死锁的原因。在此基础上，分析了该结构死锁产生死锁的充要条件，并给出了避免死锁的控制策略，为解决整个CTCH网的死锁提供了重要依据。实例表明了结论的正确性。     

带有限缓冲区的知识化制造单元无死锁调度

鉴于制造系统无死锁随机调度问题研究的缺乏,在加工时间、工件到达以及产品需求到达均为随机的生产环境下,研究了带有限缓冲区的知识化制造单元无死锁随机调度问题.针对自动机对定量指标描述能力的不足,首先给出了一种费用自动机概念.在同时考虑工件加工、库存以及缺货费用的情况下,采用无限时域折扣准则下马尔可夫链建立了单元的费用目标函数,通过一致化技术对目标函数进行离散化处理,得到目标函数的随机动态规划模型,分析并证明了单元最优目标值函数的性质.为了克服离散状态空间组合所产生的维数灾问题,提出了一种基于仿真和函数逼近的启发式近似动态规划算法对模型进行求解.在上述研究基础上,构建了一种单元无死锁随机调度策略,以保证单元安全高效地运行.最后,通过实例研究对无死锁调度策略进行了验证.     

井下机车运输调度的资源分配模型及无死锁优化调度

对井下机车运输系统进行无死锁调度和性能优化, 首先, 建立三种不同调度策略下的资源分配Petri网模型, 设计对应调度策略下无死锁标识的最大边界设置算法, 证明了调度策略在最大标识边界设置下的无死锁性. 然后, 以最小化时耗和能耗为优化目标, 利用遗传算法, 采用变迁标号的自然编码方式, 通过检查变迁的引发条件检测染色体的可行性, 修复不可行的染色体使其对应的调度满足资源约束, 从而保证了算法所利用的所有染色体均可对应系统的可行调度, 最后进行实例仿真. 设计的无死锁调度的最大标识边界设置算法和遗传算法为井下机车的运输调度提供了可靠的理论基础.     

基于信号参数集最小距离的并行测试任务调度算法

在并行自动化测试系统中,并发执行的多个测试程序会竞争有限的仪器资源,硬件资源的分配与任务调度是并行测试的一个关键问题。而现有的并行任务调度算法不适于高度异构的并行测试系统。本文在面向信号的描述仪器资源与测试需求的基础上,提出了适合于异构系统的基于信号参数集最小距离的任务调度算法,同时给出了该算法的具体实现。实验结果表明,该算法适于异构的并行测试系统。     

考虑合成机制的多星应急任务调度

以应急任务优先调度为原则,保证观测总收益的基础上最小化对原调度序列的扰动是多星应急任务调度领域急需解决的问题.首先,分析应急任务完成时间和观测收益关系,建立考虑时间依赖性收益的数学规划模型.其次,基于遗传算法,提出考虑合成机制的多星应急任务调度算法.设计任务合成、插入和替换算子完成应急任务插入,考虑任务观测收益、序列扰...     

面向协同设计的任务调度问题研究

针对协同设计任务调度存在的问题,综合考虑了协作项目间、任务间及任务自身的具体因素和约束,在建立设计任务网络图的基础上,提出了一种以"任务优先系数"为指标的可并行执行任务集内任务的执行调度算法.综合考虑协同设计过程中的诸多动态、不确定性及非量化等因素,基于均衡一适度原则建立了任务到团队成员分配的扩展数学模型,并利用匈牙利算法进行求解.研究表明,该方法能有效对复杂产品的协同设计流程进行规划,且简单易用.     

基于偏移影响率的相控阵雷达事件调度方法

在相控阵雷达事件调度中,常以时间偏移率作为指标构造目标函数,但时间偏移率在非线性滤波系统中往往难以实现最优的调度性能。针对这一问题,首先,在分析时间偏移影响的基础上,提出了以偏移影响率做为评价指标,推导了卡尔曼滤波器(Kalman filter,KF)和扩展卡尔曼滤波器(extend Kalman filter,EKF)中偏移影响率的计算公式;然后,基于“偏移影响率”指标构造相控阵雷达事件调度中的目标函数,并利用改进的遗传算法进行求解,加快收敛速度;最后,采用仿真场景测试调度方法优劣。实验结果表明,在线性滤波系统中,偏移影响率与时间偏移率的调度效果相近;在非线性滤波系统中,偏移影响率的调度性能和跟踪精度明显优于时间偏移率。     

基于MapReduce模型带准备时间的平行机调度优化

研究了一类基于MapReduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性.     

基于定时的航空集群机载网络更新方法

针对当前异步网络更新方法更新时间长且无法避免更新死锁的问题, 为降低更新期间的网络性能损失, 提出一种基于定时的航空集群机载网络更新方法。考虑真实的链路时延, 将时间参数与更新依赖图相结合。首先，构建基于时间的更新依赖图。其次，设计贪婪调度算法为每个更新操作分配更新时间步。最后，实现定时网络更新, 避免了异步更新中的更新顺序协调。仿真实验表明, 与现有异步更新方法相比, 所提定时更新方法能够降低50%~60%的更新时间, 减少网络更新期间的更新死锁率和网络拥塞。