带复合信息的三台平行机半在线排序问题

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

平行机半在线排序问题研究(Ⅰ)

对半在线平行机排序问题的研究进展作了详细综述和进一步探讨。文章给出半在线排序问题的背景、定义、分类和求解。介绍它们定义和在不同机器环境和目标函数下半在线排序问题分类，以及第一类半在线模型的近似算法的设计及其竞争比分析。     

预知工件大小上界的平行机排序问题

平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡,大型计算中的并行计算,柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:C_(max)(极小化机器最大负载makespan)和C_(min)(极大化机器最小负载).在不同的目标下,针对m台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.     

带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

平行机在线排序综述

平行机排序是一类重要的组合优化问题,列表在线排序是在线问题研究形成和发展的重要推手,也是成果最为丰富的在线问题之一.本文回顾以最大完工时间为目标的在线和半在线排序问题的最新进展,总结工件可拒绝、机器可增加及目标为机器负载的Lp范数等3类复杂目标在线排序问题的主要结果,介绍竞争比近似方案、带建议的在线算法和多样化算法性能指标等3个在线排序新课题.     

预知两种信息带准备时间的两台同型机半在线排序

研究了P2,r_j/decr,opt/Cmax问题,即预知工件大小非增排列decr和最优目标值opt的两台同型机的带准备时间的半在线问题,并给出了竞争比为7/6的半在线算法.     

总服务时间已知的两台同类机调度问题

研究调度问题上机器服务总时间已知的问题,针对机器的速度和准备时间不同,分析研究带机器准备时间的服务总时间已知的两台同类机半在线调度优化问题.目标为最小化最大机器服务时间,对于机器服务所有工件的时间已知的半在线情形,给出了人一个竞争比不超过2(s+1)/(2s+1)的半在线算法,其中s_i为机器速度,s_1=1,s_2=s>1.     

两台可拒绝同型机半在线排序问题

本文讨论一个两台可拒绝同型机半在线排序问题.当工件到达时,可以被拒绝,但要付出一定的罚值,也可以被接收加工,消耗一定的加工时间.其目标是要使所有加工工件生成的makespan和被拒绝工件的总罚值之和最小.加工不允许中断.进一步,机器带有两个并行处理子系统,可以提供两种排序方案,最后选取较好的一种.这是第一个在可拒绝同型机排序模型中使用半在线信息,我们设计出一个近似算法,其竞争比为3/2,另外又给出一个√3+1/2≈1.366的下界.     

在线计算中的几个未解问题(英文)

讨论组合优化中的一个迅速发展的领域──在线计算，选出几个典型的未解问题进行方法介绍．     

带机器准备时间的机器覆盖问题的在线、半在线算法

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.     

有使用限制的二台机器流水作业问题

本文研究了机器有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断。我们讨论了两台机器上均有使用限制离线问题的可近似情形,并给出了性能比为3/2的近似算法。同时我们还考虑了在第二台机器上存在一个不可用时间段情况下的半在线问题,给出了一个竞争比为3/2的半在线算法。     

半变系数模型PLS估计的渐近正态性

半变系数模型在统计建模中具有重要的应用．最近几年，人们提出了许多方法来估计其常系数和函数系数，但是估计的渐近性质还没有被系统的研究．本文介绍了半变系数模型的PLS估计，在Fan和Huang对常系数渐近性质研究的基础上，给出了函数系数的渐近正态性。     

在线多租赁选择问题的最优竞争策略

在线算法与竞争分析是研究信息不确定决策问题的一种新工具,应用该方法研究在线租赁问题是近年来国内外的一个研究热点。传统的在线租赁问题以经典的"雪橇租赁模型"为基础,考虑在线决策者可以选择购买或按单位时间租赁的方式来使用设备。然而现实租赁市场(比如汽车租赁,房屋租赁)往往提供多种租赁方式供在线决策者选择,除了按单位时间进行租赁,通常可以以一个较优惠的价格租赁多个单位时间。在这种现实背景下,本文建立了多种租赁形式下的在线租赁模型,给出了这种租赁模型下的确定性竞争策略,并证明该策略具有最优竞争比。     

两样本半参数模型的经验欧氏似然估计

在本文中，我们证明了两样本半参数模型的经验欧氏似然估计的相合性和渐近正态性，也证明了两样本半参数模型的经验欧氏似然比统计量的渐近x2分布性，最后给出了两个例子．     

基于相近原则的半指导直推学习机及其增量算法

半指导问题是近来机器学习研究中的备受关注一个重要内容．本文以满足“在输入空间中相近的对象其输出也相近”这一源于直观事实的原则(相近原则)去解决半指导学习问题,给出在这个原则下的一个一般的直接推理方法—基于相近原则的半指导问题直推学习机,得到了这个问题的解析解及迭代算法,用模式分类实例验证该方法的有效性,并给出适于在线处理的增量学习算法,这些增量算法尤其还适于新增了有指导的信息的场合．     

P‖Cmin随机算法研究

本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。     

一类两参数半线性奇摄动问题解的渐近性态

本文研究了一类两参数半线性奇摄动问题的基本模型.利用奇摄动方法,对该问题解的结构在两个小参数相互关联的三种不同情形下作了讨论.得到了该问题在三种不同情形下的渐近解并证明了在三种情形下解的结构与渐近性态.     

环形路网上带有服务时长的在线TSP问题

为了提高快递揽件的时效性,需要对快递车辆进行有效调度。针对环形路网上服务时长以及需求无法预知的揽件问题,本文提出了以服务总时间尽可能短为目标的环形路网上带有服务时长的在线旅行商问题。用在线算法分析了此问题竞争比的下界,设计了两个在线算法并分析了各自的竞争比,结果表明服务时长可以改善在线车的性能。最后通过简单算例对两个算法进行说明,本文研究结论可以为环形路网上的快递车辆实时调度提供指导。