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

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

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

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

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

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

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

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

视频流点播代理缓存管理新策略

随着视频流点播应用在Internet上的流行,服务器和骨干网络的带宽越来越成为了视频流点播发展的主要制约因素.为此,根据视频点播的特点和代理服务器除了能在服务器与客户端之间进行通信中继以外,还可缓存部分视频内容以直接满足客户请求的事实,提出了一个基于均匀分段的代理缓存管理策略以缓解视频流点播系统对服务器及骨干网络带宽的需求,并详细介绍了代理缓存管理策略的具体操作.理论分析表明文章提出的代理缓存管理策略能大大的减少系统对骨干网络带宽的需求,并能为客户端提供理论零延时服务.实验结果证明所提缓存管理策略明显优于现有的基于完全缓存或前缀缓存的代理缓存策略.     

MTO模式下占线生产问题的竞争比下界EI北大核心CSCDCSSCI

研究的是订单需求信息不确定条件下的按订单生产(make-to-order,MTO)模式企业的生产决策问题.这类企业单批产品的固定启动生产成本较高,企业允许延期交货,但需要承受延期惩罚费用.因此本文研究在需求订单到达序列信息不确定的条件下,决策怎么安排生产使得总固定启动生产费用和延期费用最优的生产决策问题.考虑了占线生产模型,首先证明该问题的竞争比下界是3.随后受证明的启发,研究仅针对两类产品的问题,给出了一个新的占线生产策略并证明竞争比为3,因此说明所做的下界分析是紧的,同时证明了所给出针对两类产品的问题的占线策略是最优的.     

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

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

一条路上的在线货车调度及其竞争分析

一条路上的货车调度问题是线上的在线服务器问题的推广.决策者必须以在线方式做出决策,即已知现在和过去的信息而对未来一无所知情况下决策如何调度货车完成服务需求.优化目标是使竞争比最小.本文分空载和实载两种情行进行了讨论,对每种情形分别提出两种不同的竞争策略,得到了相应的竞争比;最后,对本文中给出的问题P3的两种竞争算法作了比较并得出了结果.     

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

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

基于Web Service的作战模型共享体系的研究与实现

为保证联合作战训练系统开发过程中,充分利用现有模型资源,避免重复建设,提出了基于Web Service的作战模型共享体系.首先,介绍了模型服务的描述和获取制,以及模型服务器的总体设计和实现方法.然后,设计了单模型服务器和多模型服务器的调用方法.最后,针对多模型服务器调用过程中存在的传输数据量大和时空一致性问题,提出了基于拟合的外推算法,实验证明,基于Web Service的作战模型共享体系是可行的,所设计的外推方法可较好解决问题.     

The complexity and on-line algorithm for automated storage and retrieval system with stacker cranes on one rail

This paper considers an on-line scheduling and routing problem concerning the automated storage and retrieval system from tobacco industry. In this problem, stacker cranes run on one common rail between two racks. Multiple input/output-points are located at the bottom of the racks. The stacker cranes transport bins between the input/output-points and cells on the racks to complete requests generated over time. Each request should be accomplished within its response time. The objective is to minimize the time by which all the generated requests are completed. Under a given physical layout, the authors study the complexity of the problem and design on-line algorithms for both one-stacker-crane model and two-stacker-crane model. The algorithms are validated by instances and numerical simulations.     

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

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

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

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

基于最短时间碎片的在线生产调度算法研究

针对订单型企业的在线生产调度问题,文章通过统计每个设备上允许插入工序的时间区间,提出了基于最短时间碎片的启发式在线生产调度算法.该算法的主要思路是将工序的先后约束关系和在同一设备上的先后执行关系统一建模为无圈有向图,从而依据最短时间碎片将新订单的调度过程转化为在有向图中添加顶点和有向边的过程.仿真实验结果表明该算法可以在保证订单交付期的前提下实现排产任务,并尽可能少地变更已排产工序在设备上的相对位置;在订单频繁到达时,调度的设备利用率较高,达到了约94%;此外,算法运行较快,适用于较大规模在线生产调度问题的求解.     

基于卡尔曼滤波的在线量子态估计优化算法

针对连续弱测量中存在高斯测量噪声的问题, 提出一种基于卡尔曼滤波的在线量子状态估计的预测-修正-投影优化算法。首先,在常规在线卡尔曼滤波算法预测状态时间更新和估计状态测量更新的基础上, 通过增加对量子态的约束条件, 将其应用于在线的量子状态估计中, 将量子态在线估计问题转化为一个带有量子态约束条件的卡尔曼滤波优化问题。其次,通过将待优化问题的求解分解成两个凸优化子问题,一个是基于在线卡尔曼滤波算法求解无约束条件下的量子测量更新问题, 另一个是利用量子约束条件信息, 通过求解矩阵投影问题来获得估计状态。最后,将所提算法应用到4量子位系统状态的在线估计数值实验中, 进行了性能对比实验。实验结果表明, 所提算法具有更优的在线状态估计精度, 并且能够以更少的采样次数和耗时, 实现较高精度的量子状态在线估计。     

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

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

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

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

局外k—出租车问题及其动态规划求法

局内问题及其解法在研究是优化领域研究热点之一，而有关局内问题解法的研究必将涉及相应的局外问题。提出了局外k-出租车调度问题，给出了问题的动态规划求解方法，并给出该问题的一个具体算例。同时简要地介绍了局外k-卡车调度问题的动态规划求解方法。