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

online fractional hierarchical scheduling on uniformly related machines

COMPUTERS & OPERATIONS RESEARCH 2020年 113卷

作者： Liu, Zhaohui Zhan, Jiyuan East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

This paper studies the online fractional hierarchical scheduling problem on uniformly related machines. In the problem, the jobs and machines have several different hierarchies and a job can be processed on a machine if and only if its hierarchy is not below the hierarchy of the machine, furthermore, the jobs can be arbitrarily split between the machines. The objective is to determine the assignment scheme of the jobs so as to minimize the makespan. We present several sophisticated lower bounds and an online algorithm framework for the problem. Our bounds dominate all known bounds, and the algorithm is optimal for the problem with no more than four hierarchies. Computational tests show that our algorithm has the potential to work for all cases. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： online algorithm Fractional scheduling Hierarchical scheduling Uniformly related machines

来源：评论

学校读者我要写书评

暂无评论

Joint online Coflow Routing and Scheduling in Data Center Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2019年第5期27卷 1771-1786页

作者： Tan, Haisheng Jiang, Shaofeng H. -C. Li, Yupeng Li, Xiang-Yang Zhang, Chenzi Han, Zhenhua Lau, Francis Chi Moon USTC Coll Comp Sci & Technol Hefei 230027 Anhui Peoples R China Weizmann Inst Sci Fac Math & Comp Sci IL-76100 Rehovot Israel Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 1A1 Canada Univ Hong Kong HKU Dept Comp Sci Hong Kong Peoples R China Jinan Univ Dept Comp Sci Guangzhou 510632 Guangdong Peoples R China

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage computing task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the total weighted coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources, such as link bandwidth. To minimize the total weighted CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow. We then derive a competitive ratio bound of our problem and prove that the competitive ratio of OMCoflow is nearly tight. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently and avoids frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the total weighted CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER).

关键词： Coflow datacenter networks online algorithm

来源：评论

学校读者我要写书评

暂无评论

A new upper bound for the online square packing problem in a strip

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第4期33卷 1411-1420页

作者： Yu, Guosong Mao, Yanling Xiao, Jiaoliao Nanchang Univ Dept Math Nanchang 330031 Jiangxi Peoples R China Nanchang Univ Numer Simulat & High Performance Comp Lab Nanchang 330031 Jiangxi Peoples R China Nanchang Univ Dept Management Sci & Engn Nanchang 330031 Jiangxi Peoples R China

In this paper we consider the online problem of packing a list of squares into one strip of width 1 and infinite length without overlap so as to minimize the required height of the packing. We derive an upper bound 5 ... 详细信息

关键词： Strip packing Square packing online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Competitive ratios for preemptive and non-preemptive online scheduling with nondecreasing concave machine cost

引用

INFORMATION SCIENCES 2014年 269卷 128-141页

作者： Jiang, Yiwei Hu, Jueliang Liu, Longcheng Zhu, Yuqing Cheng, T. C. E. Zhejiang Sci Tech Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Xiamen Univ Sch Math Sci Xiamen 361005 Peoples R China Univ Texas Dallas Dept Comp Sci Dallas TX 75080 USA Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

We consider an online scheduling problem where jobs arrive one by one and each job must be irrevocably scheduled on the machines. No machine is available initially. When a job arrives, we either purchase a new machine to process it or schedule it for processing on an existing machine. The objective is to minimize the sum of the makespan and the total cost of all the purchased machines. We assume that the total machine cost function is concave in the number of purchased machines. Considering both non-preemptive and preemptive variants of the problem, we prove that the competitive ratio of any non-preemptive or preemptive algorithm is at least 1.5. For the non-preemptive variant, we present an online algorithm and show that its competitive ratio is 1.6403. For the preemptive variant, we propose an online algorithm and show that its competitive ratio is 1.5654. We further prove that both competitive ratios are tight. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Scheduling Concave function Machine cost online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2014年第3期74卷 2180-2192页

作者： Sun, Hongyang Hsu, Wen-Jing Cao, Yangjie Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore Zhengzhou Univ Sch Software Engn Zhengzhou Peoples R China

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at anytime. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs' execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Adaptive scheduling Parallel jobs Set response time Multiprocessors online algorithm Competitive analysis Hierarchical scheduling Fairness Efficiency

