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

VMSA: a performance preserving online VM splitting and placement algorithm in dynamic cloud environments

JOURNAL OF SUPERCOMPUTING 2016年第8期72卷 3169-3193页

作者： Liu, Liu Xu, Jie Yu, Hongfang Li, Lemin Qiao, Chunming Univ Elect Sci & Technol China Sch Commun & Informat Engn Chengdu 611731 Peoples R China George Mason Univ Dept Syst Engn & Operat Res Fairfax VA 22030 USA SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14226 USA

Server consolidation schemes whereby each server is replaced with a virtual machine (VM) and multiple such VMs are run on a single physical server can reduce the number of physical servers needed, and in turn, both the cost and energy consumption in data centers. However, existing schemes have not fully exploited the flexibility in the usage and allocation of virtualization resources, so as to allow one application originally deployed on a single large VM (LVM) to be split and hosted by multiple smaller VMs (SVM). Using multiple SVMs instead of an LVM enables resource allocation at a smaller granularity and thus may further increase the utilization and reduce the number of physical servers. However, a major challenge to overcome when deploying multiple SVMs for one application is to preserve the performance of the application in terms of response delay. In this paper, we show through theoretical analysis and experiments that in order to preserve the performance of the application, one needs to allocate sufficient resources to each SVM, and the total amount of resources required by all the SVMs will exceed that required by the LVM. Nevertheless, we also show that by using the proposed heuristic algorithm called VM splitting and assignment (VMSA), we can substantially improve the utilization and reduce the number of physical servers.

关键词： Cloud computing Requirement splitting Virtual machine placement online algorithm Dynamic resource demand

来源：评论

学校读者我要写书评

暂无评论

An algorithm with performance guarantee for the online Container Relocation Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第1期259卷 48-62页

作者： Zehendner, Elisabeth Feillet, Dominique Jaillet, Patrick Ecole Mines St Etienne F-13541 Gardanne France CMP Georges Charpak LIMOS UMR CNRS 6158 F-13541 Gardanne France MIT Dept Elect Engn & Comp Sci Lab Informat & Decis Syst 77 Massachusetts Ave Cambridge MA 02139 USA MIT Ctr Operat Res 77 Massachusetts Ave Cambridge MA 02139 USA

This paper introduces and investigates the online Container Relocation Problem, where containers have to be retrieved from a bay in a container terminal so as to minimize the number of relocations. Unlike the offline version of the problem, the order of container retrievals is revealed one at a time in an online fashion. We analyze the so-called leveling heuristic using the perspective of worst-case competitive analysis of online algorithms and derive its competitive ratio. We then provide some computational experiments which give insights on the actual average performance of the heuristic. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Container terminal algorithm with performance guarantee Container relocation online algorithm

来源：评论

学校读者我要写书评

暂无评论

Better online algorithms for scheduling with machine cost

引用

SIAM JOURNAL ON COMPUTING 2004年第5期33卷 1035-1051页

作者： Dósa, G He, Y Univ Veszprem Dept Math Veszprem Hungary Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Peoples R China

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem. Recently Imreh and Noga proposed adding the concept of machine cost to scheduling problems and considered the so-called list model problem. For this problem, we are given a sequence of independent jobs with positive sizes, which must be processed nonpreemptively on a machine. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. The objective is to minimize the sum of the makespan and cost of machines. In this paper, we first present an online algorithm with a competitive ratio at most 1.5798, which improves the known upper bound 1.618. Then for a special case where every job size is no greater than the machine cost, we present an optimal online algorithm with a competitive ratio 4/3. Last, we present an algorithm with a competitive ratio at most 3/2 for the semionline problem with known largest size, which improves the known upper bound 1.5309.

关键词： parallel machine scheduling machine cost online algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Integrated Scheduling of Production and Two-Stage Delivery of Make-to-Order Products: Offline and online algorithms

引用

INFORMS JOURNAL ON COMPUTING 2019年第3期31卷 493-514页

作者： Tang, Lixin Li, Feng Chen, Zhi-Long Northeastern Univ Inst Ind & Syst Engn Liaoning Engn Lab Operat Analyt & Optimizat Smart Shenyang 110819 Liaoning Peoples R China Huazhong Univ Sci & Technol Sch Management Wuhan 430074 Hubei Peoples R China Univ Maryland Robert H Smith Sch Business College Pk MD 20742 USA

