基于遗传-模拟退火算法的空间目标地基监视调度方法

空间目标监视是航天任务得以顺利开展的重要基础。针对空间目标地基监视中的大规模复杂调度问题,建立了包含多种约束条件和优化目标的调度问题数学模型。探讨了利用遗传算法对全局解的一部分进行局部优化以提高资源利用率的算法混合策略,构建了遗传-模拟退火算法,其中对模糊需求使用了启发式方法以构造可行解的局部,并采用窗口修剪法进行冲突处理。仿真结果表明,遗传-模拟退火算法与窗口修剪法结合能够在可接受的时间内求得满意的解,验证了模型和算法的有效性。     

引入微元法思想的混合测控资源联合调度方法

针对混合测控资源联合调度中存在的资源属性繁多、偏好差异大以及可能出现的调度弧段冲突等问题,借鉴单体制测控网调度研究中的任务需求描述方法,对混合测控任务需求的特点进行分析,给出其任务需求的规范化描述。以测控调度收益值最大为目标,建立混合资源联合调度模型;引入微元法思想,提出了可用弧段扩展复用方法,以此为基础提出了基于改进遗传算法的求解策略。仿真结果表明：所建模型和相应的解冲突算法能有效提高测控需求满足率和测控收益。     

带不可用时间段和恶化加工时间的单机调度

对机器带有一个不可用时间段并且加工时间恶化的不可续型单机最大完工时间调度问题进行了研究,简单说明了此问题的NP-困难性,提出了一种动态规算法以得到最优解,并给出了最短正常加工时间优先规则的最坏情况误差界限,最后提出了一种启发式算法采寻求近似解.实验结果表明该启发式算法无论从时间上还是解的质量上都是非常优异的,与动态规划给出的最优解相比,其平均相对误差仅为0.082%,最大误差也仅为3.448%,并且将近有一半的算例能得到最优解.     

任务调度启发式信息的卫星数传ACO算法应用

针对卫星数传调度问题,建立了任务调度启发式信息体系框架,提出了基于任务开始时间、任务调度收益、任务可用资源灵活度和任务调度冲突度的启发式信息,研究了任务调度启发式信息在卫星数传蚁群优化算法中的应用。针对不同规模场景的仿真结果表明,任务调度启发式信息有助于蚁群算法求解卫星数传调度问题。     

混合Flow Shop的调度仿真系统及其算法分析

研究了混合Flow Shop的调度问题，调度目标为最小化工件的最大完成时间。文中给出了调度仿真系统的设计，系统由数据库、算法和控制中心用户接口三个模块组成；在算法模块中，排序算法包括了由Flow Shop扩展到混合Flow Shop的多数算法，设备分配采用最先可用机器优先规则。另外，基于CDS虚拟机和Palmer斜度指标的启发式算法，提出了一种改进的CDS算法用于工件排序。在正在开发的混合Flow Shop调度仿真系统中实现了上述所有算法，仿真分析表明改进的CDS算法优于其他启发式算法。     

单机订单接受与加工调度问题的拉格朗日松弛算法

针对不同类型订单加工切换时机器需要准备时间的实际生产情况,研究了单机订单接受与加工调度优化决策问题,旨在最大化企业净收益。鉴于研究问题的强NP难属性,设计了基于拉格朗日松弛理论的启发式算法。首先,该算法通过加入相邻订单相异性约束以提高松弛解质量;其次,应用动态规划递推公式求解拉格朗日松弛问题;最后,利用问题的优化性质并基于贪婪规则构造原问题可行解。不同规模问题的实验结果表明,该算法能在合理计算时间内得到满意的近优解。     

卫星地面站测控资源调度CSP模型

研究了测控系统资源调度问题的描述与建模问题.在系统阐述综合航天测控网资源调度中涉及的资源、任务、事件、约束基础上,使用变结构半环CSP模型,描述测控调度中涉及的事件窗、时间约束、状态约束、周期性任务、抢先式任务、变长任务等硬、软约束,提出处理任务优先级和不确定性因素的途径.提出的模型对测控系统效能评价及资源调度算法研究也有一定的参考价值.     

面向服务仿真系统的最大可靠性容错调度算法

基于 PB 模型对面向服务的分布式仿真系统的容错调度问题进行了研究.首先,根据该类系统的特点提出了两个命题并以此为基础给出了仿真任务的调度规则;其次,分析了仿真任务的可靠性代价并给出了任务最坏反应时间的计算公式;最后,在此基础上提出了相应的算法RC-RTFT和MW-RTFT.RC-RTFT综合利用了最小可靠性代价及最小最坏反应时间两种启发式规则进行主版本任务的调度,MW-RTFT则基于最小最坏反应时间这一启发式规则进行主版本任务的调度,副版本任务的调度都是基于最小最坏反应时间启发式规则进行.算法仿真结果表明RC-RTFT算法具有较好的负载平衡特性和稳定性,且较MW-RTFT具有更小的算法复杂度.     

复杂时间约束的水利工程项目调度问题研究

水利工程项目的调度属于资源受限的项目调度问题,但现实中这类项目存在着一种复杂的时间约束,即项目中的某些活动在特定时间段内不允许执行.针对这类特殊约束,本文提出了一种新的资源受限项目调度扩展模型,设计了多优先规则的启发式算法进行求解.并在此基础上提出了一种混合遗传算法,构造了新的交叉算子同时结合精英保留和双对齐技术来改善解的质量.最后,用调整后的项目调度问题库(project scheduling problem library)大量实例验证了算法的有效性.     

基于解构造图的卫星数传调度ACO算法

