同型平行机上在线排序问题的近似算法

本文研究同型平行机上的在线排序问题。通过平移工件的到达时间，提出了一类在线确定型算法SSPT。对目标为总完工时间的情形，证明了该算法竞争比不了于2且不超过(4-1/m)，对目标为加工总长的情形，该算法的竞争比的上界为(3-1/m)。     

A Review of On-Line Machine Scheduling:Algorithms and Competitiveness

在过去的十年里，在线算法的研究吸引了广泛的兴趣．本文对在排序和时间表问题中的各种有效的在线算法以及它们的竞争度作一综述．     

带有拒绝的单机和同型机排序问题

研究了带有拒绝的单机和同型机排序问题. 对于单机情形, 工件的惩罚费用是对应加工时间的\alpha倍.如果工件有到达时间, 目标为最小化时间表长与惩罚费用之和, 证明了这个问题是可解的.如果所有工件在零时刻到达, 目标为最小化总完工时间与惩罚费用之和, 也证明了该问题是可解的.对于同型机排序问题, 研究了工件分两批在线实时到达的情形, 目标为最小化时间表长与惩罚费用之和.针对机器台数2和m, 分别给出了竞争比为2和4-2/m的在线算法.     

折扣加权总完工时间问题的半在线排序算法

讨论到达时间任意,加工时间具有上下限约束,目标函数为带折扣的加权总完工时间的单机排序问题1|rj,Pmin≤Pj≤Pmax|∑ωj(1-e-βCj),给出了此问题在任意半在线算法下的竞争比下界,并提出了求解此问题的一种半在线算法D-αWDSPT,通过分析算法竞争比说明该算法是一种近似最优算法.同时指出,算法在问题的三种特殊情况下是最优算法.第一种问题是最小加工时间P→0,第二种问题是折扣因子β→0,第三种问题是工件加工时间相同Pmin=Pmax     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+\Delta（t）]$内到达工件的信息,这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长,其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

单机上带有可变前瞻区间的分批在线排序问题

本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$（t,t+\Delta（t）]$内到达工件的信息,这里前瞻区间的长度$\Delta（t）=\beta p_{\max}（t）$并非定长,其中$p_{\max}（t）$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in（0,1）$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。     

带核箱覆盖问题的在线算法

经典的箱覆盖问题是组合优化中一个著名的问题,并且得到了广泛的研究．本文主要讨论带核元的箱覆盖问题的复杂性和在线条件下的算法．指出了带核的箱覆盖问题是强ＮＰ－ｈａｒｄ的．给出了在不同的在线条件下可行算法渐近比的上界,指出仅在条件三下才存在渐近比好于０的在线算法,并给出了在此条件下一个渐近比为１／２的最好的在线算法。     

具有优先权和准备时间的自由作业时间表问题

研究具有优先权和准备时间的自由作业时间表问题 ,在稠密时间表的情况下 ,给出一种启发式算法 ,猜想该算法的紧界是 2 -2 /( m +1 ) ,其中 m是机器台数 .对于只有两台机器的情况 ,即当 m =2 时 ,证明该算法的最坏性能比是 4/3 ,并通过实例证明上界是紧的 .     

收益约束下在线租赁最小风险策略竞争分析

在线算法是研究信息不确定决策问题的一种新工具。应用在线算法研究金融租赁问题(在线租赁)是近年来国内外的一个研究热点。本文在前人研究基础上,讨论了给定收益约束下在线租赁最小风险策略,完善了在线租赁的风险收益竞争分析。同时我们也把基本的在线租赁扩展为可退货在线租赁问题,并进一步讨论了可退货在线租赁问题的风险最小策略。本文结果对在线租赁研究具有重要意义。     

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

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

极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.     

流水车间作业排序问题蚁群算法研究

本文运用蚁群算法研究辨台处理机、目标函数为时间表长最小的同顺序排列流水车间作业排序问题，设计出解决该问题的算法步骤与流程。最后，通过仿真比较该算法与解决该问题的其它启发式算法性能，计算效果比较满意。     

在线学习方法综述:汤普森抽样和其他方法

本文尝试对在线学习领域的最新研究成果、相关主要理论和算法进行综述.在线学习的内容非常广博,本文希望能够为读者介绍其中一些基本的算法和想法,从最经典的理论模型和算法设计开始,对在线学习的发展情况作一个一般性的介绍.首先,以经典的在线优化模型——多摇臂赌博机问题为例,引入了汤普森抽样算法和信心上界算法,分析、展示了它们的基本思路和最新成果,并进一步讨论了汤普森抽样算法在更复杂的在线学习问题中的变式和应用.本文同时对在线凸优化算法做了初步探讨,它也是解决多摇臂赌博机问题和其他许多在线学习的应用问题时一种强有力的工具.     

已知工件最大加工时间的两台同类机半在线问题

考虑已知工件最大加工时间的两台同类机半在线问题．机器M1,M2的速度分别为s1=1,s2=s(s≥1),工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载．此模型简记为Q2／known largest job／Cmax．作者给出了Qmax2算法并证明此算法的竞争比为2(s 1)/s 2(1≤s≤2)和(s 1)/s(s>2),且是紧的．同时给出Q2／known largest job／Cmax问题的一个下界,并且证明Qmax2算法的竞争比与最优算法竞争比之差不大于1/4.     

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

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

几类任务到达时间受资源约束的单机排序问题

本研究了任务到达时间受资源影响的，与时间表长有关的几个问题。对问题1|rj=bj-ajuj,∑j=1^nju≤U|Cmax的一种特殊情况给出了求任务的最优排序的算法，对问题1|rj=fj(uj),pj=p,Cmax≤C|∑j=1^nuj给出了最优算法；还给出了问题1|rj=fj(uj)|∑j=1^nujΛCmax的一个算法。     

带折扣因子的单机干扰管理研究

针对可预见的干扰管理问题,考虑单机环境下,加权折扣最短加工时间优先(WDSPT)序为原目标的最优加工次序,研究了如何对初始加工时间表进行修改。在干扰事件影响下,初始加工时间表将不再是最优,甚至不再可行。和大多数重排序研究不同,构建了同时考虑原目标和由干扰事件造成的扰动目标的重排序模型,并基于理想点法提出一种动态规划算法来求解所建模型中的双目标排序问题。最后通过一个数值算例来说明该重调度模型对于求解带折扣因子的单机干扰管理问题是有效的。     

带恶化和综合学习效应的成组排序问题研究

本文研究了成组技术下带恶化和综合学习效应的排序问题,工件的加工时间带综合学习效应。对最小化时间表长问题,我们给出了多项式算法,并且证明了带一致关系的最小化总完工时间问题也是多项式可解的。     

平行机在线排序综述

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

带学习效应的两台平行机时间表长问题

研究机器带学习效应, 目标函数为时间表长的两台平行机排序问题, 问题是NP-难的. 首先建立了求解该问题最优解的整数规划模型. 其次, 基于模拟退火算法给出了该问题的近似算法SA, 并证明了该算法依概率1 全局收敛到最优解. 最后, 通过数值模拟对所提出的算法进行了性能分析. 数值模拟结果表明, 近似算法SA可以达到最优值的99%, 准确度高, 算法较有效.