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

online k-color spanning disk problems

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第2期46卷 1-14页

作者： Wang, Yin Xu, Yinfeng Zhang, Huili Tong, Weitian Xi An Jiao Tong Univ Sch Management State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Georgia Southern Univ Dept Comp Sci Statesboro GA 30458 USA

Inspired by the applications in on-demand manufacturing, we introduce the online k-color spanning disk problem, the first online model for color spanning problems to the best of our knowledge. Given a set P of n colored points in a plane, with each color chosen from a set C of m <= n colors, the online k-color spanning disk problem determines the location of the center that minimizes the accumulated radius of theminimum spanning disks for a sequence of color sets, denoted by delta = < C-1, C-2,..., CT >, C-t subset of C, |C-t| >= k, t epsilon{1, 2,..., T}, as they are presented online. Here, a minimum spanning disk for a color set means a disk contains at least one point of each color. We construct a special instance to establish a lower bound on the performance of any online algorithms. Then, an O(nm log n)-time Voronoi-diagram-based algorithm is designed such that its competitive ratio matches the problem ' s lower bound. This implies our algorithm is theoretically the best possible in terms of the competitive ratio. We also introduce and study a variant, named the online balanced k-color spanning disk problem, for which a non-trivial lower bound and a best possible algorithm are presented.

关键词： Minimum color spanning disk Voronoi diagram online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

An Improved online algorithm for the online Preemptive Scheduling of Equal-Length Intervals on a Single Machine with Lookahead

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2015年第6期32卷 1550047-1550047页

作者： Li, Wenjie Yuan, Jinjiang Luoyang Normal Univ Sch Math Sci Luoyang 471022 Henan Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

This paper studies the online preemptive scheduling of equal-length intervals on a single machine with lookahead. Let p be the length (processing time) of all intervals. In the problem, at every time point t, online algorithms can foresee all the intervals that will arrive in the time segment (t,t+L) for a certain L. When L = p, Zheng et al. [Computers & Operations Research, 2013] established a lower bound of root 2 and provided an online algorithm with a competitive ratio of 3. In this paper, we provide for this problem an improved online algorithm with a competitive ratio of 2.

关键词： Scheduling online algorithm equal-length intervals lookahead

来源：评论

学校读者我要写书评

暂无评论

ROPW: An online Trajectory Compression algorithm

ROPW: An Online Trajectory Compression Algorithm

引用

26th International Conference on Database Systems for Advanced Applications (DASFAA)

作者： Li, Sirui Zhang, Kaiqi Yin, Hongbo Yin, Dan Zu, Hongquan Gao, Hong Harbin Inst Technol Harbin 150001 Heilongjiang Peoples R China

ISBN: (纸本)9783030732158;9783030732165

In smart phones, vehicles and wearable devices, GPS sensors are ubiquitous, which can collect a large amount of valuable trajectory data by tracking moving objects. Analysis of this valuable trajectory data can benefit many practical applications, such as route planning and transportation optimization. However, unprecedented large-scale GPS data poses a challenge to the effective storage of trajectories. Therefore, the necessity of trajectory compression (also called trajectory sampling) is reflected. However, the latest compression methods usually perform unsatisfactorily in terms of space-time complexity or compression rate, which leads to rapid exhaustion of memory, computing, storage, and energy. In response to this problem, this paper proposes an online trajectory compression algorithm (ROPW algorithm) with error bounded that traverses the sliding window backwards. This algorithm has significantly improved the trajectory compression rate, and its average time complexity and space complexity is O(NlogN) and 0(1) respectively. Finally, we conducted experiments on three real data sets to verify that the ROPW algorithm performed very well in terms of compression rate and time efficiency.

关键词： online algorithm Trajectory compression Sliding window Reverse traversal

来源：评论

学校读者我要写书评

暂无评论

online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2023年第11期74卷 2432-2454页

作者： Wei, Qi Wu, Yong Cheng, T. C. E. Sun, Fengxin Jiang, Yiwei Ningbo Univ Finance & Econ Ningbo Peoples R China Hong Kong Polytech Univ Kowloon Hong Kong Peoples R China Ningbo Univ Technol Ningbo Peoples R China Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Hangzhou Peoples R China Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Sch Management & E Business Hangzhou 310018 Peoples R China

