多种任务加工表局内问题的竞争算法

介绍了局内问题的竞争算法，给出了多种任务加工表局内问题的竞争算法，估计了竞争率，并且证明了２－１ｍ是该竞争算法竞争率的最好上界，其中ｍ是机器台数．

局内问题算法的近似度

本文对局内问题算法给出了几个评估标准,对装箱问题设计了绝对性能比至多为2的局内问题算法,并用局内问题算法的近似度考察了 K 车服务问题。

随机旅行时间局内车辆路径问题的模型及其算法

人们在生活中会经常遇到随机旅行时间的局内车辆路径问题,如现实物流配送中的交通堵塞现象。文章在Laporte等的研究基础上,提出了一个考虑堵塞点动态产生、一个个遇到,堵塞时间为随机变量的模型,并构造了求解该模型的算法。

局内状态下的进货管理问题及其竞争分析

局内进货管理问题是指在未来商品的需求不确定,对未来不作预测的情况下如何决策什么时候及购进多少货物的问题。如果我们用πODPT表示局外问题的最优解,πAD表示局内算法A的最优解,那么竞争比可以表示为sup(πODPT/πAD),其中D表示任意的需求序列。决策者的目标是使得竞争比尽可能的最小。本文首先建立了一个简化的局内库存管理模型,在知道M和m(未来需求最大值和最小值)基础上设计了两种局内策略FNA和PDBA。讨论并证明了对于固定购买数量的竞争策略,我们给出的FNA策略具有最优的竞争比。而后分析了策略PDBA在需求满足各种不同情况下的竞争比。

带时间窗的局内开放式车调度问题的竞争分析

对于带时间窗的局内车辆调度问题,以往文献的研究都是关于k=1的单车调度,其开放式情形下最好的竞争比为4。针对该问题本文进行了开放式情形下多辆车(k≥2)调度的研究分析,设计了解决该问题的竞争算法,并证明了其竞争比为3.5。同时本文分析了该问题的一种特殊情形——单车调度问题,可证明其竞争比为3,优于已有结果。

局内电梯调度问题与竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案 (即最优解 ) ,其最优性在条件发生变化时就会失去。局内问题与竞争算法则是针对特定的优化问题来研究这样的方法 ,它在变化因素的每一个特例中都能给出一个方案 ,使得这一方案所得到的解离最优方案给出的解总在一定的比例之内。本文首先提出了局内电梯调度问题 ,设计了解决该问题的两个不同的竞争算法 ,并证明了这两个竞争算法的竞争比分别为k+2 和n-k +1,其中k为电梯的个数 ,n为楼层数。

局内车辆选线问题的比较策略及其竞争比分析

对现实物流配送中遇到的无法预测的线路堵塞问题,建立了具有堵塞点的局内车辆选线问题的数学模型,并分别介绍了局内运输车辆调度的贪婪策略和复位策略.在全面分析了这2种基本策略在竞争性能上的优劣之后,给出了比较策略及其算法模型.最后,讨论了该策略的竞争性能.结果表明,比较策略实现了对局内运输车辆的优化调度.

局内车辆选线问题和竞争策略分析

将现实物流配送中所遇到的问题抽象为一个局内车辆选线问题,考虑堵塞点动态产生、一个个遇到的情况下的车辆调度方案.经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解),在条件发生变化时就会失去其最优性.而论文所考虑的竞争算法能使得调度方案对于变化因素的每一个特例得到的解离最优方案给出的解总在一定范围之内.不仅设计了解决局内车辆选线问题的竞争算法:贪婪策略和复位策略,分析了不同情况下算法各自的竞争比,而且给出了此问题的竞争比下界.

基于特殊路径的局内车辆路径问题混合策略研究

针对运输途中遇到的某一或一系列无法预知的堵塞事件对决策者路径选择策略的影响,考虑堵塞只发生在一条特殊路径上且可恢复的情况,采用局内竞争分析的思想,建立了局内车辆路径问题的数学模型,对车辆到达堵塞点时堵塞恢复时间未知这一情形下的路径选择问题,提出了两种混合策略,给出了相应的竞争比,并对其竞争性能进行了理论分析。

局内经济决策问题的竞争分析——一种新的经济数学工具

基于优化领域的热点研究方向之一的局内问题与竞争策略理论 ,本文提出了局内经济决策问题的一系列概念 ,说明了处理局内经济决策问题的竞争策略和传统方法的区别以及后者的缺陷 .构建了利用局内问题及其竞争策略研究局内经济决策问题的理论框架 。

限制图上的局内出租车调度与竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案（即最优解），其最优性在条件发生变化时就会失去．局内问题与竞争算法则是针对特定的优化问题来研究这样的方法，它在变化因素的每一个特例中都能给出一个方案，使得这一方案所得到的解离最优方案给出的解总在一定的比例之内．本文应用复位策略给出限制图上局内ｋ 出租车调度问题竞争比为１＋ （ｎ－ ｋ）λ的竞争算法．

局内出租车调度与竞争算法

应用复位策略给出了局内ｋ出租车调度问题的竞争算法．

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

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

物流配送管理中的路径优化问题研究

经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解),其最优性在条件发生变化时就会失去其最优性。本文提出的局内最短路问题,就是在已知条件不断变化的条件下,如何来快速的计算出此时的最优路径,文章设计了解决该问题的一个逆向标号算法,将它与传统算法进行了比较和分析,并针对实际中的物流配送管理中路径优化问题,按照不同的算法分别进行了详细的阐述与分析。

直线上的k-配送小车调度问题与竞争策略

提出和研究了直线上的局内k-配送小车调度问题。应用复位策略,竞争比为k+2;设计了解决该问题的竞争算法,证明采用局部双覆盖策略LocalDoubleCoverageStrategy(LDCS)的竞争比为k.最后,简单地分析了该问题的一个特例——局内电梯调度问题,得出了比较结果。

局内配送车调度及其竞争算法

经典的优化理论大多是在已知条件不变的基础上给出最优方案(即最优解),其最优性在条件发生变化时就会失去.局内问题与竞争算法则是针对特定的优化问题提出一种策略,对已知条件变化的每一个特例都能给出一个方案,使得该方案的解离最优方案的解总在一定的比例之内.针对在一个有限网络上建立了s个配送中心,并且有k辆配送车进行服务的局内配送车问题,在时间目标函数下给出了当配送中心、配送车和需求点个数变化时的3种竞争算法.

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

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

价格连续型局内设备赁购问题的竞争分析

基于局内算法分析领域中的On-line Ski问题,提出了局内设备赁购决策问题.建立了价格连续型的该问题的数学模型,针对购价恒定的情形和一般情形分别设计了B价赁购策略和赁购平衡策略(Renting-Buying Balance Strategy),给出了相应的竞争比,并进行了理论证明.得到了价格连续型问题的竞争比下限,并给出理论证明.讨论了所得结果在现实经济管理活动中的应用,并指出了进一步的研究方向.

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

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

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

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