来源：评论

学校读者我要写书评

暂无评论

Truthful online Auction Toward Maximized Instance Utilization in the Cloud

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2018年第5期26卷 2132-2145页

作者： Zhu, Yifei Fu, Silvery D. Liu, Jiangchuan Cui, Yong Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Simon Fraser Univ Burnaby BC V5A 1S6 Canada Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Tsinghua Univ Dept Comp Sci & Technol Beijing 100084 Peoples R China

Although infrastructure as a service (IaaS) users are busy scaling up/out their cloud instances to meet the ever-increasing demands, the dynamics of their demands, as well as the coarse-grained billing options offered by leading cloud providers, have led to substantial instance underutilization in both temporal and spatial domains. This paper systematically examines an instance subletting service, where sublettable instances can be leased to others within predetermined periods when underutilized, from both theoretical and practical perspectives. The studied instance subletting service extends and complements the existing instance market of laaS providers. We identify the unique challenges and opportunities in this new service, and design online auction mechanisms to make allocation and pricing decisions for the instances to he sublet. For static supplies of instances, our mechanism guarantees truthfulness and individual rationality with the hest possible competitive ratio. We then incorporate a multi-stage discount strategy to gracefully handle dynamic supplies. Extensive trace-driven simulations show that our service achieves significant performance gains in both cost savings and social welfare. We further pinpoint the challenges in implementing such a service in the real-world system and validate our modeling assumptions through a container-based prototype implemented over Amazon EC2.

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

来源：评论

学校读者我要写书评

暂无评论

online Robust Subspace Clustering With Application to Power Grid Monitoring

引用

IEEE ACCESS 2023年 11卷 27816-27828页

作者： Lee, Young-Hwan Kim, Seung-Jun Lee, Kwang Y. Nam, Taesik Univ Maryland Baltimore Cty Dept Comp Sci & Elect Engn Baltimore MD 21250 USA Baylor Univ Dept Elect & Comp Engn Waco TX 76798 USA Korea Inst Ind Technol Green Energy & Nano Technol Res & Dev Grp Gwangju 61012 South Korea

In this work, a robust subspace clustering algorithm is developed to exploit the inherent union-of-subspaces structure in the data for reconstructing missing measurements and detecting anomalies. Our focus is on processing an incessant stream of large-scale data such as synchronized phasor measurements in the power grid, which is challenging due to computational complexity, memory requirement, and missing and corrupt observations. In order to mitigate these issues, a low-rank representation (LRR) model-based subspace clustering problem is formulated that can handle missing measurements and sparse outliers in the data. Then, an efficient online algorithm is derived based on stochastic approximation. The convergence property of the algorithm is established. Strategies to maintain a representative yet compact dictionary for capturing the subspace structure are also proposed. The developed method is tested on both simulated and real phasor measurement unit (PMU) data to verify the effectiveness and is shown to significantly outperform existing algorithms based on simple low-rank structure of data.

关键词： Phasor measurement units Dictionaries Clustering algorithms Data models Power measurement Monitoring Voltage measurement Anomaly detection incomplete measurement low-rank representation online algorithm subspace clustering phasor measurement unit power system monitoring synchrophasor

来源：评论

学校读者我要写书评

暂无评论

online interval scheduling to maximize total satisfaction

引用

THEORETICAL COMPUTER SCIENCE 2020年 806卷 673-688页

作者： Kobayashi, Koji M. Univ Tokyo Meguro Ku 3-8-1 Komaba Tokyo 1138902 Japan

