检索结果-内蒙古大学图书馆

SIAM JOURNAL ON COMPUTING 1999年第2期29卷 459-473页

作者： Albers, S Max Planck Inst Informat D-66123 Saarbrucken Germany

We study a classical problem in online scheduling. A sequence of jobs must be scheduled on m identical parallel machines. As each job arrives, its processing time is known. The goal is to minimize the makespan. Bartal et al. [J. Comput. System Sci., 51 (1995), pp. 359-366] gave a deterministic online algorithm that is 1.986-competitive. Karger, Phillips, and Torng [J. algorithms, 20 (1996), pp. 400-430] generalized the algorithm and proved an upper bound of 1.945. The best lower bound currently known on the competitive ratio that can be achieved by deterministic online algorithms is equal to 1.837. In this paper we present an improved deterministic online scheduling algorithm that is 1.923-competitive;for all m greater than or equal to 2. The algorithm is based on a new scheduling strategy, i.e., it is not a generalization of the approach by Bartal et al. Also, the algorithm has a simple structure. Furthermore, we develop a better lower bound. We prove that, for general m, no deterministic online scheduling algorithm can be better than 1.852-competitive.

关键词： makespan minimization online algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

An online Auction Mechanism for Dynamic Virtual Cluster Provisioning in Geo-Distributed Clouds

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2017年第3期28卷 677-688页

作者： Shi, Weijie Wu, Chuan Li, Zongpeng Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada

It is common for cloud users to require clusters of inter-connected virtual machines (VMs) in a geo-distributed IaaS cloud, to run their services. Compared to isolated VMs, key challenges on dynamic virtual cluster (VC) provisioning (computation + communication resources) lie in two folds: (1) optimal placement of VCs and inter-VM traffic routing involve NP-hard problems, which are non-trivial to solve offline, not to mention if an online efficient algorithm is sought;(2) an efficient pricing mechanism is missing, which charges a market-driven price for each VC as a whole upon request, while maximizing system efficiency or provider revenue over the entire span. This paper proposes efficient online auction mechanisms to address the above challenges. We first design SWMOA, a novel online algorithm for dynamic VC provisioning and pricing, achieving truthfulness, individual rationality, computation efficiency, and (1 + 2 log mu)-competitiveness in social welfare, where m is related to the problem size. Next, applying a randomized reduction technique, we convert the social welfare maximizing auction into a revenue maximizing online auction, PRMOA, achieving O(log mu)-competitiveness in provider revenue, as well as truthfulness, individual rationality and computation efficiency. We investigate auction design in different cases of resource cost functions in the system. We validate the efficacy of the mechanisms through solid theoretical analysis and trace-driven simulations.

关键词： Cloud computing auction mechanism design online algorithm resource allocation

来源：评论

学校读者我要写书评

暂无评论

online Bounds on Balancing Two Independent Criteria with Replication and Reallocation

引用

IEEE TRANSACTIONS ON COMPUTERS 2012年第11期61卷 1601-1610页

作者： Tse, Savio S. H. Istanbul Univ Dept Comp Engn TR-34320 Istanbul Turkey

We study the online bicriteria load balancing problem in this paper. We choose a system of distributed homogeneous file servers located in a cluster as the scenario and propose three online approximate solutions for balancing their loads and required storage spaces upon placements. We first revisit the best existing solution for simple placement (i.e., without replication and reallocation), and rewrite it in our first algorithm by imposing some flexibilities. Our second algorithm is to apply document replication. The upper bound of load is significantly reduced, without sacrificing that of the storage space. This upper bound contains at least one special case which can never be outperformed by any online simple placement algorithms. Lastly, we show that there exists an online algorithm which allows very little document reallocation, but gives an upper bound result on the load and storage space, which is never reachable by any online algorithms for simple placement. The time complexities of the first two algorithms are in O(log M), and the last algorithm runs in O(log MN) time, where M is the number of servers, and N is the number of existing documents.

关键词： Approximate distributed online algorithm load balancing scheduling distributed file server document placement replication reallocation

来源：评论

学校读者我要写书评

暂无评论

Real-Time Feedback Based online Aggregate EV Power Flexibility Characterization

引用

