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

研究了已知总加工时间的两台同类机半在线问题.假设工件是分别独立地到达加工机器,并且工件的总加工时间是已知的,目标函数为极大化最小机器负载.将总加工时间标准化后,给出近似算法及其竞争比,并证明此竞争比是紧的.给出此问题竞争比的一个下界1.6180,并由此推出当两台机器的速度比为1.618 0时,算法是最优的,算法的竞争比与最优算法的竞争比之差小于0.089.     

单机等长区间的在线排序问题研究

在单机区间排序环境中定义了一种新的半在线排序模型:区间是随着时间依次到达的,区间的一切信息,如到达时间、区间长度、权重等在区间的到达时刻才可获知;已知区间实例集中区间的最大权重与最小权重之比为Δ;目标是确定一个工件允许被终端抢先的排序最大化接收区间的总权重。用对手法给出了该问题的一个下界为2,接着用组合分析法设计了该问题的一个在线算法H,并用最小反例法证明其竞争比分别为(1+(4Δ+1)1/2)/2(1≤Δ≤12时)和4(Δ>12时)。表明当Δ=2时,算法H是一个最好可能的在线算法.     

一类网上英式拍卖的保留价与起始价分析

对eBay上一类网上英式拍卖,给出了设置保留价和不设置保留价时卖方期望收入的表达式,发现顾客总人数与顾客估价的最大偏差对卖方的期望收入起互补作用,并证明了卖方的期望收入都是补偿因子的严格递增的凹函数,当顾客足够多时,无保留价拍卖最优起始价产生的期望收入与含保留价拍卖最优保留价产和的期望收入相同．     

一类工件有尺寸且分两次到达的在线分批排序

研究了工件有尺寸大小,有到达时间的在线分批排序,目标函数为工件的极大完工时间。就所有工件有2个到达时间的在线分批排序,给出算法,并证明了算法的竞争比不超过3。     

考虑运输的退化工件在线排序问题研究

本文研究了单台机器上工件具有退化效应并且需要考虑工件运输的在线排序问题.目标函数是最小化最大运输完工时间.对于这个在线排序问题,主要是设计一个有效的在线算法.首先采用对手法找到问题的下界,即设计一个坏实例,使得算法得到的目标值与离线最优目标值的比尽可能的大,之后依据下界设计给出一个在线算法.通过对手法的应用,给出问题的下界,并设计了一个竞争比为2的在线算法.     

机器无等待工件具有区间限制的两台同构并行机上批在线调度

针对两台同构并行机上的在线批调度问题,提出了使工件加工的最大完成时间最小的一个批在线列表调度算法。即工件组成不同的批,每个批中有m个工件,当每批到达等待加工时,其内部的工件加工时间才已知,且每个工件加工时间限定在某个实区间[a,b]上。在对当前批后批中工件的信息不了解的情况下,立即将其中的工件按LPT规则调度进行调度,调度过程中不允许中断。解决了算法的可使用性的度量问题,对其最坏情况进行了分析,给出了算法的最坏情况比。     

基于随机矩阵的新型频谱盲感知方法

针对传统频谱感知算法需要预先估计噪声方差且当存在噪声不确定度时,检测性能降低的特点,提出一种基于随机矩阵的改进型频谱盲感知算法(M-CMME)。该算法通过分析协方差矩阵最大特征值极限分布特性,分析并利用采样协方差矩阵特征值与信号平均能量的关系,推导设定虚警概率条件下判决门限的闭式表达式。该算法不需要预先知道授权用户信号的先验知识,且能够有效克服噪声不确定度的影响。仿真结果显示,当噪声方差估计存在偏差的情况下,该算法具有较强的鲁棒性,且在较少采样点、低信噪比、较少阵元数情况下能够获得比CMME更优的检测性能。     

2台并行机上的批在线调度

针对在2台同构并行机上的批在线调度问题,将经典在线调度中工件顺次到达的列表调度,推广为批在线列表调度,其目标函数是使最大完成时间(makespan)最小.给出了一个批在线启发式算法(BLPT-算法),要求在每一个批中的工件按LPT规则调度.证明了该算法的竞争率为3/2,并给出了该算法的一个实例.     

混合供电发射机的能量调度和自适应功率算法

针对混合供电的点到点无线通信链路,讨论了能量收集过程、数据到达过程以及衰落信道统计分布均未知情况下发射机的能量调度和自适应发送功率问题,目的是在保证通信系统一定性能的要求下最小化传统电网的能耗,即有效利用可再生能源的能量.基于Lyapunov优化提出一种低复杂度动态算法,理论证明了该算法可使优化目标无限趋于最优,同时保证最大数据时延不超过用户要求.仿真结果表明,提出的算法在性能和数据时延上都优于其他2种贪婪算法.     

多小区多播无线携能通信鲁棒信干噪比平衡

针对非理想信道多小区多播协作网络中的供能问题,提出了一种鲁棒的无线携能通信优化方案,该方案以最差用户信干噪比最大化为目标、以每用户能量采集和每小区功率为约束,在保证用户能量采集约束和系统功率预算的前提下实现最差用户服务质量最优化.为了求解优化问题,采用半定松弛和S-引理将原始问题转化为拟凸优化问题,进而采用二分迭代算法得到问题的最优解.仿真结果表明,所提系统设计正确,迭代算法收敛特性良好.     

面向无线自主网络高效信息扩散的资源分配