针对卫星数传调度问题,建立了基于任务调度关系（弧模式）和基于任务调度位置（结点模式）的解构造图,提出了基于解构造图的卫星数传调度蚁群优化(ant colony optimization, ACO)算法。算法利用伪随机概率转移规则进行路径搜索,通过划分冲突任务集来限制蚁群的搜索邻域。算法根据迭代最优解和至今最优解进行全局信息素更新,并将构造图中的信息素浓度限制在一定范围内。仿真结果表明,文中提出的两种解构造图及ACO算法是正确可行的,基于结点模式解构造图的ACO算法能获得更优的解。     

Multi-satellite observation integrated scheduling method oriented to emergency tasks and common tasks

Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems.Although many scheduling algorithms have been proposed,emergency tasks,characterized as importance and urgency(e.g.,observation tasks orienting to the earthquake area and military conflict area),have not been taken into account yet.Therefore,it is crucial to investigate the satellite integrated scheduling methods,which focus on meeting the requirements of emergency tasks while maximizing the profit of common tasks.Firstly,a pretreatment approach is proposed,which eliminates conflicts among emergency tasks and allocates all tasks with a potential time-window to related orbits of satellites.Secondly,a mathematical model and an acyclic directed graph model are constructed.Thirdly,a hybrid ant colony optimization method mixed with iteration local search(ACO-ILS) is established to solve the problem.Moreover,to guarantee all solutions satisfying the emergency task requirement constraints,a constraint repair method is presented.Extensive experimental simulations show that the proposed integrated scheduling method is superior to two-phased scheduling methods,the performance of ACO-ILS is greatly improved in both evolution speed and solution quality by iteration local search,and ACO-ILS outperforms both genetic algorithm and simulated annealing algorithm.     

成像卫星协同任务规划模型与算法

作为一类重要的对地观测卫星,成像卫星多星组网协同工作可提高处理复杂任务的能力,其中的任务规划属于多时间窗口、多优化目标和多约束条件的组合优化问题。针对任务协同规划技术,主要完成两项工作：第一,建立协同规划模型,引入了元任务间的3类协同作用关系,并进一步考虑了风险控制的要素;第二,在阐述引入启发式信息的遗传禁忌选择的求解算法基础上,提出算法协同进化模型求解技术。最后,利用卫星工具箱（satellite tool kit, STK）提供仿真数据,评价几种典型的求解算法,并验证了本文算法在收敛速度和鲁棒性上的有效性。     

基于Pareto改进VNS-MMAS的定点修理任务多目标动态调度

针对战时定点修理任务重、修理时间有限、约束复杂的问题,进行了面向定点修理的战时装备维修任务多目标动态调度研究。提出了战时定点修理装备维修任务调度军事问题,考虑修理时间窗、非遍历性等约束,构建了战时装备维修任务多目标动态调度模型。采取分步求解思路处理修理小组分配以及修理任务排序两阶段优化问题,并从状态转移规则、信息素更新规则、先验信息获取3个方面对最大最小蚂蚁系统(max-min ant system, MMAS)算法进行改进,结合变邻域搜索(variable neighborhood search, VNS)算法增强算法的局部搜索能力,设计了基于Pareto改进VNS-MMAS算法实现模型求解,并通过示例仿真验证了模型及算法的科学性与有效性。     

神经网络和启发式算法混合策略解Job-shop调度问题

提出一种有效的自适应神经网络和启发式算法混合策略来求解Ｊｏｂｓｈｏｐ调度问题．自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性，被用来求得调度问题的可行解，而启发式算法被分别用来加速神经网络的运行和保证神经网络收敛到可行解、获得确定排序下最优解和提高可行解的质量．仿真表明本文提出的混合策略是快速有效的     

基于CSP的Job shop调度算法研究

针对一类典型的约束满足问题——Job shop调度问题，提出一种CSP调度算法框架，详细讨论CSP调度算法中的工序开始时间窗、一致性预处理、搜索空间概率模型、工序排序启发、开工时间排序启发的求解方法。仿真结果表明CSP调度算法在较小的计算时间代价下，获得了FT10标准调度问题的近优解。     

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

以应急任务优先调度为原则,保证观测总收益的基础上最小化对原调度序列的扰动是多星应急任务调度领域急需解决的问题。首先,分析应急任务完成时间和观测收益关系,建立考虑时间依赖性收益的数学规划模型。其次,基于遗传算法,提出考虑合成机制的多星应急任务调度算法。设计任务合成、插入和替换算子完成应急任务插入,考虑任务观测收益、序列扰动和最短观测时间设计适应度函数,设计交叉、变异、全局修复算子迭代优化调度序列。最后,通过数值实验表明设计的算法能够显著提高调度质量,适用于多星应急任务调度问题。     

伴随修理中的维修任务调度策略

伴随修理是一种重要的维修保障形式, 合理地调度维修任务将提高伴随修理的效率, 进而将提高作战单元的作战效能. 应用离散事件仿真方法对伴随修理中的维修任务调度策略进行了研究. 首先, 对伴随修理及维修任务调度策略进行了探讨. 其次, 建立了装备作战单元伴随修理的仿真模型. 最后, 应用仿真模型对几种维修任务调度策略进行了仿真评估, 并分别对 平均故障间隔时间(MTBF)、任务持续时间、抢占资源、优先级更新方式的影响进行了分析. 仿真结果表明, 应尽可能 允许重要维修任务抢占所需资源, 调度过程中优先考虑重要的维修任务, 在故障频繁的时候使用"改进的先到先服务(MFCFS)"策略, 故障不频 繁的时候使用"改进的最小处理时间(MSMPT)"策略, 比较可靠的策略是"改进的预测最早完成时间(MEETOC)"策略.