具有优先关系的累积调度问题的约束传播算法

约束传播是约束规划成功应用的关键技术之一.针对累积调度问题提出一种结合工作间优先关系和工作最早开始/最晚完成时间约束的约束传播算法,给出了算法的理论依据.引用资源受限项目调度问题库PSPLIB中的典型问题对算法进行了测试,结果表明:针对测试问题新的约束传播算法在总体约减效果上优于现有约束传播算法,新算法与基于能量推理的约束传播算法可以互补,两者结合推理效果更好.

基于约束程序累积调度的编组站静态配流模型研究

静态配流是铁路编组站阶段计划的核心,模型和算法的优劣直接影响编组站作业效率和经济效益。本文基于约束程序累积调度和字典序多目标优化理论,考虑配流成功的出发列车优先级总和最大、出发车流来源总数最小、到达车辆先到先发等具有字典序的3个目标,以满轴、正点、不违编、解编顺序及编组场容量限制等为约束条件,建立静态配流字典序多目标累积调度模型。采用迭代、约束传播和回溯算法求解。通过现场实际数据验证:本算法求解时间满足现场要求;模型稳定、扩展性好,符合实际需求。

全负载场景中最优调度算法长时平均性能分析

首先分析了全负载场景中轮询调度、最大速率调度、比例公平调度和速率累积分布调度这4种常用调度算法.结果显示,速率累积分布调度在保证公平的基础上可以得到最好的效率,是4种调度算法中的最优算法.然后采用概率推导法给出了该调度算法的长时平均性能分析,即以轮询调度为比较基准的多用户分集增益的理论推导.该分集增益可通过短时统计结果预测长时平均性能,且可适用于任意实际场景.计算机仿真结果验证了对于该调度算法所产生的多用户分集增益理论分析的准确性,理论分析结果与实际调度结果的误差低于0.1%.