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

online scheduling in a parallel batch processing system to minimize makespan using restarts

THEORETICAL COMPUTER SCIENCE 2007年第1-3期374卷 196-202页

作者： Fu, Ruyan Tian, Ji Yuan, Jinjiang Lin, Yixun Zhengzhou Univ Dept Math Zhengzhou 450052 Peoples R China

We consider an online scheduling problem in a parallel batch processing system with jobs in a batch being allowed to restart. online means that jobs arrive over time, and all jobs' characteristics are unknown before their arrival times. A parallel batch processing machine can handle up to several jobs simultaneously. All jobs in a batch start and complete at the same time. The processing time of a batch is equal to the longest processing time of jobs in the batch. We are allowed to restart a batch, that is, a running batch may be interrupted, losing all the work done on it. Jobs in the interrupted batch are released and become independently unscheduled jobs. We deal with an unbounded model where each batch's capacity is sufficiently large. We provide a linear online algorithm with competitive ratio 3/2 for the problem. We also show that the considered problem has no online algorithm using restarts with competitive ratio less than (5 - root 5)/2. (C) 2007 Elsevier B.V. All rights reserved.

关键词： single machine scheduling parallel batch online algorithm restart competitive ratio

来源：评论

学校读者我要写书评

暂无评论

LPT online strategy for parallel-machine scheduling with kind release times

引用

OPTIMIZATION LETTERS 2016年第1期10卷 159-168页

作者： 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

In this paper, we introduce a new environment of online scheduling in which jobs have kind release times (KRT). Under the KRT assumption, no jobs can be released when all of the machines are busy. Then we study the competitive ratio of the online LPT algorithm to minimize makespan on identical parallel machines under the KRT assumption. The online LPT algorithm can be described as follows: At any time a machine becomes available for processing, schedule an available job with the largest processing time. When , we show that LPT is a best possible online algorithm with a competitive ratio of . For each , we show that LPT has a competitive ratio of . We also show that LPT is a best possible online dense-algorithm, where an online algorithm is called dense if it always immediately assigns currently available jobs to one of the idle machines as long as there are at least two idle machines. Furthermore, for , we show that no online algorithms have a competitive ratio less than . Comparing to the known result of Chen and Vestjens (Operations Research Letters 1997), which establishes the -competitiveness of LPT, the results in this paper imply that the KRT assumption can help to improve the competitive ratio of LPT for two parallel machines.

关键词： Scheduling online algorithm Makespan Kind release time LPT strategy

来源：评论

学校读者我要写书评

暂无评论

Soundprism: An online System for Score-Informed Source Separation of Music Audio

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2011年第6期5卷 1205-1215页

作者： Duan, Zhiyao Pardo, Bryan Northwestern Univ Dept Elect Engn & Comp Sci Evanston IL 60208 USA

Soundprism, as proposed in this paper, is a computer system that separates single-channel polyphonic music audio played by harmonic sources into source signals in an online fashion. It uses a musical score to guide the separation process. To the best of our knowledge, this is the first online system that addresses score-informed music source separation that can be made into a real-time system. The proposed system consists of two parts: 1) a score follower that associates a score position to each time frame of the audio performance;2) a source separator which reconstructs the source signals for each time frame, informed by the score. The score follower uses a hidden Markov approach, where each audio frame is associated with a 2-D state vector (score position and tempo). The observation model is defined as the likelihood of observing the frame given the pitches at the score position. The score position and tempo are inferred using particle filtering. In building the source separator, we first refine the score-informed pitches of the current audio frame by maximizing the multi-pitch observation likelihood. Then, the harmonics of each source's fundamental frequency are extracted to reconstruct the source signal. Overlapping harmonics between sources are identified and their energy is distributed in inverse proportion to the square of their respective harmonic number. Experiments on both synthetic and human-performed music show both the score follower and the source separator perform well. Results also show that the proposed score follower works well for highly polyphonic music with some degree of tempo variations.

关键词： Multi-pitch estimation online algorithm score following source separation

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for online time series search and one-way trading with interrelated prices

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第2期23卷 159-166页

作者： Zhang, Wenming Xu, Yinfeng Zheng, Feifeng Dong, Yucheng Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China

The basic models of online time series search and one-way trading are introduced by El-Yaniv et al. in algorithmica 30(1), 101-139 (2001) where it is assumed that the prices are bounded within interval [m,M] (0 < m < M). In this paper, we consider another case where every two consecutive prices are interrelated, that is, the variation range of each price depends on its preceding price. We present optimal deterministic online algorithms for the two problems, respectively. According to one conclusion in algorithmica 30(1), 101-139 (2001), we further point out that for the case we considered, an optimal deterministic algorithm for the one-way trading problem can be regarded as an optimal randomized one for the time series search problem, and randomization is useless for the one-way trading problem.