We study integrated production- and delivery-scheduling problems that arise in practical make-to-order settings in several industries. In these problems, make-to-order products are first processed in a plant and then delivered to customer sites through two stages of shipping: first, from the plant to a pool point (e.g., a port, a distribution, or a consolidation center) and, second, from the pool point to customer sites. The objective is to obtain a joint schedule of job processing at the plant and two-stage shipping of completed jobs to customer sites to optimize a performance measure that takes into account both delivery timeliness and total transportation costs. We consider two problems in which delivery timeliness is measured by total or maximum lead time of the jobs and study both offline and online versions of these problems. For the offline problems involving a single production line at the plant, we provide optimal dynamic programming algorithms. For the more general offline problems involving multiple production lines at the plant, we propose fast heuristics and analyze their worst-case and asymptotic performances. For the online problems, we propose online algorithms and analyze their competitive ratios. By comparing our offline heuristics with lower bounds using randomly generated test instances, it is shown that these heuristics are capable of generating near-optimal solutions quickly. Using real data from Baosteel's Meishan plant, we also show that our corresponding offline heuristic generates significantly better solutions than Baosteel's rule-based approach. In addition, our computational results on the performance of the online algorithms relative to the offline heuristics generate important methodological insights that can be used by practitioners in choosing a specific solution approach.

关键词： make-to-order scheduling delivery dynamic programming heuristic online algorithm worst-case analysis asymptotic analysis competitive ratio analysis

来源：评论

学校读者我要写书评

暂无评论

Complexity and online algorithms for minimum skyline coloring of intervals

引用

THEORETICAL COMPUTER SCIENCE 2019年 788卷 66-78页

作者： Erlebach, Thomas Liu, Fu-Hong Liu, Hsiang-Hsuan Shalom, Mordechai Wong, Prudence W. H. Zaks, Shmuel Univ Leicester Dept Informat Leicester Leics England Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Univ Wroclaw Inst Comp Sci Wroclaw Poland TelHai Coll IL-12210 Upper Galilee Israel Univ Liverpool Dept Comp Sci Liverpool Merseyside England Technion Dept Comp Sci Haifa Israel Ruppin Acad Ctr Sch Engn Netanya Israel

Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Skyline coloring of intervals online algorithm NP-hardness Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Distribution-Oblivious online algorithms for Age-of-Information Penalty Minimization

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2023年第4期31卷 1779-1794页

作者： Tsai, Cho-Hsin Wang, Chih-Chun Purdue ECE W Lafayette IN 47907 USA MathWorks Inc Natick MA 01760 USA

The ever-increasing needs of supporting real-time applications have spurred new studies on minimizing Age-of-Information (AoI), a novel metric characterizing the data freshness of the system. This work studies the single-queue information update system and strengthens the seminal results of Sun et al. on the following fronts: (i) When designing the optimal offline schemes with full knowledge of the delay distributions, a new fixed-point-based method is proposed with quadratic convergence rate, an order-of-magnitude improvement over the state-of-the-art;(ii) When the distributional knowledge is unavailable (which is the norm in practice), two new low-complexity online algorithms are proposed, which provably attain the optimal average AoI penalty;and (iii) the online schemes also admit a modular architecture, which allows the designer to upgrade certain components to handle additional practical challenges. Two such upgrades are proposed for the situations: (iii.1) The AoI penalty function is also unknown and must be estimated on the fly, and (iii.2) the unknown delay distribution is Markovian instead of i.i.d. The performance of our schemes is either provably optimal or within 3% of the omniscient optimal offline solutions in all simulation scenarios.

关键词： Age-of-information online algorithm fixed-point equation stochastic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Primal Dual Gives Almost Optimal Energy-Efficient online algorithms

引用

ACM TRANSACTIONS ON algorithmS 2018年第1期14卷 1–30页

作者： Devanur, Nikhil R. Huang, Zhiyi Microsoft Res 1 Microsoft Way Redmond WA 98052 USA Univ Hong Kong 423 Chow Yei Ching Bldg Pokfulam Hong Kong Peoples R China

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow-time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for unrelated machines.) For power functions of the form f (s) = s(alpha) for some constant alpha > 1, we get a competitive ratio of O(alpha/log alpha), improving upon a previous competitive ratio of O(alpha(2)) by Anand et al. (2012), along with a matching lower bound of Omega(alpha/log alpha). Further, in the resource augmentation model, with a 1+epsilon speed up, we give a 2(1/epsilon + 1) competitive algorithm, with essentially the same techniques, improving the bound of 1 + O(1/epsilon(2)) by Gupta et al. (2010) and matching the bound of Anand et al. (2012) for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.