IEEE TRANSACTIONS ON SUSTAINABLE ENERGY 2024年第1期15卷 658-673页

作者： Yan, Dongxiang Huang, Shihan Chen, Yue Chinese Univ Hong Kong Dept Mech & Automat Engn Hong Kong Peoples R China

As an essential measure to combat global warming, electric vehicles (EVs) have witnessed rapid growth. Flexible EVs can enhance power systems' ability to handle renewable generation uncertainties. How EV flexibility can be utilized in power grid operation has captured great attention. However, the direct control of individual EVs is challenging due to their small capacity and large number. Hence, it is the aggregator that interacts with the grid on behalf of the EVs by characterizing their aggregate flexibility. In this article, we focus on the aggregate EV power flexibility characterization problem. First, an offline model is built to obtain the lower and upper bounds of the aggregate EV power flexibility region. It ensures that any trajectory within the region is feasible. Then, considering that parameters such as real-time electricity prices and EV arrival/departure times are not known in advance, an online algorithm is developed based on Lyapunov optimization techniques. We provide a theoretical bound for the maximum charging delay under the proposed online algorithm. Furthermore, real-time feedback is designed and integrated into the proposed online algorithm to better unlock EV power flexibility. Comprehensive performance comparisons are carried out to demonstrate the advantages of the proposed method.

关键词： Aggregate flexibility charging station electric vehicle (EV) Lyapunov optimization online algorithm

来源：评论

学校读者我要写书评

暂无评论

online unbounded batch scheduling on parallel machines with delivery times

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第1期29卷 228-236页

作者： Liu, Peihai Lu, Xiwen E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

We consider the online unbounded batch scheduling problems on m identical machines subject to release dates and delivery times. Jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Jobs can be processed in a common batch and the batch capacity is unbounded. Once the processing of a job is completed it is independently delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J(j), its processing time and delivery time are denoted by p(j) and q(j), respectively. We first consider a restricted model: the jobs have agreeable processing and delivery times, i.e., for any two jobs J(i) and J(j) p(i) > p(j) implies q(i) >= q(j). For the restrict case, we provide a best possible online algorithm with competitive ratio 1+ alpha(m), where alpha(m) > 0 is determined by alpha(2)(m) + m alpha(m) = 1. Then we present an online algorithm with a competitive ratio of 1 + 2/ [root m] for the general case.

关键词： Scheduling online algorithm Batch machines Delivery times Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Resource augmentation for online bounded space bin packing

引用

JOURNAL OF algorithmS 2002年第2期44卷 308-320页

作者： Csirik, J Woeginger, GJ Univ Twente Dept Math NL-7500 AE Enschede Netherlands Univ Szeged Dept Comp Sci H-6720 Szeged Hungary Graz Tech Univ Inst Math A-8010 Graz Austria

We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0, 1] into a small number of bins of size b greater than or equal to 1. Its performance is measured by comparing the produced packing against: the optimal offline packing of the list L into bins of size I. We present a complete solution to this problem: For every bin size, b greater than or equal to 1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound rho (b). Moreover, we prove that no online bounded space algorithm can perform better than rho(b) in the worst case. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： online algorithm competitive analysis resource augmentation approximation algorithm asymptotic worst case ratio bin packing

来源：评论

学校读者我要写书评

暂无评论

online single-machine scheduling to minimize the linear combination of makespans of two agents

引用

INFORMATION PROCESSING LETTERS 2022年 173卷

作者： Lu, Xiwen Zhao, Kejun Gu, Manzhan East China Univ Sci & Technol Sch Sci Shanghai 200237 Peoples R China Shanghai Univ Finance & Econ Sch Math Shanghai 200433 Peoples R China

This paper considers an online two-agent scheduling problem. All jobs belong to two agents A and B, and each job is arriving over time, which means that no information of the job is known in advance before its arrival. The objective is to schedule all jobs on a single machine such that the linear combination of the makespans of the two agents, i.e. C-max(A) + theta C-max(B) (theta >= 1), is minimized. For the problem, we propose an online algorithm and show the competitive ratio of the algorithm is 1 + 2 theta+theta(2)/2+2 theta+theta(2). (C) 2021 Elsevier B.V. All rights reserved.

