卫星观测系统整体调度的收发问题模型及求解

探讨了一类涉及多星、多地面站、多任务的卫星观测系统整体调度问题,该问题要求从过多赋权卫星观测需求中,选择有能力完成的一个任务子集,并为相应的拍照和数据下传活动安排资源和时间,以实现特定的优化目标.用一种变体形式的收发问题模型描述了该问题,并给出了其约束规划和禁忌搜索相结合的求解方法.最后用随机生成的问题示例检验了求解算法的性能.     

编队卫星对地观测调度问题模型比较研究

研究了编队卫星对地观测调度问题。分别建立了基于问题自然描述和基于有向图描述的两类整数规划模型,运用整数规划凸包理论比较了两类模型与各自对应的线性松弛模型之间的最优值差异,得出了基于有向图描述的线性松弛模型更接近于原问题凸包的结论,并基于有向图描述模型设计了不完全分支定界算法。最后,在随机生成的仿真算例下,运用ILOG CPLEX实现了该算法,实验结果表明了模型及算法的有效性,并验证了对于两类整数规划模型的边界分析。     

成像卫星集成调度的变邻域禁忌搜索算法

探讨了一类涉及多星、多地面站的成像卫星系统集成调度问题,要求从可能过度订购的卫星观测需求中,选择一个能够无冲突完成的任务子集,并为相应的观测和数据下传活动安排资源和时间,以最大化对所有用户需求的总体满足程度.建立了该问题的变体形式车辆路线问题模型,设计了改进型和调整型两类邻域结构,并提出了一种变邻域禁忌搜索算法.通过交替使用两类邻域结构,增强了算法对解空间的探索能力和规避局部极值的能力.测试算例的计算结果和与其它算法的比较表明,该算法能够在相近的计算时间内显著改善求解质量.     

卫星合成观测调度的最大覆盖模型及算法研究

遥感卫星采用合成观测方式可以提高观测效率,研究了遥感卫星合成观测调度问题.通过分析观测活动与目标的覆盖关系,建立了考虑任务优先级的最大覆盖模型.分析了观测活动性质,并基于观测活动间存在时序关系特征,将问题按照卫星的最大侧摆次数划分为多个阶段,提出了基于动态规划思想的算法,能够在多项式时间内得到问题的最优解.测试算例验证了算法的有效性.     

VFP＆VRP联合优化模型及其多目标遗传算法

单车型非满载问题是十分典型和重要的物流配送问题之一．单车型非满载问题通常包括物品装车（VFP）和车辆路径安排（VRP）2个紧密相关的子问题．研究同时考虑VFP和VRP讲两个因素的联合优化问题，建立了多目标优化模型，设计了模型的多目标遗传算法，并结合实例验证模型和算法的有效性．     

卫星测控资源调度CSP模型研究

对卫星测控调度问题的建模技术进行了研究,分析了问题的特点。首先对场景、需求和任务进行了形式化建模;然后针对测控调度问题中涉及的资源、时间、关系等主要约束类型进行了分析和模型描述,并按照不同类型的测控需求确定了测控调度的目标函数;最后在此基础上建立了问题的约束满足问题(constraint satisfied problem, CSP)模型,并针对模型进行了求解方法研究。     

一类对地观测卫星成像调度系统的设计与实现

针对一类光学小卫星成像调度的应用需求,综合考虑星地等各种资源的载荷使用约束,设计实现了一个成像调度系统.详细分析了载荷约束,针对约束特点,提出了五阶段系统执行流程,并重点介绍了各阶段的关键技术,包括基于成像约束图的观测动作生成算法和基于背包模型的数传动作生成算法.最后给出了应用实例和实验结果,表明了系统的适用性和可行性.该系统已经成功应用于某在轨卫星的日常规划中.     

基于任务合成的对地观测卫星应急调度方法

针对应急条件下对地观测任务时敏度高、动态性强的特点,提出了基于任务动态合成的多星应急调度方法。首先,建立了多星动态应急调度数学规划模型。然后,提出了任务动态合成(dynamic merging,DM)策略,并设计了候选合成任务集合构建(candidate merging task set establishment, CMTSE)算法。最后,提出了基于任务动态合成的多星动态应急调度(dynamic merging based dynamic emergency scheduling, DM DES)算法。为验证DM DES算法的有效性,通过大量仿真实验将DM DES与基于迭代修复的启发式算法(repair based heuristic algorithm, RBHA)和不考虑任务合成的动态应急调度(dynamic emergency scheduling, DES)算法进行比较。实验结果表明,DM DES算法能有效提高调度质量,适用于多星动态应急调度。     

不确定环境下多星联合观测调度问题研究

在分析多星联合对地观测活动中存在的不确定性因素基础上,研究对其量化描述方法,定义了卫星观测活动的信息收益和发现目标收益,将两者的组合作为目标函数建立了多星联合对地观测调度模型,仿真结果表明该模型能够解决不确定环境下多星联合对地观测问题,并且性能优于随机观测模型和均匀覆盖观测模型。     

敏捷成像卫星时间依赖型调度问题、模型与算法

