基于MapReduce模型带准备时间的平行机调度优化

研究了一类基于MapReduce模型的平行机调度问题.每个工件包含Map和Reduce两道加工工序,Map工序可以分割为若干个子任务,并且在多台平行机上同时并行加工,Reduce工序只有在该工件的所有Map工序的子任务加工完成后才能进行,而且Reduce只能在一台机器上加工且不可中断.结合工件具有释放时间和加工准备时间等约束,以最小化最大完工时间为目标,构建了混合整数规划模型,并设计了采用差分变异策略和逐维Levy扰动机制的改进正弦余弦算法来求解该模型.最后,利用数值仿真实验与标准正弦余弦算法及遗传算法进行对比,实验结果表明,运用改进正弦余弦算法求解的结果与下界值的平均相对偏差GAP为3.02%,较标准正弦余弦算法以及遗传算法的效果提升显著,显示了该改进算法的有效性.     

预知信息和有限运载能力下应急车辆路径选择问题

由于自然灾害的频繁发生,灾后的应急物资车辆调度受到了人们的广泛重视.针对应急物资车辆装载能力有限和受灾点被提前获知但是不能马上被服务的情形,提出了具有预知信息的在线配额旅行商(quota TSP)问题,分析了该问题的下界,针对受灾点仅在正半轴上的情形设计了MLIB算法和SW算法,对于一般网络设计了Greedy算法,分别分析了三种算法的竞争性能.结果表明算法的竞争性能会随着预知信息的增加而得到改善.     

带有预知信息的在线Homing ATSP问题

针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.     

具有服务时长的在线TSP问题

针对城市快递揽件服务过程中,需求事先无法预知并且每个需求服务时长不确定的情形,提出具有服务时长的在线TSP问题.分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法,在直线上给出PQR-ST算法,并对算法进行了竞争性能分析.本文提出模型是在线TSP问题的一般形式,结论可以为快递车辆的实时调度决策提供依据.     

基于预知信息的占线Nomadic TSP问题

自然灾害的频繁发生使得应急减灾倍受关注, 尤其有效的应急救援车辆调度对应急减灾非常重要. 针对受灾点被提前获知但是不能立即接受救援服务的情形, 通过将受灾点(需求)的揭露时间和释放时间引入Nomadic TSP模型中构建了预知信息的占线Nomadic TSP问题, 并分别给出了问题的下界, 直线网络结构下的ENO-dd算法, 和一般网络结构下的GTR-dd算法, 并对算法进行了竞争性能分析. 结果表明两个算法随着预知信息的增多会有明显改进. 更为一般的预知信息结构以及最优的算法设计是下一步研究的方向.     

城市交通网络中商业街的选址分析与计算

商业街在城市交通网络体系中的选址是商业街布局的重要方面。本文提出交通网络商业街选址问题并建立数学模型，给出了两种选址原则：（1）城市中所有节点至商业街（只需要达到商业街的其中一个节点）之间的最短路径之和最小。（2）城市中所有点对之间过商业街的最短路径之和最小。针对以上两个方面，分另4给出其计算方法，并进行了算法的时间和空间复杂性分析。     

(θ,n)对手策略下的双方向外汇兑换问题及其竞争策略分析

外汇兑换是现实中的一个典型占线决策问题。R．El-Yaniv等人将外汇之间的兑换抽象成了一个占线兑换模型，提出了基于风险的兑换策略。在此研究的基础上，本文考虑汇率每日波动在一定范围内的双方向外汇兑换问题，运用博弈的分析方法，给出了占线均衡策略和平均分配策略．并在理论上证明了均衡策略是该问题的最优占线策略，最后通过数值结果对两个策略进行了比较。     

关于占线广播调度问题的一个下界

通过研究带有时限的占线广播调度问题及其贪婪算法竞争比为5、确定性算法的竞争比下界为2.59,来剖析所有请求均为紧时限的特殊情形,并运用最坏情形分析法分析得出,在任意一个连续中断的序列中最大中断比具有逐渐减小的变化特征,进而证明了在所有可能的两类连续中断序列中都不可能存在竞争比小于4的确定性算法.由此得出,当请求均为紧时限时,竞争比下界为4.由于紧时限是任意时限的一个特例,从而得出请求为任意时限时的竞争比下界至少为4的结论.     

基于风险补偿的占线拍卖策略

扩展了传统的占线算法及其竞争分析框架，在此基础上建立网上占线拍卖的风险模型．为具有风险偏好的占线拍卖人设计了风险忍耐策略（RTS），并得到了该拍卖策略的竞争比．使占线拍卖人可以根据自己不同的风险容忍度和未来预期选择最优的拍卖策略。     

连续网络上的占线可恢复加拿大旅行者问题

针对堵塞完全在无法预知的情况下一个个出现，且堵塞恢复时间信息可以获取的占线可恢复加拿大旅行者问题，给出连续网络上的等待策略和移动策略以及相应策略下的竞争比，并对两种策略的执行效果进行分析和比较。