共查询到20条相似文献,搜索用时 187 毫秒
1.
本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法. 相似文献
2.
带机器准备时间的平行机在线与半在线排序 总被引:12,自引:0,他引:12
本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。 相似文献
3.
工件按加工长度不增序到达的最小化最大流程在线分批排序 总被引:1,自引:0,他引:1
研究单处理机工件按加工长度不增顺序到达的在线分批排序问题.工件按时在线到达,目标是最小化最大流程.流程时间是指工件的完工时间与到达时间的差值,它体现了工件在系统内的逗留时间.对于批容量有界的情形,给出了一个竞争比为1+√5/2的最好可能的在线算法;对于批容量无界的情形,给出了一个竞争比为√2的最好可能的在线算法. 相似文献
4.
研究调度问题上机器服务总时间已知的问题,针对机器的速度和准备时间不同,分析研究带机器准备时间的服务总时间已知的两台同类机半在线调度优化问题.目标为最小化最大机器服务时间,对于机器服务所有工件的时间已知的半在线情形,给出了人一个竞争比不超过2(s+1)/(2s+1)的半在线算法,其中s_i为机器速度,s_1=1,s_2=s>1. 相似文献
5.
在线多租赁选择问题的最优竞争策略 总被引:2,自引:0,他引:2
在线算法与竞争分析是研究信息不确定决策问题的一种新工具,应用该方法研究在线租赁问题是近年来国内外的一个研究热点。传统的在线租赁问题以经典的"雪橇租赁模型"为基础,考虑在线决策者可以选择购买或按单位时间租赁的方式来使用设备。然而现实租赁市场(比如汽车租赁,房屋租赁)往往提供多种租赁方式供在线决策者选择,除了按单位时间进行租赁,通常可以以一个较优惠的价格租赁多个单位时间。在这种现实背景下,本文建立了多种租赁形式下的在线租赁模型,给出了这种租赁模型下的确定性竞争策略,并证明该策略具有最优竞争比。 相似文献
6.
7.
本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法. 相似文献
8.
9.
10.
11.
12.
13.
14.
Scheduling with unexpected machine breakdowns 总被引:1,自引:0,他引:1
We investigate an online version of a basic scheduling problem where a set of jobs has to be scheduled on a number of identical machines so as to minimize the makespan. The job processing times are known in advance and preemption of jobs is allowed. Machines are non-continuously available, i.e., they can break down and recover at arbitrary time instances not known in advance. New machines may be added as well. Thus machine availabilities change online. We first show that no online algorithm can construct optimal schedules. We also show that no online algorithm can achieve a bounded competitive ratio if there may be time intervals where no machine is available. Then we present an online algorithm that constructs schedules with an optimal makespan of CmaxOPT if a lookahead of one is given, i.e., the algorithm always knows the next point in time when the set of available machines changes. Finally, we give an online algorithm without lookahead that constructs schedules with a nearly optimal makespan of CmaxOPT+, for any >0, if at any time at least one machine is available. Our results demonstrate that not knowing machine availabilities in advance is of little harm. 相似文献
15.
16.
Online signal extraction by robust linear regression 总被引:1,自引:0,他引:1
Summary In intensive care, time series of vital parameters have to be analysed online, i.e. without any time delay, since there may
be serious consequences for the patient otherwise. Such time series show trends, slope changes and sudden level shifts, and
they are overlaid by strong noise and many measurement artefacts. The development of update algorithms and the resulting increase
in computational speed allows to apply robust regression techniques to moving time windows for online signal extraction. By
simulations and applications we compare the performance of least median of squares, least trimmed squares, repeated median and deepest regression for online signal extraction. 相似文献
17.
本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$(t,t+\Delta(t)]$内到达工件的信息,这里前瞻区间的长度$\Delta(t)=\beta p_{\max}(t)$并非定长,其中$p_{\max}(t)$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in(0,1)$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。 相似文献
18.
Aimed at the inventory competition of perishable products in a dual-channel supply chain with consideration of the delivery lead time in the online direct channel, we extend the Newsvendor model considering stock-out-based consumer switching behavior to include the delivery lead time. We examine the retailer's optimal order quantity decision in the retail channel and the manufacturer's optimal inventory level decision in the online direct channel, explore the manufacturer's optimal delivery lead time decision in the online direct channel, discuss the impact of the product price and consumer switching behavior on the optimal decisions of supply chain members, and compare the optimal decisions between decentralized and centralized scenarios. The results show that, compared with the centralized scenario, at least one of the supply chain members will overstock in the decentralized scenario and that consumers in the online direct channel enjoy a shorter delivery lead time and hence better service in the decentralized scenario. Finally, we present numerical examples to analyze the impact of relevant parameters on the supply chain members’ profits and the supply chain efficiency. 相似文献
19.
本文研究单台无界平行批处理机上带有可变前瞻区间的在线排序问题。工件按时在线到达,目标是最小化时间表长。在时刻$t$,在线算法能够预见到$(t,t+\Delta(t)]$内到达工件的信息,这里前瞻区间的长度$\Delta(t)=\beta p_{\max}(t)$并非定长,其中$p_{\max}(t)$表示在$t$时刻及之前到达工件的最大加工时长,$\beta\in(0,1)$是常数。本文对于工件加工时长的一般情形,给出了当 0<β≤1/6 时最好可能的在线算法;对于工件加工时长被限制在一个区间的情形,给出了当 0<β<1 时最好可能的在线算法。 相似文献
20.
Jin Hong 《Designs, Codes and Cryptography》2010,57(3):293-327
Cryptanalytic time memory tradeoff algorithms are generic one-way function inversion techniques that utilize pre-computation.
Even though the online time complexity is known up to a small multiplicative factor for any tradeoff algorithm, false alarms
pose a major obstacle in its accurate assessment. In this work, we study the expected pre-image size for an iteration of functions
and use the result to analyze the cost incurred by false alarms. We are able to present the expected online time complexities
for the Hellman tradeoff and the rainbow table method in a manner that takes false alarms into account. We also analyze the
effects of the checkpoint method in reducing false alarm costs. The ability to accurately compute the online time complexities
will allow one to choose their tradeoff parameters more optimally, before starting the expensive pre-computation process. 相似文献