关键词： Time series search One-way trading online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal online pricing with network externalities

引用

INFORMATION PROCESSING LETTERS 2012年第4期112卷 118-123页

作者： Ehsani, Shayan Ghodsi, Mohammad Khajenezhad, Ahmad Mahini, Hamid Nikzad, Afshin Sharif Univ Technol Dept Comp Engn Tehran Iran Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

We study the optimal pricing strategy for profit maximization in presence of network externalities where a decision to buy a product depends on the price offered to the buyer and also on the set of her friends who have already bought that product. We model the network influences by a weighted graph where the utility of each buyer is the sum of her initial value on the product, and the linearly additive influence from her friends. We assume that the buyers arrive online and the seller should offer a price to each buyer when she enters the market. We also take into account the manufacturing cost. In this paper, we first assume that the monopolist defines a unique price for the product and commits to it for all buyers. In this case, we present an FPTAS algorithm that approximates the optimal price with a high probability. We also prove that finding the optimum price is NP-hard. Second, we consider a market with positive network externalities and assume that the monopolist could offer a private price to each customer. We prove that this problem is also hard to approximate for linear influences. On the positive side, we present a polynomial time algorithm for the problem when influences are symmetric. At last, we show that the seller has more ability to extract influences with price discrimination. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Social networks Pricing Approximation algorithm online algorithm Market

来源：评论

学校读者我要写书评

暂无评论

MVOPFAD: Multiview online Passenger Flow Anomaly Detection

引用

IEEE SENSORS JOURNAL 2024年第9期24卷 14668-14681页

作者： Tan, Erlong Yan, Haoyang Zhao, Kaiqi Ma, Xiaolei Ma, Zhenliang Du, Yuchuan Beihang Univ Sch Transportat Sci & Engn Beijing 100191 Peoples R China Beihang Univ Key Lab Intelligent Transportat Technol & Syst Minist Educ Beijing 100191 Peoples R China KTH Royal Inst Technol Dept Civil & Architectural Engn S-10044 Stockholm Sweden Tongji Univ Minist Educ Key Lab Rd & Traff Engn Shanghai 201804 Peoples R China

Prompt and accurate identification of anomalies in passenger flow within metro systems is crucial for safety, security, and operational efficiency. However, traditional anomaly detection methods often struggle to achieve high accuracy and low latency when constrained by limited labeled data for online applications. This study presents a straightforward yet effective online anomaly detection framework, termed multiview online passenger flow anomaly detection (MVOPFAD), to address these difficulties in a data-driven manner. Specifically, to reduce the computational burden and meet online requirements, we particularly propose an elastic extreme studentized deviate (EESD) model accounting for the characteristic of abnormal passenger flow. Concurrently, an improved shifted wavelet tree (ISWT) is employed to effectively capture various passenger flow features. It is joined by the implementation of ensemble learning techniques and EESD to further enhance the accuracy and robustness of our detection model. To evaluate the performance of our proposed framework, we conducted a comprehensive series of experiments utilizing data collected from the automated fare collection (AFC) system integrated into the Beijing Metro network. Our proposed MVOPFAD demonstrates significant superiority over the other three types of methods across all evaluation metrics. In particular, it yields a 15.49% increase in precision and a 9.71% rise in the F2-score compared to the second-best model for detecting outbound passenger flow anomalies. Additionally, our model incurs lower computational cost than deep learning models and machine learning models. The experimental results strongly suggest the feasibility of online implementation, thereby demonstrating the practicality and effectiveness of our proposed model.

关键词： Anomaly detection online algorithm passenger flow urban metro system

来源：评论

学校读者我要写书评

暂无评论

Obtaining online approximation algorithms for facility dispersion from offline algorithms

引用

NETWORKS 2006年第4期47卷 206-217页

作者： Rosenkrantz, Daniel J. Tayi, Giri K. Ravi, S. S. SUNY Albany Dept Comp Sci Albany NY 12222 USA SUNY Albany Sch Business Dept Management Sci & Informat Syst Albany NY 12222 USA

