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

ON-line SCHEDULING WITH REJECTION ON IDENTICAL PARALLEL MACHINES

Journal of Systems Science & Complexity 2006年第3期19卷 431-435页

作者： Cuixia MIAO Yuzhong ZHANG Department of Mathematics Qufu Normal University Qufu 273165 China. Institute of Operations Research Qufu Normal University Rizhao 276826 China.

In this paper, we consider the on-line scheduling of unit time jobs with rejection on rn identical parallel machines. The objective is to minimize the total completion time of the accepted jobs plus the total penalty of the rejected jobs. We give an on-line algorithm for the problem with competitive ratio 1/2 （2 ＋√3） ≈ 1.86602.

关键词： Competitive ratio identical parallel machines on-line algorithm rejection penalty.

来源：评论

学校读者我要写书评

暂无评论

Randomized On-line Scheduling Similar Jobs to Minimize Makespan on Two Identical Processors

引用

Acta Mathematicae Applicatae Sinica 2005年第3期21卷 485-488页

作者： Dong-lei Du Faculty of Administration University of New Brunswick P.O. Box 4400 Fredericton NB E3B 5V4 Canada

In this paper we consider an on-line scheduling problem, where jobs with similar processing times within [1, r] arrive one by one to be scheduled in an on-line setting on two identical parallel processors without preemption. The objective is to nlinimize makespan. We devise a randomized on-line algorithm for this problem along with a lower bound.

关键词： on-line algorithm randomized algorithm scheduling preemption

来源：评论

学校读者我要写书评

暂无评论

On-line updating of cyclostationary tools for fault detection in rotating machines - the filter bank approach

引用

IFAC-PapersOnline 2017年第1期50卷 4702-4707页

作者： Kruczek P. Obuchowski J. Wylomanska A. Zimroz R. KGHM CUPRUM Ltd CBR Sikorskiego 2-8 Wroclaw 53-659 Poland Diagnostics and Vibro-Acoustics Science Laboratory Wrocław University of Science and Technology Wrocław Poland

The theory of cyclostationarity provides many valuable tools for fault detection in rotating machines. Cyclostationarity indicators and bi-frequency maps help to quantify fault-related modulations of vibration signals. High quality and robustness of these tools are achieved at a relatively high computational cost. Thus, industrial application of cyclostationarity is limited to off-line analysis in the post-processing stage. In this paper an on-line updating of cyclostationary tools is investigated alternatively to the moving block approach. As an exemplary cyclostationary tool the cyclic modulation spectrum is involved. The filter bank approach is proposed in order to carry out the sample-by-sample updating. We compare properties of the newly proposed method with the one based on sliding discrete Fourier transform. © 2017

关键词： cyclic modulation spectrum cyclostationarity fault detection filter bank mechanical system on-line algorithm periodic motion vibration analysis

来源：评论

学校读者我要写书评

暂无评论

On-line updating of cyclostationary tools for fault detection in rotating machines the filter bank approach

On-line updating of cyclostationary tools for fault detectio...

引用

20th World Congress of the International-Federation-of-Automatic-Control (IFAC)

作者： Kruczek, Piotr Obuchowski, Jakub Wylomanska, Agnieszka Zimroz, Radoslaw KGHM CUPRUM Ltd CBR Sikorskiego 2-8 PL-53659 Wroclaw Poland Wroclaw Univ Sci & Technol Diagnost & Vibroacoust Sci Lab Wroclaw Poland

The theory of cyclostationarity provides many valuable tools for fault detection in rotating machines. Cyclostationarity indicators and bi-frequency maps help to quantify fault related modulations of vibration signals. High quality and robustness of these tools are achieved at a relatively high computational cost. Thus, industrial application of cyclostationarity is limited to off-line analysis in the post-processing stage. In this paper an on-line updating of cyclostationary tools is investigated alternatively to the moving block approach. As an exemplary cyclostationary tool the cyclic modulation spectrum is involved. The filter bank approach is proposed in order to carry out the sample-by-sample updating. We compare properties of the newly proposed method with the one based on sliding discrete Fourier transform. (C) 2017, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.

关键词： fault detection mechanical system periodic motion vibration analysis cyclostationarity on-line algorithm filter bank cyclic modulation spectrum

来源：评论

学校读者我要写书评

暂无评论

On-line maximum-order induced hereditary subgraph problems

引用

International Transactions in Operational Research 2005年第2期12卷 185-201页

作者： Demange, Marc Paradon, Xavier Paschos, Vangelis Th. Department of Decision and Information Systems ESSEC France LAMSADE Université Paris-Dauphine CNRS UMR 7024 Paris Cedex 16 75775 Place du Maréchal De Lattre de Tassigny France

We first study the competitive ratio for the on-line version of the problem of finding a maximum-order induced subgraph satisfying some hereditary property, under the hypothesis that the input graph is revealed by clusters. Next, we focus ourselves on two of the most known instantiations of this problem: the maximum independent set and the maximum clique. Finally, we study a variant of the on-line maximum-weight induced hereditary subgraph problem. Our results can also be seen as general reductions, either from off-line problems to the corresponding on-line versions, or between on-line problems. The concept of reduction was absent, until now, from the on-line computation. © 2005 Wiley Periodicals, Inc.

关键词： Clique Hereditary property Independent set on-line algorithm Reduction

来源：评论

学校读者我要写书评

暂无评论

On-line Approximation Mining for Frequent Closed Itemsets Greater than or Equal to Size K 3

On-Line Approximation Mining for Frequent Closed Itemsets Gr...

引用