关键词： online algorithm scheduling flow-time energy efficiency

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for MapReduce scheduling on two uniform machines

引用

OPTIMIZATION LETTERS 2019年第7期13卷 1663-1676页

作者： Jiang, Yiwei Zhou, Ping Cheng, T. C. E. Ji, Min Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Sch Management & & Business Hangzhou 310018 Zhejiang Peoples R China Zhejiang Business Coll Coll Humanities Hangzhou 310053 Zhejiang Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

We study online scheduling on two uniform machines in the MapReduce system. Each job consists of two sets of tasks, namely the map tasks and reduce tasks. A job's reduce tasks can only be processed after all its map tasks are finished. The map tasks are fractional, i.e., they can be arbitrarily split and processed on different machines in parallel. Our goal is to find a schedule that minimizes the makespan. We consider two variants of the problem, namely the cases involving preemptive reduce tasks and non-preemptive reduce tasks. We provide lower bounds for both variants. For preemptive reduce tasks, we present an optimal online algorithm with a competitive ratio of s2+2s+5+1-s/2 where s = 1 is the ratio between the speeds of the two machines. For non-preemptive reduce tasks, we show that the LS-like algorithm is optimal and its competitive ratio is 2s+1/s+1 if s < 1+root 5/2 and s+1/s if s >= 1+root 5/2.

关键词： Big data MapReduce scheduling online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal online algorithms for scheduling on two identical machines under a grade of service

引用

Journal of Zhejiang University-Science A(Applied Physics & Engineering) 2006年第3期7卷 309-314页

作者：蒋义伟何勇唐春梅 Laboratory of Information and Optimization Technologies Ningbo Institute of Technology Zhejiang University Ningbo 315100 China Department of Mathematics Zhejiang University Hangzhou 310027 China Department of Mathematics Zhejiang University Hangzhou 310027 China

This work is aimed at investigating the online scheduling problem on two parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels, so each job and machine are labelled with the GoS levels, and each job can be processed by a particular machine only when its GoS level is no less than that of the machine. The goal is to minimize the makespan. For non-preemptive version, we propose an optimal online al-gorithm with competitive ratio 5/3. For preemptive version, we propose an optimal online algorithm with competitive ratio 3/2.

关键词： online algorithm Competitive analysis Parallel machine scheduling Grade of service (GoS)

来源：评论

学校读者我要写书评

暂无评论

Efficient Framework for Real-Time Color Cast Correction and Dehazing Using online algorithms to Approximate Image Statistics

引用

IEEE ACCESS 2024年 12卷 72813-72827页

作者： Bilal, Muhammad Masud, Shahid Hanif, Muhammad Shehzad King Abdulaziz Univ Ctr Excellence Intelligent Engn Syst Jeddah 21589 Saudi Arabia King Abdulaziz Univ Fac Engn Dept Elect & Comp Engn Jeddah 21589 Saudi Arabia Lahore Univ Management Sci Dept Elect Engn Lahore 54792 Pakistan

Image dehazing is a crucial task in the early stages of real-time image processing pipelines used in applications such as surveillance and advance driver assistance systems. Dehazing algorithms mitigate the spatially selective degradation of image details caused by natural phenomenon such as fog and sandstorms. The problem is exacerbated in the presence of color cast which can affect the color-sensitive processing in the downstream tasks. In order to correct these two aberrations, we have proposed a light-weight algorithm which is not only quantitively more effective than the state-of-the-art works but also uses minimal computational resources. Specifically, it has been proposed to tackle both aforementioned problems by processing luminance and chrominance channels separately through a custom resource-efficient colorspace transform. Moreover, it has been proposed to employ online calculation of the relevant video stream statistics to estimate the degradation model over several temporally adjacent frames. This approach not only reduces the hardware resource utilization when implemented inside the video processing pipeline but also reduces the flicker effect observed when frames are processed individually. It has been demonstrated through quantitative analysis on standard datasets that the proposed approach either works at par or better than the reference works in terms of image quality metrics. Furthermore, the proposed framework has been developed as a real-time video processing system on an FPGA platform. The synthesis results of this implementation suggest that the proposed framework achieves this performance using minimal logic resources.

关键词： Image color analysis Real-time systems Hardware Estimation Streaming media Task analysis Approximate computing Field programmable gate arrays Image processing algorithm design and analysis color cast correction dehazing FPGA high-level synthesis online algorithm real-time image processing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：