Facility dispersion problems arise in the context of placing obnoxious facilities and retail outlets. In the off line version of such a problem, the input consists of a complete graph on n nodes, a nonnegative weight (distance) for each edge, and the number k <= n of facilities to be placed. The goal is to choose a facility placement consisting of k nodes so as to maximize a given measure of the distances among the facilities. Here, we consider an online version of the problem where the value of k is not known apriori;instead, requests for facilities arrive one at a time. It is also required that previously placed facilities cannot be moved or eliminated. Our main result is that for any objective that satisfies two properties, namely monotonicity and graceful degradation, any off line approximation algorithm with a performance guarantee p can be used to develop an algorithm with competitive ratio c rho for the online version, where c is a constant independent of the problem instance. Objectives for which our result applies include the average edge weight and average weight of a star subgraph. The result holds even when the edge weights do not satisfy the triangle inequality. We also identify dispersion objectives for which the offline and online versions have different behaviors when only one of the above two properties Is satisfied. (C) 2006 Wiley Periodicals, Inc.

关键词： facility dispersion offline algorithm online algorithm approximation ratio competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Mobile coupons delivery problem: Postponable online multi-constraint knapsack

引用

DECISION SUPPORT SYSTEMS 2019年 116卷 13-25页

作者： Kang, Keumseok Altinkemer, Kemal Hur, Inkyoung Florida Int Univ Coll Business Miami FL 33199 USA Purdue Univ Krannert Sch Management W Lafayette IN 47907 USA Nova Southeastern Univ Coll Engn & Comp Ft Lauderdale FL 33314 USA

We study the mobile coupons delivery problem (MCDP) in a push-based location based advertisement where an advertiser proactively sends mobile coupons to prospective customers on behalf of stores based on the customers' location and preferences. MCDP provides a new capability called postponable selection that enables an advertiser to better capitalize on the plethora of customer information provided by mobile phone users through network service providers. Postponable selection allows a customer to be reconsidered for selection for coupon delivery (i.e. postponed) as more information becomes available. We formulate MCDP as a new problem category referred to as the postponable online multi-constraint knapsack. We propose a single threshold-type algorithm with different design options and conduct extensive computational experiments to discuss the effectiveness of our algorithm as well as the benefit of postponable selection. Our experimental results show that the proposed algorithm outperforms the First-Come-First-Serve heuristic by 46% and postponable selection additionally improves performance by 4% on average.

关键词： Mobile coupons delivery problem online multi-constraint knapsack problem online algorithm Postponable selection Computational experiment

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

online unit covering in Euclidean space

引用

THEORETICAL COMPUTER SCIENCE 2020年 809卷 218-230页

作者： Dumitrescu, Adrian Ghosh, Anirban Toth, Csaba D. Univ Wisconsin Dept Comp Sci Milwaukee WI 53201 USA Univ North Florida Sch Comp Jacksonville FL 32224 USA Calif State Univ Northridge Dept Math Los Angeles CA USA Tufts Univ Dept Comp Sci Medford MA 02155 USA

We revisit the online UNIT COVERING problem in higher dimensions: Given a set of n points in R-d, that arrive one by one, cover the points by balls of unit radius, so as to minimize the number of balls used. In this paper, we work in R-d using the Euclidean distance. (I) We give an online deterministic algorithm with competitive ratio O(1.321(d)), thereby improving on the previous record, O(2(d)d logd), due to Charikar et al. (2004), by an exponential factor. In particular, the competitive ratios are 5 in the plane and 12 in 3-space (the previous ratios were 7 and 21, respectively). For d = 3, the ratio of our online algorithm matches the ratio of the current best offline algorithm for the same problem due to Biniaz et al. (2017), which is remarkable (and rather unusual). (II) We show that the competitive ratio of every deterministic online algorithm for UNIT COVERING in R-d under the L-2 norm is at least d + 1 for every d >= 1. This greatly improves upon the previous best lower bound, Omega(logd/ log loglogd), due to Charikar et al. (2004). (III) We generalize the above result to UNIT COVERING in R-d under the L-C norm, where C is a centrally symmetric convex body, via the illumination number. (IV) We obtain lower bounds of 4 and 5 for the competitive ratio of any deterministic algorithm for online UNIT COVERING in R-2 and R-3, respectively;the previous best lower bounds were 3 for both cases. (V) When the input points are from the square or hexagonal lattice in R-2, we give deterministic online algorithms for UNIT COVERING with an optimal competitive ratio of 3. For the cubic lattice in R-3, we give a deterministic online algorithm with a competitive ratio of 5. (C) 2019 Elsevier B.V. All rights reserved.

关键词： online algorithm Unit covering Unit clustering Competitive ratio Illumination number Newton number

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：