共查询到20条相似文献,搜索用时 109 毫秒
1.
2.
3.
研究调度问题上机器服务总时间已知的问题,针对机器的速度和准备时间不同,分析研究带机器准备时间的服务总时间已知的两台同类机半在线调度优化问题.目标为最小化最大机器服务时间,对于机器服务所有工件的时间已知的半在线情形,给出了人一个竞争比不超过2(s+1)/(2s+1)的半在线算法,其中s_i为机器速度,s_1=1,s_2=s>1. 相似文献
4.
5.
一台批处理机一次可以同时加工多个工件(称为一批),每批工件有相同的开工和完工时间,加工时间等于其中最长工件的加工时间.本文研究单台批处理机上的在线排序,其中每个工件有事先未知的到达时间,加工时间在其到达时才知道,目标是极小化工件的最大完工时间.Zhang等(Naval Research Logistics,2001,48:241~258)就该问题提出了一个竞争比不超过2的算法MHB,并猜测其竞争比可以达到1.618,因此是最好的在线算法.在本文中,我们证明了当机器容量趋于无穷时,算法MHB的竞争比不可能小于2,从而就上述猜测给出了否定的回答;另外,我们也提出了一个新算法,其竞争比也不超过2. 相似文献
6.
7.
8.
研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法. 相似文献
9.
10.
本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686. 相似文献
11.
Abraham D. Flaxman David Gamarnik Gregory B. Sorkin 《Random Structures and Algorithms》2005,27(3):277-289
Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For “sparse” random instances the competitive ratio is also large, with high probability (whp); If the instance has ¼(1 + ε)n random edge pairs, with 0 < ε ≤ 0.003, then any online algorithm generates a component of size O((log n)3/2) whp , while the optimal offline solution contains a component of size Ω(n) whp . For “dense” random instances, the average‐case competitive ratio is much smaller. If the instance has ½(1 ? ε)n random edge pairs, with 0 < ε ≤ 0.015, we give an online algorithm which finds a component of size Ω(n) whp . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005 相似文献
12.
In this paper, a new price is given to the online decision maker at the beginning of each day. The trader must decide how many items to purchase according to the current price. We present three variants and an online algorithm based on cost function. The competitive ratio of the online algorithm is given for each variant, which is a performance measure of an online algorithm. More importantly, we show that the online algorithm is optimal. 相似文献
13.
对网络环境下一个买家多个卖家的反向拍卖,研究了供应商在不同时间到达并投标而采购商接到每个投标后需要立即做出决策的在线反向拍卖的风险策略。对于无限可分商品,在资金一定前提下,首先对采购商无风险行为情形给出了基于标价上涨威胁的在线反向拍卖策略,通过竞争分析得到了其最优竞争比及整体需要曲线;其次引入采购商的风险容忍度概念,建立了激励相容在线反向拍卖的风险回报框架,并对风险忍耐策略进行了竞争分析。 相似文献
14.
依附于互联网电子商务的在线采购拍卖交易, 对传统的贝叶斯离线拍卖理论提出新的挑战, 因为面对不同时间点的投标, 采购电商必须即可决策出是否中标以及购买价格。鉴于此, 对于诸如石油、煤、粮食等无限可分商品的电子采购, 本文基于投标具有高斯分布特征设计了一种激励相容的在线采购策略, 演绎出在线采购的数学模型, 利用Runge-Kutta数值算法, 通过Matlab编程求解出采购电商在线定价策略的需求曲线及其对应的竞争比, 最后, 利用数值模拟, 将在线采购机制策略与纯竞争分析得到的在线采购策略比较, 结果显示利用了高斯分布信息的在线采购策略的竞争性能由于利用了投标的统计信息而得到了提高。 相似文献
15.
We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We analyze two greedy primal-dual algorithms and provide bounds on their competitive ratios. Our analysis relies on a smooth surrogate of the objective function that needs to satisfy a new diminishing returns (PSD-DR) property (that its gradient is order-reversing with respect to the PSD cone). Using the representation for monotone maps on the PSD cone given by Löwner’s theorem, we obtain a convex parametrization of the family of functions satisfying PSD-DR. We then formulate a convex optimization problem to directly optimize our competitive ratio bound over this set. This design problem can be solved offline before the data start arriving. The online algorithm that uses the designed smoothing is tailored to the given cost function, and enjoys a competitive ratio at least as good as our optimized bound. We provide examples of computing the smooth surrogate for D-optimal and A-optimal experiment design, and demonstrate the performance of the custom-designed algorithm. 相似文献
16.
René Sitters 《Operations Research Letters》2010,38(6):585-588
We give an online algorithm for minimizing the total weighted completion time on a single machine where preemption of jobs is allowed and prove that its competitive ratio is at most 1.57. 相似文献
17.
We answer this question using the competitive ratio as an indicator for the quality of information about the future. Analytical results show that the better the information the better the worst-case competitive ratios. However, experimental analysis gives a slightly different view. We calculate the empirical-case competitive ratios of different variants of a threat-based online algorithm. The results are based on historical data of the German Dax-30 index. We compare our experimental empirical-case results to the analytical worst-case results given in the literature. We show that better information does not always lead to a better performance in real life applications. The empirical-case competitive ratio is not always better with better information, and some a-priori information is more valuable than other for practical settings. 相似文献
18.
优惠卡问题是租赁问题的一个推广,已往的研究都是考虑只存在一种优惠活动的情况,并给出最优的单阀值购买策略。在本文中,则考虑更接近实际的情况,即存在多种优惠活动的问题,给出了当所有优惠卡价格在有界范围内的双阀值购买策略,分别给出了其竞争比上下界。最后,通过数值分析说明优惠卡价格和折扣率对消费者购买策略和竞争比的影响。 相似文献
19.
考察单水库电站的多时段发电调度问题,决策者在每个时段初决策该时段的发电量,目标是使得在整个调度期内总发电量最大。针对在每个时段决策时缺乏当前及后续时段来水信息的情形,运用在线理论建立在线发电调度模型,设计给出了竞争比为2/(2-β(1-Ф))的在线发电调度策略,其中,β∈(0,1)表示每个时段最大来水导致的水头最大增幅与水库有效水头最大落差的比值,Ф∈(0,1)表示最低与最高有效水头数值之比。针对各时段可获知当前时段来水信息的情形,给出了在线调度策略,并证明了其竞争比为1+(1-Ф)/(1+Ф)。 相似文献
20.
We propose an online algorithm for an economic lot-sizing (ELS) problem with lookahead, which achieves asymptotically optimal worst-case performance for increasing lookahead. Although intuitive, this result is interesting since deterministic algorithms for previously studied online ELS problems have unbounded competitive ratio. We also prove lookahead-dependent lower bounds for deterministic algorithms. 相似文献