关键词： Scheduling Two-agent Release dates online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Peak-Aware online Economic Dispatching for Microgrids

引用

IEEE TRANSACTIONS ON SMART GRID 2018年第1期9卷 323-335页

作者： Zhang, Ying Hajiesmaili, Mohammad H. Cai, Sinan Chen, Minghua Zhu, Qi Chinese Univ Hong Kong Dept Informat Engn Hong Kong Hong Kong Peoples R China Xi An Jiao Tong Univ Sch Elect Engn Xian 710049 Peoples R China Univ Calif Riverside Dept Elect & Comp Engn Riverside CA 92521 USA

By employing local renewable energy sources and power generation units while connected to the central grid, microgrid can usher in great benefits in terms of cost efficiency, power reliability, and environmental awareness. Economic dispatching is a central problem in microgrid operation, which aims at effectively scheduling various energy sources to minimize the operating cost while satisfying the electricity demand. Designing intelligent economic dispatching strategies for microgrids;however, it is drastically different from that for conventional central grids due to two unique challenges. First, the demand and renewable generation uncertainty emphasizes the need for online algorithms. Second, the widely-adopted peak-based pricing scheme brings out the need for new peak-aware strategy design. In this paper, we tackle these critical challenges and devise peak-aware online economic dispatching algorithms. We prove that our deterministic and randomized algorithms achieve the best possible competitive ratios 2-beta and e/(e - 1 + beta) in the fast responding generator scenario, where beta. [0, 1] is the ratio between the minimum grid spot price and the local-generation price. By extensive empirical evaluations using real-world traces, we show that our online algorithms achieve near offline-optimal performance. In a representative scenario, our algorithm achieves 17.5% and 9.24% cost reduction as compared with the case without local generation units and the case using peak-oblivious algorithms, respectively.

关键词： Microgrids online algorithm peak-aware scheduling economic dispatching

来源：评论

学校读者我要写书评

暂无评论

An online joint replenishment problem combined with single machine scheduling

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第5期45卷 1-20页

作者： Gyorgyi, Peter Kis, Tamas Tamasi, Timea ELKH Inst Comp Sci & Control Kende utca 13-17 H-1111 Budapest Hungary Eotvos Lorand Univ Inst Math Dept Operat Res H-1117 Budapest Hungary

This paper considers a combination of the joint replenishment problem with single machine scheduling. There is a single resource, which is required by all the unit time jobs, and a job can be started at time point t on the machine if and only if the machine does not process another job at t, and the resource is replenished between its release date and t. Each replenishment has a cost, which is independent of the amount replenished. The objective is to minimize the total replenishment cost plus the maximum flow time of the jobs. We consider the online variant of the problem, where the jobs are released over time, and once a job is inserted into the schedule, its starting time cannot be changed. We propose a deterministic 2-competitive online algorithm for the general input. Moreover, we show that for a certain class of inputs (so-called p-bounded input), the competitive ratio of the algorithm tends to v2 as the number of jobs tends to infinity. We also derive several lower bounds for the best competitive ratio of any deterministic online algorithm under various assumptions.

关键词： Joint replenishment Single machine scheduling online algorithm Maximum flow time

来源：评论

学校读者我要写书评

暂无评论

online independent reduced least squares support vector regression

引用

INFORMATION SCIENCES 2012年 201卷 37-52页

作者： Zhao, Yong-Ping Sun, Jian-Guo Du, Zhong-Hua Zhang, Zhi-An Li, Ye-Bo Nanjing Univ Sci & Technol ZNDY Ministerial Key Lab Nanjing 210094 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Energy & Power Engn Nanjing 210016 Peoples R China

In this paper, an online algorithm, viz, online independent reduced least squares support vector regression (OIRLSSVR), is proposed based on the linear independence and the reduced technique. As opposed to some offline algorithms, OIRLSSVR takes the realtime advantage, which is confirmed using benchmark data sets. In comparison with online algorithm, the realtime of OIRLSSVR is also favorable. As for this point, it is tested with experiments on the benchmark data sets and a more realistic scenario namely a diesel engine example. All in all. OIRLSSVR can enhance the modeling realtime, especially for the case where the samples enter in a flow mode. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Machine learning Support vector regression online algorithm Offline algorithm Linear independence

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：