针对敏捷成像卫星时间依赖型调度问题展开研究,将时间依赖调度与敏捷成像卫星调度相结合,在分析主要约束条件的基础上,建立了问题的数学模型.根据成像质量随成像时间动态变化的特点,设计了随时间动态变化的收益函数,并将轮盘赌思想和时间窗口裁剪概念引入到求解方法中,提出了一种启发式算法.实验数据显示,通过对时间依赖的考虑,更多的任务能够在最佳观测时刻点附近成像,同时也表明了模型的合理性以及算法的有效性.     

带瓶颈移动法的混合遗传算法求解柔性作业车间调度

柔性作业车间调度问题是对传统车间调度问题的扩充，它更接近于现实的生产调度问题。针对柔性作业车间调度问题，提出了带局域搜索（瓶颈移动法）的混合遗传算法。区别于传统的遗传算法，本文算法用两个向量束表达解，并采用了适应问题特征和染色体结构的交叉和变畀算子。基于关键路径的思想，舰颈移动法使用两种有效的邻域结构；改变关键路径上相邻两工序的加工顺序和为关键路径上的工序分配新设备。为了提高搜索能力，邻域结构可以动态调整。我们在3个代表性标准测试问题上检验了该算法的求解性能。     

单车场复杂情况下的车辆调度

针对单车场复杂情况下的车辆调度问题提出了一种改进的禁忌算法。该算法基于自然数编码，并且采用多初始解和全局禁忌表等技术，把不同的车型指标、路况信息、时间窗、容量、发车时间等约束通过控制车场插入和惩罚项加入到优化解中。本文介绍了此算法的原理，给出了具有代表性的算例试验结果和结果分析。实验表明，此方法对求解复杂情况下的车辆调度问题是有效的。     

具有时间窗口约束的并行机床调度问题研究

具有时间窗口约束的并行机床调度问题可以被描述为在M台互不相同机器上安排加工N个工件。每个工件只能在一个给定机器子集中的一台机器上加工，且加工过程只能在给定的离散时间窗口内进行，并且工件的加工时间长度和时间窗口约束与加工机器有关。为了解决该问题，本文给出一种集成约束规划与禁忌搜索的搜索算法，其中约束规划系统被作为验证解的可行性和确定变量的值，而禁忌搜索过程被用来对解空间进行搜索。讨论禁忌搜索过程中的初始解产生、邻域结构、禁忌列表、解空间搜索等算法设计问题。最后给出算法在不同问题实例上的算法效率比较及分析。     

实时条件下多车辆路径与调度

研究实时条件下的多车辆路径与调度问题，重点研究了多种费用，包括车辆空驶费用、任务延迟费用和任务拒绝费用下的问题模型及求解。给出了问题的数学描述，并对其静态问题，构造了一个混合整数规划模型。随后提出了两种滚动时域求解策略。最后通过仿真实例，对几种策略的性能进行了对比。     

有交货期的单件车间调度问题的逆序算法

提出了一种以“加工效率”为主要参数,并引入“虚工序”、“虚机器”求解有交货期的单件车间调度问题的逆序算法． 经分析实例验证,该算法具有一定的优度,并且在工程中是可行的．     

一类含时间窗口的多资源动态调度问题的建模与求解方法

摘要内容含时间窗口的多资源调度，是一个包括资源分配和时间窗口分配的两阶段优化过程。资源在初始调度方案执行过程中可能会出现故障，而使初始方案不能继续执行，需要对初始方案进行调整。本文针对这种情况，分析了该问题中的主要约条件，建立了含时间窗口的多资源动态调度模型，给出了一种启发式搜索方法；并以含时间窗口的并机调度问题为例，对模型和算法进行了验证。     

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

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

带时间窗的局内开放式车调度问题的竞争分析

对于带时间窗的局内车辆调度问题，以往文献的研究都是关于k=1的单车调度，其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆丰（k≥2）调度的研究分析，设计了解决试问题的竞争算法，并证明了其竞争比为3．5。同时本文分析了该问题的一种特殊情形——单车调度问题，可证明其竞争比为3．优于已有结果。     

无重叠区的两抓钩周期性排序问题的一个搜索求解法

在当今的自动化制造系统中,计算机控制的抓钩的排序直接影响系统的生产率.本文研究了产品在生产线两端装载和卸载的电镀线的周期性抓钩排序问题,目标是极小化生产周期.本文把生产线分成无重叠的两部分,并给每部分分配一个抓钩,构成一个无重叠两抓钩周期性排序问题.为了求解该问题,提出了一种基于线性规划模型和禁忌表的搜索算法.这个算法使用测试的周期长度作为控制参数以产生不同的运送顺序,对每个给定的运送顺序和抓钩分配,用线性规划模型求得子问题的最优解.在搜索中,为了避免相同序列的子问题模型的求解,采用了禁忌表.量化的示例表明所使用的方法是高效的.     

基于混合遗传算法的物流配送车辆调度优化问题求解方法

物流配遥车辆调度优化问题是一个NP-hard问题,随着问题规模的扩大,若单纯地应用精确算法将很难获得最优解.首先对物流配送车辆调度问题进行了深入分析并建立了优化数学模型;然后,根据模型把问题的解决合理地划分为两个阶段,将遗传算法的全局搜索能力和C-W节约启发式算法的局部搜索能力有机结合,由此构造出一种混合遗传算法;最后,通过一个应用实例的分析验证了此算法寻优的有效性.