排序方式: 共有91条查询结果,搜索用时 15 毫秒
1.
研究了一类基于MapReduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性. 相似文献
2.
预知信息和有限运载能力下应急车辆路径选择问题 总被引:1,自引:1,他引:0
由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法,分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善. 相似文献
3.
带有预知信息的在线Homing ATSP问题 总被引:1,自引:1,他引:0
针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优. 相似文献
4.
针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据. 相似文献
5.
考虑交通网络中出行者不仅具有路径选择偏好, 同时具有时间偏好的特征, 分别针对出行者是否具有时间或路径选择偏好的4种不 同情形, 建立相应的交通流分配模型. 通过分析这4个模型的性质, 分别给出了有效的求解方法. 在分析4种不同情形 下出行者总出行时间的相互关系基础上, 设计了时间诱导和路径诱导策略. 最后, 以西安市东南郊清明假日交通流分 配为例, 分别模拟分析了不进行诱导, 进行时间诱导, 进行路径诱导的情形下高峰期的交通流分配, 该实例验证了时 间诱导策略与路径诱导策略的有效性. 相似文献
6.
自然灾害的频繁发生使得应急减灾倍受关注, 尤其有效的应急救援车辆调度对应急减灾非常重要. 针对受灾点被提前获知但是不能立即接受救援服务的情形, 通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题, 并分别给出了问题的下界, 直线网络结构下的ENO-dd算法, 和一般网络结构下的GTR-dd算法, 并对算法进行了竞争性能分析. 结果表明两个算法随着预知信息的增多会有明显改进. 更为一般的预知信息结构以及最优的算法设计是下一步研究的方向. 相似文献
7.
8.
9.
外汇兑换是现实中的一个典型占线决策问题。R.El-Yaniv等人将外汇之间的兑换抽象成了一个占线兑换模型,提出了基于风险的兑换策略。在此研究的基础上,本文考虑汇率每日波动在一定范围内的双方向外汇兑换问题,运用博弈的分析方法,给出了占线均衡策略和平均分配策略.并在理论上证明了均衡策略是该问题的最优占线策略,最后通过数值结果对两个策略进行了比较。 相似文献
10.
通过研究带有时限的占线广播调度问题及其贪婪算法竞争比为5、确定性算法的竞争比下界为2.59,来剖析所有请求均为紧时限的特殊情形,并运用最坏情形分析法分析得出,在任意一个连续中断的序列中最大中断比具有逐渐减小的变化特征,进而证明了在所有可能的两类连续中断序列中都不可能存在竞争比小于4的确定性算法.由此得出,当请求均为紧时限时,竞争比下界为4.由于紧时限是任意时限的一个特例,从而得出请求为任意时限时的竞争比下界至少为4的结论. 相似文献