We consider online hierarchical scheduling on m identical machines in shared manufacturing to minimize the total completion time. Each job has a unit-size processing time. The jobs arrive one by one and must be assigned to one of the m machines before the next job arrives. The jobs with a lower hierarchy can only be processed on the first k machines, 1 <= k <= m-1, and the jobs with a higher hierarchy can be processed on any one of the m machines. We first show that the lower bound of the problem is at least 1+min{1/m-k+1,max{2/k inverted right perpendiculexpressionr s right ceiling +3k+2m+4/ inverted right perpendiculexpressionr s right ceiling ,2/k left floor s right floor +3k+2m+4/ left floor s right floor }}, where s=root 2m+4/k. Proposing a greedy algorithm, we show that its tight competitive ratio is 1+2(m-k)k/m(root(4m-3k)k root+k)by analyzing a set of instances that must contain a worst-case instance, which is different from the general method of calculating the competitive ratio. In addition, for the case where k = 1, we present an improved online algorithm with a tight competitive ratio of 1+max{2/ inverted right perpendiculexpressionr root 2m+4 root right ceiling +2m+4/ inverted right perpendiculexpressionr root 2m+4 root right ceiling +3,2/ left floor root 2m+4 right floor +2m+4/ left floor root 2m+4 root right floor +3}, which is optimal for 2 <= m <= 5. Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.

关键词： Share manufacturing hierarchical scheduling online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Single-Machine online Scheduling with Non-delayed Processing Constraint and Deterioration Effect in the Steel Rolling Process

引用

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 2024年 1-18页

作者： Meng, Lan-Meng Ma, Ran Zhang, Yu-Zhong Qingdao Univ Technol Sch Management Engn Qingdao 266520 Shandong Peoples R China Qufu Normal Univ Inst Operat Res Rizhao 276826 Shandong Peoples R China

This paper focuses on the online production scheduling of the steel rolling processes in a single-machine environment with objective to minimize the maximum delivery completion time of all of the jobs, subject to the job deterioration effect and non-delayed processing constraint. The deterioration is reflected in the processing time of the job. Specifically, the job's processing time is a linear function of its start time and can be denoted as p(j )= a(j )(A+Bt), where A > 0, B > 0 and a(j) > 0 represents the job's processing deterioration rate. For this problem, we firstly show that the competitive ratio of any deterministic online algorithm is not less than 1+ Ba-max . Then, we design an online algorithm called Modified-Largest Delivery Time (M-LDT) and show the algorithm M-LDT is (1+alpha)(1+ Ba-max)-competitive, where is the positive root of alpha(2) - alpha -1 =0. Finally, we use the combination of graphs and tables to give the simulation results of multiple instances, and then verify the correctness and effectiveness of our proposed online algorithm.

关键词： Scheduling online algorithm Delivery time Deteriorating effect Non-delayed processing constraint

来源：评论

学校读者我要写书评

暂无评论

online Optimal Service Selection, Resource Allocation and Task Offloading for Multi-Access Edge Computing: A Utility-Based Approach

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第7期22卷 4150-4167页

作者： Chu, Weibo Yu, Peijie Yu, Zhiwen Lui, John C. S. Lin, Yi Northwestern Polytech Univ Xian 710060 Shaanxi Peoples R China Chinese Univ Hong Kong Shatin Hong Kong Peoples R China

Multi-access edge computing promises satisfactory user experience by offloading tasks to the MEC server deployed at the network edge. However, since the MEC server is often resource-limited as compared to the cloud infrastructure, how to efficiently utilize its resources for system performance optimization becomes a challenge. In this paper, we study this problem with the aim at maximizing user's QoE through jointly optimizing service selection, computation resource allocation and task offloading decision, which is less studied in existing literature. We formulate a mixed-integer nonlinear programming problem (MINLP) for the task and propose a utility-based approach together with a low-complexity resource-efficiency based heuristic to address the problem. We consider realistic settings, where centralized solutions may not apply and an optimal mechanism needs to adapt as system operates. A distributed algorithm based on the Lagrangian-dual based decomposition theory is proposed, and we prove all sub-problems derived can be efficiently solved. In line with the current VM technology, we develop a cost-aware online algorithm that explicitly incorporates the cost of service switches into service selection and resource allocation. We evaluate our mechanism through both synthetic and trace-driven simulations, and results indicate they are effective as compared to representative baseline algorithms.

