可退占线优惠卡问题及其竞争分析

占线优惠卡问题是租赁问题的推广.定义了退卡费用函数,在此基础上提出了可退占线优惠卡问题.从传统竞争分析的角度,给出了最优购买策略及其竞争性能分析(竞争比上下界证明).在上述工作的基础上,将风险管理引入到竞争分析,分别给出了不同预期下的最优风险竞争策略,使决策人的决策行为更加贴近实际.     

基于系统最优策略的占线交通流量分配

针对n次连续的交通需求依次到达出发点选择路径到目的地去的问题,本文从占线与竞争策略的角度出发,研究流量是任意可分的情形下交通流量分配,采用系统最优策略分配交通需求,即每次分配流量后都能使得当前网络上所有用户花费费用总和最小.借助于变分不等式对系统最优策略进行了竞争分析,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+)d+1-竞争的,同时给出系统最优策略竞争比的下界是5/3.     

工程项目进度-费用优化的占线风险补偿模型

针对关键活动发生不确定性延误的项目进度{}\,-{}费用优化问题,从占线策略与竞争分析的角度, 设计了占线预赶工策略,给出了策略竞争比, 同时分析了一般赶工策略与离线最优策略的关系,得到了关于一般策略费用与最优策略费用比值的三条性质,进而证明占线预赶工策略是最优确定性竞争策略. 在此基础上,引入风险补偿模型, 设计了具有不同风险偏好的风险补偿策略,使具有不同风险偏好的项目管理人员可以根据自己的偏好与预期选择最优的风险策略.     

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

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

有阈值约束的占线订单加工策略及竞争分析

结合生产订单管理的实际情形,将服务质量(QOS)的概念引入订单排序加工问题,并运用占线理论与竞争分析方法对此问题进行建模与剖析。在有QOS要求的模型中,订单收益与订单完成百分比成正比;在实际情况下,只有当订单完成百分比超过一定量时才是有效加工并获得相应收益。因此,构建了具有完成度阈值限制的可中断占线订单加工模型;其次,运用贪婪设计思想给出一个确定性占线策略并证明其具有竞争比(1+3α)/(1+α),其中,α∈[2/3,1)是订单完成度阈值参数。     

具有交货期限的占线订单加工

探讨一类占线订单加工问题，具体分析当订单交货时间具有一定上限约束时的不可中断和可中断两种模型。对于不可中断模型，证明先到先服务策略在两种不同交货期限约束时分别是最优策略与最优占线策略；对于可中断模型，提出了基于先到先服务原则的可中断策略，并证明当交货期限小于3倍加工时间时该策略具有竞争比3／2。     

存在市场利率条件下的占线租赁策略研究

基于占线租赁问题的输入结构简单且具有良好的统计特性，运用竞争分析方法并结合输入结构的分布信息建立最优占线租赁决策模型，突破纯竞争分析有意规避概率分布这一假设条件，分析当存在市场利率因素时的占线租赁策略，并给出最优的竞争策略及其竞争比。相对于Karp及EI-Yaniv等人的研究结果，由于引进了输入信息使得竞争比性能分析提高；相对于Fujiwara等人的研究结果，本文研究了存在利率时离散性情形，给出了问题的最优解。     

占线订单排序D-收益函数下改进的随机策略

对于订单具有紧交货期限且以最大化完工总收益为目标的占线订单排序问题,Woeginger提出了完工收益与订单长度满足D-收益函数的模型,并给出了竞争比为4的最优确定性策略.针对该模型设计了竞争比为2的一个简单随机策略,该结论改进了Epstein和Levin(2008)的竞争比2.455 4.     

限制信息条件下基于时间窗的占线装-卸货问题及其竞争分析

提出并研究限制信息条件下基于时间窗的占线装一卸货问题。客户在提出服务请求时只指定需要承运的货物的装载地，而没有提供目的地信息，服务车只有在到达装载地之后才知道目的地的具体位置，如现实中的出租车调度和电梯调度等问题。就两种度量空间对限制信息条件下带时间窗的占线装一卸货问题进行了分析，分别给出了两种竞争策略及其竞争比结果，并得到了针对该问题的任何确定型算法的竞争比下界。     

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

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

带预期的占线周期性折扣租赁策略

在雪橇租赁模型基础上,考虑占线决策者还可以以T天为周期进行租赁,租赁价格具有一定折扣的租赁选择.给出了这种租赁模型下的确定性竞争策略,并证明其具有最优竞争比.进一步建立了带预期的占线租赁模型,针对租赁者的不同预期设计策略并分析其竞争性能.     

贪婪策略在占线订单加工问题中的竞争分析

根据实际生产中订单收益随加工长度变化的一般规律,建立了占线订单加工模型,构建一种贪婪策略并分析它在本模型中的竞争性能.具体证明它在中断订单有、无惩罚两种情形下的竞争比,并讨论了模型中收益函数的参数对竞争比结果的影响.     

基于凸情形下在线设备更新问题的竞争分析

