为了最小化一些扰动对系统性能的影响， 启动重调度是必需的。Wu 研究用有效性和稳定性作为标准的单机重调度启发式算法。Shafaei 提出动态和随机环境的调度规则的鲁棒性。Wu 等设计了一个半在线的方法对Job-Shop 问题生成鲁棒调度， 实质是一种先预处理后调度的方法， 将离线方法的全局视角和在线调度的自适应性结合起来。目前， 关于模糊调度问题的研究， 主要集中在模糊数的操作问题上， 包括模糊数......
2023-06-20
抢占式快速动态调度算法优化
【摘要】：在Step3中，对冲突的任务进行重调度，为避免冲突的传递和保证算法的效率，重调度的执行深度设置为1，即只对冲突任务执行一次直接调度操作，而不继续进行间接调度操作。在Step3中，冲突任务被替换后若能重新调度，则将执行“整传插入操作”或“续传插入操作”，分别定义为“移动整传操作”或“移动续传操作”；若不能重新调度，则被删除，定义为“删除替换操作”。
由上节内容分析可知，中继卫星的动态扰动通常具有很强的突发性，而响应过慢可能使对突发问题的处理失去意义或错失最佳处理效果。另外，很多突发任务需要实时调度，因此，对扰动的反应速度是系统稳健性的一项重要指标，动态资源调度策略的设计需要重点考虑新调度方案的快速生成。
微波与激光混合链路中继卫星系统的动态调度问题是一个动态的约束满足问题，若对问题进行全局寻优，可获得最大收益的调度方案。但全局寻优获得的调度方案与初始调度方案必然存在很大变化，另外，全局寻优也难以达到快速调度的要求，因此，动态资源调度应采用启发式的邻域搜索策略。启发式的邻域搜索策略为：以初始调度方案和新任务调度的约束条件为启发式信息，分别以3个动态调度目标为调整原则，只对初始调度方案进行部分调整，从而实现新任务的调度和减少方案的变化。因此，启发式的邻域搜索属于局部搜索算法，可实现快速调度的目的。
抢占式快速动态调度算法基于启发式的邻域搜索策略，其主要思想是：在新任务的有效时限内，存在可完成该任务的空闲资源，则直接调度该新任务，从而实现最大方案收益和最小方案变化的目标；若不能单次完成整个任务，则尝试多次续传完成。但当新任务有效时限短，且优先级高时，通常难以找到可完成新任务的空闲资源，则尝试移动或删除部分冲突的旧任务，以实现新任务的间接调度。算法具体流程如图9-21所示。
图9-21 抢占式快速动态调度算法流程
9.6.2.1 直接调度操作
直接调度的基本思想是：在不改变初始调度方案的前提下，在任务有效时间范围内，利用其可用资源的空隙时间单次完成整体任务或多次续传完成任务。直接调度新任务主要包括两种插入操作，分别为“整传插入操作”和“续传插入操作”新任务。两种操作均建立在不改变初始方案的基础上，只利用可用资源在初始方案中的空隙时间完成突发新任务的调度。因此，新任务的插入位置即为初始方案中各旧任务的结束时刻。其具体操作过程如图9-22所示。
图9-22 直接调度操作流程
由于资源的空隙时间开始时刻即为已调度任务的结束时刻，因此，在Step4中新任务允许插入的开始时刻即为其可见时间窗口的开始时刻和窗口内已安排任务的结束时刻。由于任务续传次数过多将降低用户的服务质量，且给系统带来更多的额外开销，因此，算法限定任务的最大续传次数为N conti＿trans（如图9-22中Step6所示），这里设置N conti＿trans为3。Step6中任务续传相关的约束条件与前述主要约束条件一致。
当新任务实现直接调度时，即可获得最大的方案收益。但由于新任务多为突发的紧急（有效时限短）、重要（优先级高）任务，通常难以“整传插入”或“续传插入”。因此在Step6中，当新任务不能直接调度时，则执行间接调度操作。
9.6.2.2 间接调度操作
间接调度新任务的主要思想是：当突发的新任务不能直接调度时（通常此类新任务优先级高，且有效时限短），可对初始方案进行适当调整（包括移动或删除冲突的旧任务），以完成对新任务的调度。间接调度操作包括两个步骤，分别为“替换冲突任务”和“重调度或删除冲突任务”。其具体操作过程如图9-23所示。
在图9-23的Step2中，需要对新任务与冲突任务进行优先级比较后再执行替换操作，表明调度新任务时不允许调整高优先级任务。在Step3中，对冲突的任务进行重调度，为避免冲突的传递和保证算法的效率，重调度的执行深度设置为1，即只对冲突任务执行一次直接调度操作，而不继续进行间接调度操作。因此，冲突任务被替换后将执行“整传插入操作”或“续传插入操作”，由于插入点包括新任务可见时间窗口的开始时刻，而此时可能已调度任务正在执行。因此，当出现紧急且重要的新任务时，执行间接调度操作可能使正在执行的已调度任务被迫中断，因而任务未执行部分通过选择资源的空闲时段进行续传。
在Step3中，冲突任务被替换后若能重新调度，则将执行“整传插入操作”或“续传插入操作”，分别定义为“移动整传操作”或“移动续传操作”；若不能重新调度，则被删除，定义为“删除替换操作”。在Step4中，新任务调度后，根据冲突任务执行的操作类型，则可采用式（9-18）～式（9-20）计算各目标值，从而对各插入点对应调度方案的临时解进行评价。
虽然对新任务执行间接调度操作可增加方案的收益，提高系统的效能；然而此操作也增加了初始方案的变化和任务的总续传次数，在另一方面又降低了用户服务质量。因此，插入的高优先级新任务越多，获得的方案收益越大，而系统付出的代价（方案变化和续传任务总续传次数）也越大，如何权衡方案收益和代价，是动态资源调度算法需要解决的另一关键问题。
图9-23 间接调度操作流程
有关空间激光微波混合信息网络技术的文章
- 详细阅读
-
混合链路中继卫星网络动态资源调度方法优化详细阅读
特别在混合链路系统中，由于激光束发散角极小，卫星平台的振动将影响光束对准，造成信道质量的严重恶化或链路中断。为适应混合链路系统执行调度方案的不确定性和突发的数传任务，须对混合链路中继卫星系统提出动态资源算法，以提高系统的鲁棒性和资源利用率。针对此问题，本节分析了混合链路中继卫星系统的扰动因素，讨论一种允许任务中继续传的抢占式动态资源调度算法。......
2023-07-02
-
粒子群算法优化半导体生产调度的关键步骤详细阅读
表6-2每个工序对应工件的优先水平表6-3某一粒子编码在粒子算法求解调度问题中， 一个粒子代表一个调度方案。粒子的维数等于每个工件经过加工环节数量之和。在计算初始时刻， 粒子的初始种群和初始速度都是随机产生的。位置的先后也是调度方案中执行生产的先后。粒子算法可以适合大规模的调度研究， 并......
2023-06-20
-
水库水量调度优化技术详细阅读
式中V死——卧虎山水库死水位对应库容；V兴——卧虎山水库兴利水位对应库容。水库供水时，首先应满足城市供水，其次满足河道生态补水，最后满足农业用水。根据各用水户的保证程度和优先顺序，调算时须设定各用水户供水限制条件。当水库水位低于某用户供水限制线时，该用户供水将遭到破坏；当水库水位高于该用户供水限制线时，可保证该用户供水。......
2023-06-25
-
ATO模式下的动态塔调度问题分析详细阅读
然而在需求降低的时候， MTO 模式的生产不能够充分利用产能。因此， ATO 模式对客户的响应比传统的MTO 模式快， 而库存比MTS 模式低。Wei 和Sun 在ATO 生产模式下研究了相关性产品问题， 预计了总利润函数的库存管理问题， 对两个终端产品不同阶段随机非整数规划进行制定、 分解， 并对提出的算法进行了验证。Huang 等考虑了MTO 模式下生产调度和订单选择问题。......
2023-06-20
-
建立综合优化调度评估模型详细阅读
本节将运用赋权重的方法考虑各方面约束，以防洪、发电、航运、泥沙为主要优化目标，建立综合优化调度方案评估模型，为三峡水库选定优化调度方案提供决策支持。......
2023-06-21
-
提升调度算法性能的方法详细阅读
9.4.5.2调度优化性能分别以32，64，80，100个任务量的仿真场景进行计算，对于每个场景进行100次仿真优化，优化结果取均值与标准遗传算法的优化结果进行比较，比较结果如表9-5所示。......
2023-07-02
-
汛限水位调度目标优化详细阅读
汛限水位优化调度的目的，就是在平衡各运用目标要求的前提下，充分利用弃水，进一步发挥水库综合效益。在求解上述三峡水库汛限水位调度优化问题时，可根据约束法将多目标优化问题转变为单目标优化问题。在防洪目标和下游航运目标转化为约束条件后，三峡水库汛限水位优化调度目标转换为:在不降低目前防洪标准和改善下游航运条件的前提下，获取最大的发电及上游航运综合效益。......
2023-06-22
相关推荐