关键词： Task analysis Servers Resource management Quality of experience System performance Computational modeling Multi-access edge computing service selection computation resource allocation task offloading online algorithm

来源：评论

学校读者我要写书评

暂无评论

online scheduling of two-machine flowshop with lookahead and incompatible job families

引用

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

作者： Qian, Xia Xingong, Zhang Chongqing Normal Univ Sch Math Sci Chongqing 401331 Peoples R China

This paper considers online scheduling on two unit flowshop machines, which there exists unbounded parallel-batch scheduling with incompatible job families and lookahead intervals. The unit flowshop machine means that the processing time of any job on each machine is unit processing time. The objective is to minimize the maximum completion time. The lookahead model means that an online algorithm can foresee the information of all jobs arriving in time interval (t, t + beta] at time t. There exist incompatible job families, that is, jobs belonging to different families cannot be processed in the same batch. In this paper, we address the lower bound of the proposed problem, and provide a best possible online algorithm of competitive ratio 1+ alpha f for 0 <= beta < 1, where alpha f is the positive root of the equation (f + 1)alpha(2) + (beta + 2)alpha + beta - f = 0 and f is the number of incompatible job families which is known in advance.

关键词： online algorithm Lookahead interval Incompatible job families Parallel-batch scheduling Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal online Bin Packing algorithms for Some Cases with Two Item Sizes

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2023年第9期E106A卷 1100-1110页

作者： Fujiwara, Hiroshi Kawaguchi, Masaya Takizawa, Daiki Yamamoto, Hiroaki Shinshu Univ Dept Elect & Comp Engn Nagano 3808553 Japan Saitama Univ Grad Sch Sci & Engn Saitama 3388570 Japan East Japan Railway Co Tokyo 1510053 Japan

The bin packing problem is a problem of finding an assignment of a sequence of items to a minimum number of bins, each of capacity one. An online algorithm for the bin packing problem is an algorithm that irrevocably assigns each item one by one from the head of the sequence. Gutin, Jensen, and Yeo (2006) considered a version in which all items are only of two different sizes and the online algorithm knows the two possible sizes in advance, and gave an optimal online algorithm for the case when the larger size exceeds 1/2. In this paper we provide an optimal online algorithm for some of the cases when the larger size is at most 1/2, on the basis of a framework that facilitates the design and analysis of algorithms. key words: bin packing problem, online algorithm, competitive analysis, mathematical optimization

关键词： bin packing problem online algorithm competitive analysis mathematical optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A cost-driven online auto-scaling algorithm for web applications in cloud environments

引用

KNOWLEDGE-BASED SYSTEMS 2022年 244卷 108523-108523页

作者： Si, Wen Pan, Li Liu, Shijun Shandong Univ Sch Software 1500 Shunhua Rd Jinan 250101 Shandong Peoples R China

Today, many web application service providers rely on clouds to deploy applications to serve users. Generally, request arrivals faced by web applications are dynamic and uncertain. When a service provider deploys web applications in clouds, for saving costs, it needs to flexibly rent cloud VM (Virtual Machine) instances based on dynamic request arrivals. However, renting an instance too early may incur more rental fees for the new instance being added incorrectly due to few future requests, and renting an instance too late may incur more penalty fees for SLA (service-level agreement) violations due to too many future requests, which indicates that an arbitrary instance scaling decision will incur more costs. For making optimal instance scaling decisions, future request arrival rate curves are needed, but it is generally very hard to predict them precisely. To solve this problem, in this paper, we propose a cost-driven online auto-scaling algorithm which can make optimized instance rental decisions without requiring future knowledge. We show theoretically that the proposed algorithm can achieve a guaranteed competitive ratio which is less than 2. Eventually, we verify the effectiveness of our online auto-scaling algorithm via extensive experiments using workload data which can simulate real end users. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Cloud computing Web application Cost optimization online algorithm Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：