We use cookies to improve your experience with our site.

两个特殊的在线设备更新问题的竞争分析

Competitive Analysis of Two Special Online Device Replacement Problems

  • 摘要: 设备更新问题在运筹学和最优化领域一直是热点研究方向。设备更新决策分析问题一般以设备的年经营成本(或年总费用)最低来确定设备更新时机,从一系列备选方案种进行决策分析来选择更新方式,而且在比较方案的优劣是往往以最低的设备年经营成本(或年总费用)为决策目标。以往对该问题的研究都是围绕着离线问题展开的。所谓离线问题就是在输入完全已知的情况下所提出的问题,需要寻求一种优化算法来解决该问题的成本最小或利润最大。而在线问题中,输入是事先不完全已知的,即在线问题就是一类输入的到来和输出的产生都必须是以在线方式进行的最优化问题。与离线问题相比较而言,在线问题所固有的复杂性在于每一个在线输出都会影响到全局解。Y.Azar等学者研究了离散时间的在线设备更新问题。该问题可以描述为假设一个专门从事来料加工的工厂,陆续接到国外的生产订单,因此工厂投资购买了生产设备加工订单,之后市场上又不断推出新的设备和新的生产订单。工厂可以选择采用原有的设备也可以购买新设备来完成新订单,目标函数是使得完成生产订单的总费用最小,包括投资新设备的成本和用该设备从事生产产品的运行成本。由于只知道当前的订单和设备信息而对未来的信息一无所知,因此决策人必须以在线的方式来决策是否购买新设备以及何时购买。Damaschke从时间连续型的角度建立了凸情形下的两类特殊情形的投资更新模型,对于设备的购买价格相等情形下的竞争比下界为1.618和一个简单算法的竞争比2。MacCrimmon 和Wehrung给出了一个研究风险的基本模型,在他们的模型中有两种行为:得到确定结果的无风险行为和有可能产生收益或损失的风险行为,且风险行为产生的结果是不确定的。对于占线人来说,选择的行为就是进行投资的方案,而结果就是得到的竞争比。本文在上述研究的基础上研究了两个特殊的在线设备更新问题。首先对设备价格相等的在线设备更新问题,通过证明下界的平均分析法将Damaschke给出竞争比下界由1.618改善到2,由于上下界重合说明该下界不能改善。然后提出了两阶段的设备更新问题,首先证明了该问题的竞争比下界为 ,其后给出了一个最优的竞争策略。并且将市场利率引入该模型中,在很多经济模型中这是一个合理的讨论因素。在此基础上又引入风险补偿因素,结果说明风险补偿的引入可以较好的改善该问题的竞争比性能,并给出了相应的数值分析。

     

    Abstract: When anew investment opportunity of purchasing a new deviceoccurs, the investors must decide whether or not and when to buy this device in anonline fashion. That is, the online player must make an investment decision whileneither future demand for orders nor future investment opportunities are known. Thisproblem which generalizes the basic leasing problem has been introduced by Azar \itet al., and then two special cases have been studied by Damaschke. In the so-calledequal prices model a 2-competitive algorithm is devised and a 1.618 lowerbound is given. Here we make use of an averaging technique and obtain a better tightlower bound of 2, in other words, this lower bound cannot be improved.Furthermore, another special case which only considerstwo-stage device replacement is studied in this paper.Accounting for the interest rate is an essential featureof any reasonable financial model. Therefore, we explorethe two-stage model with and without the interest raterespectively. In addition, we introduce the risk-rewardmodel to analyze this problem and improve the competitive ratio performance.

     

/

返回文章
返回