针对无线自主网络中的信息扩散,提出了一种高效的资源分配机制.首先,使用一个传输队列来描述扩散信息的动态到达和离开过程.针对用户信息数据队列和无线传输信道的时变特性,将动态的信息扩散描述为多用户的马尔可夫决策过程,并将多用户的马尔可夫决策过程进行分解.为了降低算法的复杂度,提出了一种基于模型的在线学习方法.在用户信息数据到达率和无线信道变化的情况下,用户通过在线学习,仅需1次迭代就可确定自身具有预见性的行为决策.     

不完全信息下路径选择策略设计及分析

用户出行时不能获知所有路况信息,针对从出发地去目的地,路段权重信息无法准确预知就必须做出决策,选择出行路径的问题。从在线与竞争策略的角度出发考虑,设计了最优策略——贪婪策略选择路径,当路段权重满足三角不等式时,证明了该策略的竞争比是3且是紧界;当路段权重不满足三角不等式时,证明了该问题不存在竞争策略。     

带两个服务等级约束的三台机排序问题

研究带两个服务等级约束的3台同型机在线排序问题。工件和机器的服务等级为1或2,加工允许中断但不允许引入机器空闲时间,目标是最小化最大完工时间。该文首先证明任意在线算法的竞争比至少是3/2,接着对仅有1台机器等级为1的情形给出了竞争比为5/3的在线算法。     

面向电动汽车无线充电市场的迭代双边拍卖算法

在智能电网中,分布式能源具有灵活性,可以支持来自电动汽车的快速变化的无线充电需求。针对无线充电市场采用迭代双边拍卖算法进行电能供需匹配,分布式能源作为电能卖方,汇集商汇集电动汽车的充电需求,作为电能买方,买卖方按照自身效益最大化的原则进行出价。代理商作为拍卖师,根据出价进行电能分配和定价,可以在买卖方隐私信息未知的情况下最大化总效益。仿真结果表明,该算法可以最大化供需双方的总效益,且具有较快的收敛速度,能够保证电动汽车与分布式能源之间电能分配的高效性。     

基于Q学习算法的随机离散时间系统的随机线性二次最优追踪控制

针对随机线性离散时间系统,利用Q学习算法求解无限时域的随机线性二次最优追踪控制(SLQT)问题.首先,假设通过命令生成器生成追踪所需的参考信号,并建立一个由原随机系统和参考轨迹系统组成的增广系统,把最优追踪问题转化为最优调节问题的形式.其次,为了在线求解随机系统的最优追踪问题,将随机系统转为确定性系统,并根据增广系统定义随机线性二次最优追踪控制的Q函数,在无需知道系统模型参数的情况下在线求解增广随机代数方程(GSAE).再次,证明了Q学习算法和增广随机代数方程的等价性,给出了Q学习算法实现步骤.最后,给出一个仿真实例说明Q学习算法的有效性.     

认知双向中继网络下分布式鲁棒波束成形

针对认知双向中继网络下信道状态信息不理想的情况,提出了基于信干噪比(SINR)平衡的分布式鲁棒波束成形算法. 该算法的最优波束成形因子在满足中继总功率和主用户接收端干扰功率受限的条件下,使认知用户在最差情况下的SINR最大化. 通过使用S-Procedure,并引入半正定松弛思想,可将原优化问题转化为凸优化可行性问题进行求解. 仿真结果表明,该算法可有效降低认知用户对主用户接收端的干扰,保证主用户的正常通信,验证了该算法的有效性和鲁棒性.     

生产和运输时间具有一致性的单机在线最优算法

探讨工件带运输时间实时在线排序问题,目标是极小化所有工件被运达目的地的时间.在工件的加工时间和运输时间具备一致性的情况下,即若工件Ji和Jj的加工时间满足pi≥pj,则它们的运输时间有qi≥qj,给出了竞争比为2的最优在线算法.     

异构网络中时延最小的多接入业务分配算法

以业务到达时延最小化为目标,提出一种联合网络选择和业务分配的并行多接入算法．该算法中考虑了不同网络的可利用传输速率和网络时延,利用贝克曼变化思想证明了最优业务分配问题存在门限值,可以根据门限选择最小的接入网络集合获得最小时延．仿真结果表明在重负载情况下,该算法不仅能获得最大吞吐量,并且能够有效地降低业务的到达时延．     

公交车站有效泊位换算系数的元胞自动机仿真分析

为了研究具有多个泊位的在线公交车站的有效泊位数量,提出在相同的公交车辆排队概率情况下,将多泊位公交车站能服务的最大公交车辆到达率与1个泊位的最大公交车辆到达率比值作为确定有效泊位换算系数的计算方法.构建了适用于在线公交车站车辆运行的一维慢启动多元胞自动机仿真模型.该模型将一辆公交车分解成多个元胞,同时允许车辆纵向跨越多个连续元胞前进,以适应较小时间步长的情况下,公交车辆低速运行的要求.利用仿真模型就具有1个泊位、2个泊位、3个泊位的公交车站分别进行了仿真,并对其有效泊位折算系数进行了计算分析.     

控制与组织效率

从理论上讲,一个完全竞争的市场在达到长期均衡时,便实现了帕累托最优配置或帕累托效率,似乎并不存在也不需要对经济及经济组织的控制,便可达到整个社会福利最大化.但事实上由于信息的不完备性,经济的外部性等原因,不仅完全竞争难以实现,而且最终会导致市场失效,因此社会必须有控制地选定适当的收入分配方案,由市场的竞争均衡来实现帕累托最优.本文目的在于:从增进社会福利的角度出发,搜寻和整理在体制变迁过程中的关于控制与效率的基本理论,为进一步研究国有企业改革作支撑.