局内封闭式车辆调度问题及其竞争策略

基于k-卡车问题和局内运输问题,提出了具有时间窗的局内封闭式车辆调度问题,建立了相关的模型,研究了当车辆数为1时该问题的竞争分析的有关结果,给出了三种不同的竞争策略,得到了相应的竞争比,并进行了理论证明.     

具有时间窗的局内开放式车辆调度的竞争分析

基于k-卡车问题和局内运输问题，提出了具有时间窗的局内开放式车辆调度问题．该问题的优化目标为：在服务需求的发布为局内方式的条件下，如何最小化完成整个服务需求序列的时间跨度．建立了该问题的数学模型并对有关的概念和参数进行了定义和说明．研究了当车辆数为1时该问题的竞争分析的有关结果：给出并证明了对于该问题的竞争策略的竞争比下限；针对该局内问题，设计了两种不同的竞争策略，得到了相应的竞争比，并进行了理论证明．     

有限使用寿命情形下局内设备的赁购决策

局内设备赁购模型(RBP)是局内问题中被广泛研究和应用的经典模型。但在该模型以往的研究中,都假设设备的使用寿命无限长,这导致了模型本身的一些不足。为此,提出了有限使用寿命情况下的局内设备赁购模型。研究意外地发现,考虑设备寿命后,最优策略组合中可能不存在"购买行为"(M<2 N时),这在经典设备赁购模型中是不可能的;在考虑了设备寿命之后,租赁方的最优决策将与出租方的利润有关,这也是经典模型所忽略的。最后,对有限寿命设备赁购模型的经济意义和具体应用进行了说明。     

突发事件下的局内单机调度

研究决策者面对突发事件,应对单机调度中的应急管理问题.在完全没有突发事件发生时间和发生次数信息条件下,利用局内决策理论与方法构建确定情形下的应急策略,并利用"竞争比"说明该策略的有效性.在此基础上进一步研究随机模型下的平均竞争比.理论和数值分析表明指数分布的引入使得竞争分析的性能得到显著改善.     

考虑二手货市场的在线租赁决策与竞争

以往的在线租赁研究基于Karp提出的“雪橇租赁”模型,其假设当租赁方购买设备后不允许出售.研究了存在二手货市场的在线设备租赁问题,即购买的设备可在二手货市场上出售.讨论了设备在二手货市场出售价格为2种不同情形下问题的竞争策略.第1种情形,出售价格围绕购买设备的剩余价值(购买价格与价值损耗量之差)上下波动,分析了问题的离线最优解,并证明不存在具有常数竞争性能比的租赁策略.第2种情形为第1种情形的特例,其出售价格完全由购买设备的剩余价值决定,给出一个租赁策略,并证明了该策略为最优策略,其竞争比小于Karp“雪橇租赁”模型中最优策略的竞争比.     

基于概率分布的局内特殊优惠卡问题及其竞争分析

特殊优惠卡问题是租赁问题的推广.应用平均情形竞争分析研究了局内特殊优惠卡问题,理论和数值分析表明概率分布的引入使得竞争分析的性能得到了改善.并对存在市场利率的特殊优惠卡问题进行了讨论,市场利率的引入使得该金融模型更贴近于现实情况.得到两种情形下不同的竞争比,同时竞争比是市场利率的递减函数.     

成对需求的局内k-服务器问题及其工作函数策略

提出了多需求的k 服务器问题,建立了数学模型.研究了问题空间为k+2时的一个特例:即在任一时刻点都同时有两个服务需求提出.给出了此特例的工作函数策略,进行了相应的策略分析并给出了竞争比的证明.关于成对及多需求k 服务器问题的一般情形的策略设计及理论证明仍然是公开问题.     

基于所得税的设备赁购问题在线策略与竞争分析

由于所得税在企业租赁和购买设备时影响成本的方式不同导致实际设备使用费发生变化,因此,需要在市场环境下考虑所得税对企业设备赁购行为决策的影响。将所得税概念引入经典在线租赁问题,提出了基于所得税的在线设备赁购问题。给出了该问题的离线最优解,设计了在线赁购策略RBS和租赁策略RS并进行竞争分析得到策略竞争比和问题下界。当设备寿命期内一直租赁费用与设备购置费用比值小于与所得税税率相关的函数值时,证明了策略RS是最优在线策略。最后,通过算例,结合实际中一般居民企业、小型微利企业和高新技术企业等3种不同类型企业缴纳的不同所得税税率,证实了所得税税率高低会影响企业的在线设备赁购决策和技术更新行为。     

基于物价指数上涨的最优在线租赁决策模型

考虑到现实租赁市场设备租金费用及购买价格随着时间推移总体呈现出持续性上涨特征, 建立了基于物价指数上涨的在线租赁决策模型, 首先分析了该问题的最优离线策略, 其次运用在线算法理论给出了该问题的确定性最优在线租赁策略及其竞争比. 从提高策略的竞争性能角度出发, 基于风险控制思想, 给出了该问题的随机性最优在线租赁策略及其竞争比, 并运用两人零和博弈分析技巧严格证明了此策略是该问题的唯一随机性最优竞争策略. 进一步指出了确定性和随机性最优策略的竞争性能均随着购买价格上涨而下降, 也随着物价指数上涨而降低. 最后, 结合数值分析发现当存在通货膨胀因素时, 最优决策日期相对提前, 但策略的竞争性能显著降低, 这表明物价指数变动对在线租赁决策具有显著影响.     