3rd IEEE/ACIS International Conference on Big Data, Cloud Computing, Data Science and Engineering (BCD)

作者： Nishina, Takumi Iwanuma, Koji Yamamoto, Yoshitaka Univ Yamanashi Dept Comp Sci & Engn Kofu Yamanashi Japan

ISBN: (纸本)9781538656051

An on-line mining of a data stream consisting of huge transactions is still a quite difficult computation problem because of an explosion of frequent itemsets. In this paper, we study a problem for mining the closed itemsets greater than or equal to size K. We give an on-line approximation algorithm, which is based on incremental intersection of transactions and rejection of closed itemsets less than size K. A closed itemset greater than or equal to size K has an intermediate property between a maximal itemset and an ordinary closed itemset. We use such a framework in order to partially solve an explosion problem in closed itemset mining. We study some theoretical properties, such as an incompleteness for frequent closed itemsets and a completeness of frequent itemsets of the on-line approximation algorithm. We also show preliminary experimental results for evaluating the performance of the proposed on-line algorithm.

关键词： on-line algorithm approximation closed itemset intersection completeness

来源：评论

学校读者我要写书评

暂无评论

Forbidden structures for efficient First-Fit chain partitioning (extended abstract)

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 173-179页

作者： Bosek, Bartłomiej Krawczyk, Tomasz Matecki, Grzegorz Theoretical Computer Science Jagiellonian University Krakow Poland

Using natural numbers for identifying chains, First-Fit algorithm processes elements of a poset P in some order and for each element it assigns the smallest natural number such that all elements with the same number form a *** a class P of posets with bounded-width we prove that there is a constant c such that all posets from P are partitioned by First-Fit into at most c chains if and only if there is a width 2 poset not induced by any poset from P. © 2011 Elsevier B.V.

关键词： Chain partition First-fit on-line algorithm Poset

来源：评论

学校读者我要写书评

暂无评论

On-line bin packing with arbitrary release times

引用

1st International Conference on Combinatorics, algorithms, Probabilistic and Experimental Methodologies

作者： Shi, Yongqiang Ye, Deshi Zhejiang Univ Coll Econ Hangzhou 310027 Peoples R China Zhejiang Univ Coll Comp Sci Hangzhou 310027 Peoples R China

ISBN: (纸本)9783540744498

We study a new variant of on-line bin packing problem, in which each item a(i) is associated with a size a(i) and also a release time r(i) so that it must be placed at least r(i) above from the bottom of a bin. Items arrive in turn and must be assigned without any knowledge of subsequence items. The goal is to pack all items into unit-size bins using the minimum number of bins. We study the problem with all items have equal size. First, we show that the ANY FIT algorithm cannot be approximated within any constant. Then we present a best possible on-line algorithm with asymptotic competitive ratio of 2.

关键词： bin packing arbitrary release time on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Mapping the Virtual Networks with Stochastic Bandwidth Resource Request in Multi-datacenters

Mapping the Virtual Networks with Stochastic Bandwidth Resou...

引用

International Conference on Advanced Intelligence and Awareness Internet (AIAI 2011)

作者： Sun, Gang Yu, Hongfang Anand, Vishal Li, Lemin Cai, Yanyang Di, Hao Univ Elect Sci & Technol China Sch Commun & Informat Engn Chengdu 610054 Peoples R China SUNY Coll Brockport Dept Comp Sci Brockport NY 14420 USA

ISBN: (纸本)9781849194716

Network virtualization allows the design of multiple diverse virtual overlay network architectures over a common physical infrastructure. A key issue in designing such virtual networks (VN) is the mapping of the VN onto the underlying substrate network. Accordingly, many research works have focused on the VN mapping problem. However, these works only consider the case where the VNs require deterministic amount of network resources. Some other works even deal with the dynamic resource demand by using over provisioning, which is simple but inefficient. In this paper, we investigate the online stochastic VN mapping (StoVNM) problem in multi-datacenters, in which the VN requests follow a Poisson distribution and the associate VN bandwidth demands follow a Normal distribution. We formulate the StoVNM problem as an optimization problem with the objective of minimizing mapping cost and load-balancing. Since the VN mapping problem is NP-hard we devise a sliding window technique based on heuristic algorithm w-StoVNM for tackling this NP-hard problem efficiently. Through extensive simulations we demonstrate the effectiveness of the proposed approach compared to traditional VN mapping solutions in terms of VN mapping cost, blocking ratio and total net revenue in the long term.

关键词： virtual network on-line algorithm stochastic virtual network mapping

来源：评论

学校读者我要写书评

暂无评论

On-line Scheduling with a Monotonous Subsequence Constraint 1

引用

11th International Frontiers of algorithmics Workshop (FAW)

作者： Luo, Kelin Xu, Yinfeng Zhang, Huili Luo, Wei Xi An Jiao Tong Univ Sch Management Xian 710049 Shaanxi Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Shaanxi Peoples R China Univ Calif Santa Barbara Dept Geog Berkeley CA USA

ISBN: (数字)9783319596051

ISBN: (纸本)9783319596051;9783319596044

In this paper, we study a new on-line scheduling problem that each server has to process a monotonous request subsequence. The customer requests are released over-list, and the operator has to decide whether or not to accept the current request and arrange it to a server immediately. The goal of this paper is to find a strategy which accepts the maximal requests. When the number of servers k is less than that of the request types m, we give several lower bounds for this problem. Also, we present the optimal strategy for k = 1 and k = 2 respectively.

关键词： Scheduling on-line algorithm Competitive analysis Monotonous subsequence

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：