市场以在线的方式给出新设备,决策者必须决定是否更新现有的设备,并确定何时更新？即在已知现在和过去的设备信息和订单信息而对未来信息一无所知情况下,决策如何更新设备完成陆续达到的订单需求.优化目标是使设备更新投资成本与设备运行成本总和最小.首先讨论了离线设备更新问题, 给出了两种算法并分析了算法复杂度.其后, 讨论了凸情形下在线设备更新问题, 给出了临界值策略,得出了竞争比为6, 证明该策略要优于原有的策略.     

带学习效应的二级易变质产品供应链的最优策略研究

研究了由一个制造商和一个分销商组成的易变质产品二级供应链的最优生产与订购策略. 有限时期内,上游制造商采取按订单生产的方式应对下游分销商的需求, 制造商生产过程以及分销商订购过程具有学习效应, 对此建立二级供应链系统决策问题的数学模型. 目标是要确定使得系统总成本最低的决策变量, 包括生产量, 订购次数以及订购时间. 通过分析系统的成本结构,利用将订购次数松弛为连续变量的技巧, 证明了系统最优策略的存在性和唯一性, 给出了最优策略的求解方法. 最后通过应用实例进行了验证.     

占线中心选址问题竞争比的下界

对占线中心选址问题的竞争比进行了研究。对度量空间占线中心选址问题，本文证明该问题的下界是2-（n-√n^2-3n＋3/n-1），其中n为空间点的个数，该结果要优于已有的结果2-（2/n-1）.对一般空间上的占线中心选址问题，本文证明了竞争比的下界是（（n-2）△＋√（n-2）^2△^2＋4（n-2））/2（n-1）,其中△是所给空间最大的相对距离，并证明一般空间上的占线中心选址问题不存在常数竞争算法。     

可退货再销售商品的占线报童问题

基于在网络销售渠道中,很多顾客会发生退货行为,且如果退回的商品是完好的则可以再次进行销售这一背景,研究允许退货再销售条件下的占线报童问题。建立了占线决策模型,并根据问题的特征修正了已有的竞争比概念,给出了占线零售商相应的最优竞争策略,证明了最优严格竞争测度比。     

住房租赁占线算法及其竞争策略

研究一个住房租赁占线算法问题.不同于Karp[1]研究的雪橇,住房具有价值昂贵、使用寿命长的特征,因此模型引入＂买卖存在交易成本,价格高于交易成本＂的假设,描述一个可二手交易的住房租赁问题的占线决策过程.在该过程中,理性的决策者在住房使用结束后会权衡住房市值与交易成本变卖住房以降低居住成本.我们对这一问题展开了竞争分析,获得了一个反映交易环境、行业竞争水平与占线策略及竞争比的等式.等式说明在对未来需求信息了解相同的情况下,交易市场、行业竞争水平等环境因素决定占线策略及竞争比,模型对类似环境条件下租赁问题的决策具有借鉴意义.     

随机生产服务系统最优服务能力分配策略

针对由生产设施和服务中心组成的柔性生产服务系统,研究服务能力在不同订单之间的分配问题。生产设施生产两类产品,服务中心基于对应的产品为两类顾客提供不同的服务,服务每个顾客订单需要消耗对应的产品。生产和服务时间均服从指数分布,需求过程为泊松过程。因服务能力有限,管理者在任何时刻须决定将服务能力分配给哪一类订单。将系统的最优服务能力分配问题转化为一个连续时间马尔科夫决策过程。通过解析证明和分析,发现该随机系统的最优服务策略为形式非常简洁的指标型优先权服务策略,但又不同于传统服务系统的最优服务策略。最后,分别对最优服务策略与分散决策下的服务策略、相反优先权服务策略以及动态协同下的服务策略进行对比,说明了最优服务能力分配策略的优越性和有效性。     

共享平台占线任务分配的结构性下界

共享平台任务分配过程中,经常会遇到如下的情形:在用户未来需求任务序列(到达时刻、开始时刻和持续时间等)未知的条件下,决策者需要决定如何将当前需求合理分配给现有服务器使得平台收益最大.平台上服务器具有数量限制,同时要求用户需求一旦被分配就不可更改.以往研究建立的模型一般都是针对静态任务分配而言的,但实际需要的是满足上述约束的动态任务分配模型.以最大化共享平台收益为目标建立了占线共享平台任务分配模型,其中收益不仅包含了抽成比例,而且包含了固定收益.利用Yao原则给出了问题的竞争比的下界结果,该下界不需要任何复杂性假设条件,因此,是结构性下界.     

共享平台占线任务分配的结构性下界

共享平台任务分配过程中,经常会遇到如下的情形:在用户未来需求任务序列(到达时刻、开始时刻和持续时间等)未知的条件下,决策者需要决定如何将当前需求合理分配给现有服务器使得平台收益最大.平台上服务器具有数量限制,同时要求用户需求一旦被分配就不可更改.以往研究建立的模型一般都是针对静态任务分配而言的,但实际需要的是满足上述约束的动态任务分配模型.以最大化共享平台收益为目标建立了占线共享平台任务分配模型,其中收益不仅包含了抽成比例,而且包含了固定收益.利用Yao原则给出了问题的竞争比的下界结果,该下界不需要任何复杂性假设条件,因此,是结构性下界.