局内军车调度的时间优化及其竞争策略

提出时间目标函数下的局内k－军车调度问题，应用复位策略给出该问题的几种竞争算法：给出了对应的局内k－服务器问题的竞争比的c时的该问题的竞争比为c 1 1/θ的竞争算法；分别给出了当k=n和k=n-1时该问题的竞争比为1和1＋1／θ的竞争算法。     

加拿大旅行者问题

针对加拿大旅行者问题 ,分析其主要变形——确定型可恢复的加拿大旅行者问题。考虑堵塞边动态产生 ,一个遇到且堵塞边在时间 l( x,x)后可以自动恢复情况下的道路选择。通常对于在线算法可以从两个方面进行评价 :最坏情形分析和竞争比分析。本文先设计了求解最坏情形下旅行时间最短的标号算法并分析了其计算复杂性。而后在竞争比分析中 ,设计了基于贪婪原则的选路策略 ,并对其进行了竞争比分析 ,证明了该贪婪策略对于确定型可恢复加拿大旅行者问题的竞争比为 ( k+ 2 ) /2     

特殊在线优惠卡问题及其竞争分析

商家在策划优惠卡发行时需要严密论证发行价格和折扣率等因素对消费者消费行为的影响. 利用在线算法和竞争分析理论, 研究了消费者对同时发行的两种优惠卡的在线决策问题. 一方面得到了最优确定性策略及其竞争比; 另一方面构造了一个随机性策略, 得到了最优随机性策略竞争比的一个上界, 并利用Yao引理得到了随机性策略最优竞争比的一个下界. 借助于数值算例, 分析了各因素对在线策略及其竞争比的影响. 研究结果可以为优惠卡发行价格和折扣率的决策提供依据.     

具有美式看跌期权的单方向在线外汇兑换竞争策略设计

El-Yaniv等学者首次运用在线算法及其竞争分析方法研究了单方向在线外汇兑换问题, 提出了基于汇率突然下跌威胁的在线兑换策略. 结合期权工具改进了该兑换策略对汇率上、下界的估计, 即不估计汇率波动的下界, 仅估计上界. 利用看跌期权以第一期汇率价格为敲定价格锁定后续汇率波动的最低交易底价, 同时利用首期汇率信息对汇率上界进行估计, 从而这样预估的上界较El-Yaniv等学者模型中估计的上界更准确. 当汇率上界确定后, 分别给出了兑换期限已知和未知两种情形下的最优在线兑换策略, 并与El-Yaniv等学者给出的兑换策略进行了对比分析. 最后, 通过算例分析说明了当El-Yaniv等学者模型中的下界和上界参数相差很大时或末期汇率出现大幅下跌时, 本文所提出的结合期权工具的在线交易策略的竞争性能更具有优越性.     

占线顶点覆盖问题的结构性下界

在实际 顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.     

堵塞恢复时间随机的在线加拿大旅行者问题

针对旅行者在行走过程中遇到的某一或一系列无法预知堵塞事件的加拿大旅行者问题,考虑每个堵塞恢复时间是一个相互独立随机变量的情形,从在线问题与竞争策略的角度,给出了每个堵塞恢复时间都为均匀分布下的等待策略和贪婪策略以及相应策略下的竞争比,并对两种策略的执行效果进行了分析和比较.     

原材料采购问题的占线竞争策略分析

研究的是价格不确定条件下的原材料采购问题.在实际的原材料采购决策中,经常会遇到如下情形:特定时间内某原材料的价格随时间的变动具有不可预期性,同时该原材料具有固定的需求消耗.为了最小化采购费用,我们需要在满足需求的条件下确定在什么时间,以什么价格以及采购多少的决策问题.以往的研究一般都是假设采购价格是随机波动的,而实际情况中价格常常是不可随机观测的.本文从占线理论出发考虑了原材料占线采购问题,设计了一个竞争策略,证明了相应的竞争比,该竞争比结果优于已有结果.     

连续双向拍卖机制下的短期价格行为分析

建立描述限价指令市场中连续双向拍卖交易机制下短期价格动态变化的理论模型.通过对该机制下的几个特征变量包括最佳(高)买价、最佳(低)卖价、买卖价差、成交价格和成交概率的分析揭示连续双向拍卖机制下的短期价格行为,并着重探讨其均衡性质包括成交价格所收敛到的竞争均衡及达到均衡的时间.研究结果表明建立的理论模型能较好地刻画连续双向拍卖机制下短期价格的动态演进特征,进而印证连续双向拍卖交易机制能快速收敛到竞争均衡从而产生很高的价格发现效率的相关结论.