具有预知信息的集装箱码头泊位与岸桥联合调度在线模型

探讨了预知服务需求信息能力下的集装箱码头泊位与岸桥联合调度 over-list 在线模型. 在每个船舶服务请求释放时, 决策者预知后续 k(k \geq 2)个请求的信息,目标为最小化所有请求的最大完工时间. 针对由3个离散泊位组成的混合型泊位与4个岸桥, 以及只有大小两种服务请求的情形, 给出了预知任意 k \geq 2个请求下的竞争比下界; 同时, 对于k=2的特定情形, 给出了具有最优竞争比7/6 的在线策略. 数值实验进一步表明了所设计策略的良好执行性能.     

工件按加工长度不增序到达的最小化最大流程在线分批排序

研究单处理机工件按加工长度不增顺序到达的在线分批排序问题．工件按时在线到达,目标是最小化最大流程．流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间．对于批容量有界的情形,给出了一个竞争比为1＋√5/2的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为√2的最好可能的在线算法．     

基于最优出力分配的梯级总出力调度图优化

为提高梯级水库调度管理的科学水平和水资源利用效率,分析了蓄供水判别式法运用于梯级水库调度所存在的三点不足,以梯级调度期总发电量最大为目标,构建了基于梯级总出力调度图优化和时段内最优出力分配的双层嵌套模型,并给出了基于逐步收索方式和逐步优化算法的模型求解流程。以我国西南某流域梯级水库为实例进行计算,其结果与常规方案相比,不仅年发电量有所提高,保证出力和保证率也有较大程度的提升,验证了所建模型的合理性。     

无限可分商品在线反向拍卖的风险策略研究

对网络环境下一个买家多个卖家的反向拍卖,研究了供应商在不同时间到达并投标而采购商接到每个投标后需要立即做出决策的在线反向拍卖的风险策略。对于无限可分商品,在资金一定前提下,首先对采购商无风险行为情形给出了基于标价上涨威胁的在线反向拍卖策略,通过竞争分析得到了其最优竞争比及整体需要曲线;其次引入采购商的风险容忍度概念,建立了激励相容在线反向拍卖的风险回报框架,并对风险忍耐策略进行了竞争分析。     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

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

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

工件满足一致性的同类机在线分批排序问题

研究了工件满足一致性,批容量无界的两台同类机在线分批排序问题,目标为极小化工件的最大完工时间和极小化工件的最大流程时间,三元素法分别表示为Q_2|r_ir_j?p_i≤p_j,B=∞, on-line|C_(max),Q_2|r_ir_j?p_i≥p_j,B=∞, on-line|F_(max).不失一般性,假设第一台机器速度为1,第二台机器速度为s,s≥1.对于上述两类问题设计了一个在线算法,并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α,这里α为α~2+sα-1=0的正根,特别地,当s=1时,该算法的竞争比不超过1.618.对第二类排序问题,该在线算法的竞争比不超过1+1/α.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.     

Online C-benevolent job scheduling on multiple machines

We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized \((2+2/{\hbox {m}})\)-competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.     

平行机上带有前瞻区间的不相容工件组在线排序问题

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.     

Online batch scheduling with kind release times and incompatible families to minimize makespan

This paper studies online scheduling of jobs with incompatible families on a single unbounded batch machine under the KRT environment, where jobs arrive over time and “KRT” means that in the online setting no jobs can be released when the machine is busy. The goal is to determine a feasible schedule to minimize the makespan. We provide a best online algorithm with a competitive ratio of \(1+\frac{\sqrt{f^{2}-f+1}-1}{f}\), where f is the number of job families.     

基于高斯分布的在线采购机制设计及竞争分析

依附于互联网电子商务的在线采购拍卖交易, 对传统的贝叶斯离线拍卖理论提出新的挑战, 因为面对不同时间点的投标, 采购电商必须即可决策出是否中标以及购买价格。鉴于此, 对于诸如石油、煤、粮食等无限可分商品的电子采购, 本文基于投标具有高斯分布特征设计了一种激励相容的在线采购策略, 演绎出在线采购的数学模型, 利用Runge-Kutta数值算法, 通过Matlab编程求解出采购电商在线定价策略的需求曲线及其对应的竞争比, 最后, 利用数值模拟, 将在线采购机制策略与纯竞争分析得到的在线采购策略比较, 结果显示利用了高斯分布信息的在线采购策略的竞争性能由于利用了投标的统计信息而得到了提高。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

具有两个不相容工件族单位工件的有界分批在线排序问题

研究具有两个不相容工件族单位工件单机有界平行分批的在线排序问题.工件按时在线到达,目标是最小化最大完工时间.在有界平行分批排序中,容量有限制机器最多可将b个工件形成一批同时加工,每个工件及每一批的加工时间为1.不相容工件族是指来自不同工件组的工件不能放在同一批加工.对该问题提供了一个竞争比为√17+3/4的最好可能的在线算法.