The interval scheduling problem is one variant of the scheduling problem. In this paper, we propose a novel variant of the interval scheduling problem, whose definition is as follows: given jobs are specified by their release times, deadlines and profits. An algorithm must start a job at its release time on one of m identical machines, and continue processing until its deadline on the machine to complete the job. All the jobs must be completed and the algorithm can obtain the profit of a completed job as a user's satisfaction. It is possible to process more than one job at a time on one machine. The profit of a job is distributed uniformly between its release time and deadline, that is its interval, and the profit gained from a subinterval of a job decreases in reverse proportion to the number of jobs whose intervals intersect with the subinterval on the same machine. The objective of our variant is to maximize the total profit of completed jobs. This formulation is naturally motivated by best-effort requests and responses to them, which appear in many situations. In best-effort requests and responses, the total amount of available resources for users is always invariant and the resources are equally shared with every user. We study online algorithms for this problem. Specifically, we show that for the case where the profits of jobs are arbitrary, there does not exist an algorithm whose competitive ratio is bounded. Then, we consider the case in which the profit of each job is equal to its length, that is, the time interval between its release time and deadline. For this case, we prove that for m = 2 and m >= 3, the competitive ratios of a greedy algorithm are at most 4/3 and at most 3, respectively. Also, for each m >= 2, we show a lower bound on the competitive ratio of any deterministic algorithm. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling problem Interval scheduling online algorithm Competitive analysis Best-effort service

来源：评论

学校读者我要写书评

暂无评论

Applying "Peeling Onion" approach for competitive analysis in online scheduling with rejection

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第1期290卷 57-67页

作者： Ma, Ran Guo, Sainan Qingdao Univ Technol Sch Management Engn Qingdao 266525 Peoples R China Univ Res Ctr Smart City Construct & Management Sh Qingdao 266525 Peoples R China Henan Polytech Univ Sch Math & Informat Sci Jiaozuo 454000 Henan Peoples R China

In this study, we consider the classical online scheduling problem with rejection on identical parallel machines. In particular, a series of independent jobs arriving online over time will be scheduled on the identical machines with the flexibility of rejection, which implies that each job is either rejected with a penalty cost or accepted and scheduled on one of the identical machines. In addition, the knowledge of each job J(j), including the processing time p(j), release date r(j), and penalty cost e(j), is disclosed upon arrival of this job. Our goal is to minimize the total completion time of the accepted jobs plus the total penalty cost of the rejected jobs. For this problem, we provide a deterministic polynomial time online algorithm named as Delayed Shortest Processing Time with Rejection, shortly as DSPTR. For the sake of analyzing the competitive ratio of DSPTR, we introduce an interesting and efficient approach entitled as "Peeling Onion". By means of "Peeling Onion", we demonstrate that DSPTR is a 2-competitive online algorithm and the bound is tight. We believe that the introduction of the analysis approach "Peeling Onion" could also be applied to other online optimization problems and yield a new perspective on competitive analysis in general. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithm Competitive ratio Parallel machines Rejection

来源：评论

学校读者我要写书评

暂无评论

online Scaling of NFV Service Chains Across Geo-Distributed Datacenters

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2018年第2期26卷 699-710页

作者： Jia, Yongzheng Wu, Chuan Li, Zongpeng Le, Franck Liu, Alex Univ Hong Kong Hong Kong Hong Kong Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Calgary Calgary AB T2N 1N4 Canada IBM Thomas J Watson Res Ctr Ossining NY 10598 USA Michigan State Univ E Lansing MI 48824 USA

Network Function Virtualization (NFV) is an emerging paradigm that turns hardware-dependent implementation of network functions (i.e., middleboxes) into software modules running on virtualized platforms, for significant cost reduction and ease of management. Such virtual network functions (VNFs) commonly constitute service chains, to provide network services that traffic flows need to go through. Efficient deployment of VNFs for network service provisioning is a key to realize the NFV goals. Existing efforts on VNF placement mostly deal with offline or one-time placement, ignoring the fundamental, dynamic deployment and scaling need of VNFs to handle practical time-varying traffic volumes. This work investigates dynamic placement of VNF service chains across geo-distributed datacenters to serve flows between dispersed source and destination pairs, for operational cost minimization of the service chain provider over the entire system span. An efficient online algorithm is proposed, which consists of two main components: 1) A regularization-based approach from online learning literature to convert the offline optimal deployment problem into a sequence of one-shot regularized problems, each to be efficiently solved in one time slot and 2) An online dependent rounding scheme to derive feasible integer solutions from the optimal fractional solutions of the one-shot problems, and to guarantee a good competitive ratio of the online algorithm over the entire time span. We verify our online algorithm with solid theoretical analysis and trace-driven simulations under realistic settings.

关键词： Network function virtualization service chains online algorithm convex optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：