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

An on-line algorithm for checkpoint placement

IEEE TRANSACTIONS ON COMPUTERS 1997年第9期46卷 976-985页

作者： Ziv, A Bruck, J CALTECH PASADENACA 91125

Checkpointing enables us to reduce the time to recover from a fault by saving intermediate states of the program in a reliable storage. The length of the intervals between checkpoints affects the execution time of programs. On one hand, long intervals lead to long reprocessing time, while, on the other hand, too frequent checkpointing leads to high checkpointing overhead, In this paper, we present an on-line algorithm for placement of checkpoints. The algorithm uses knowledge of the current cost of a checkpoint when it decides whether or not to place a checkpoint. The total overhead of the execution time when the proposed algorithm is used is smaller than the overhead when fixed intervals are used. Although the proposed algorithm uses only on-line knowledge about the cost of checkpointing, its behavior is close to the of-line optimal algorithm that uses a complete knowledge of checkpointing cost.

关键词： fault-tolerant computing checkpointing on-line algorithm performance optimization

来源：评论

学校读者我要写书评

暂无评论

on-line algorithm for optimal 3D path planning

引用

COMPUTER APPLICATIONS IN ENGINEERING EDUCATION 2012年第4期20卷 713-720页

作者： Hun, Chien-Wan Chen, Hun-Chen Hwang, Ming-Fung Natl United Univ Dept Elect Engn Miaoli Taiwan Natl United Univ Dept Mech Engn Miaoli Taiwan Da Yeh Univ Liberal Arts Ctr Changhua Taiwan

The issues of automatic car operation aiming at in an unknown complex terrain are the most effective path planning and the obstacles avoiding in this complex terrain. For that, an on-line algorithm for guiding a mobile object in an unexplored terrain filled with convex polygonal obstacles is presented. The mobile object was taken as a point-size auto equipped with a sensor system, which is used to detect previously all visible parts of the obstacles surrounding it. Both the visibility and the tangent graph were modified and used in this algorithm to construct the basic concept. At each stage, the next subgoal was selected from local information provided by the sensor. Furthermore, in order to expand the algorithm to handle nonconvex polygonal obstacles and mazes, it was modified by adding backtracking and by removing visited vertices. The algorithm was implemented in MATLAB language, and several numerical examples are shown to evaluate its feasibility. Moreover, the convergence of the algorithm was examined using the visibility graph, and the performance of the algorithm was evaluated by simply comparing with other algorithms for both the length of the path and the traveling time from the initial point to the target point. (C) 2010 Wiley Periodicals, Inc. Comput Appl Eng Educ 20: 713720, 2012

关键词： on-line algorithm convex polygonal obstacle path planning

来源：评论

学校读者我要写书评

暂无评论

on-line algorithm for extraction of specific signals with temporal structure

引用

14th International Conference on Neural Information Processing (ICONIP 2007)

作者： Santana, Ewaldo Cavalcante, Andre B. Santos, Marcio de O. Barros, Allan Freire, R. C. S. Univ Fed Campina Grande Campina Grande PB Brazil Fac Atenas Maranhense Sao Luis Brazil Univ Fed Maranhao Sao Luis Brazil

ISBN: (纸本)9783540691594

Blind source separation techniques based on statistical independence criteria require a large number of data samples to estimate higher-order statistics. Thus, those techniques are not suitable to either on-line adaptive modeling. In this work we developed both an online and a batch algorithms for semi-blind extraction of a desired source signal with temporal structure from linear mixtures. Here, we do not assume that sources are statistically independent but we use an a prion information about the autocorrelation function of primary sources to extract the desired signal. Also, we develop an analytical framework to guarantee convergence of the online algorithm based on second-order statistics. Extensive computer simulations and real data applications confirm the validity and high performance of the proposed algorithms.

关键词： on-line algorithm ICA BSS

来源：评论

学校读者我要写书评

暂无评论

The Complexity and on-line algorithm for Automated Storage and Retrieval System with Stacker Cranes on One Rail

引用

Journal of Systems Science & Complexity 2016年第5期29卷 1302-1319页

作者： GAO Qiang LU Xiwen Department of Mathematics East China University of Science and Technology

This paper considers an on-line scheduling and routing problem concerning the automated storage and retrieval system from tobacco industry. In this problem, stacker cranes run on one common rail between two racks. Multiple input/output-points are located at the bottom of the racks. The stacker cranes transport bins between the input/output-points and cells on the racks to complete requests generated over time. Each request should be accomplished within its response time. The objective is to minimize the time by which all the generated requests are completed. Under a given physical layout, the authors study the complexity of the problem and design on-line algorithms for both one-stacker-crane model and two-stacker-crane model. The algorithms axe validated by instances and numerical simulations.

关键词： Automated storage and retrieval system NPohard on-line algorithm routing scheduling.

来源：评论

学校读者我要写书评

暂无评论

A best possible on-line algorithm for scheduling on uniform parallel-batch machines

引用

THEORETICAL COMPUTER SCIENCE 2018年 740卷 68-75页

作者： Li, Wenhua Chai, Xing Song, Yali Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Hennan Key Lab Financial Engn Zhengzhou 450001 Henan Peoples R China

An on-line scheduling problem on m uniform parallel-batch machines to minimize the makespan is considered in this paper. Each machine can process infinite jobs as a batch at a time. Jobs arrive over time and have equal lengths denoted by 1. Compared to parallel machines, uniform machines are more difficult to deal with because they have different processing speeds. There are two types of machines in our model. The lower bound on the competitive ratio is characterized by some complicated algebraic equations. And a best possible on-line algorithm matching the lower bound is constructed and proved in this paper. (C) 2018 Elsevier B.V. All rights reserved.

关键词： on-line algorithm Uniform machines Parallel-batch Makespan Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

DOAMI: A distributed on-line algorithm to minimize interference for routing in wireless sensor networks

引用

THEORETICAL COMPUTER SCIENCE 2019年 774卷 1-13页

作者： Zhang, Kejia Han, Qilong Cai, Zhipeng Yin, Guisheng Lin, Junyu Harbin Engn Univ Coll Comp Sci & Technol Harbin 15001 Heilongjiang Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

This paper investigates the Minimizing-Interference-for-Multiple-Paths (MIMP) problem for routing with minimum interference in wireless sensor networks, which is defined as: Given k routing requests {s(1), t(1)},..., {s(k), t(k)}, find k paths connecting these routing requests with minimum (wireless) interference. A key point to solve this problem is how to quantify interference level among multiple routing paths. However, all the existing metrics cannot measure interference precisely under some certain circumstances, e.g., some of the routing paths have common nodes or links. This paper proposes a metric that can measure interference precisely among any set of paths, even though these paths have some nodes or links in common. For this proposed metric, the MIMP problem is NP-hard even for k = 2. A heuristic Distributed on-line algorithm for Minimizing Interference (DOAMI) is given to solve the MIMP problem. DOAMI has good communication and time complexity in theory, whose efficiency is also verified by simulation results. (C) 2016 Published by Elsevier B.V.

关键词： Interference metric Minimizing interference on-line algorithm Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2009年第2期17卷 206-213页

作者： Yuan, Jinjiang Li, Shisheng Tian, Ji Fu, Ruyan Zhengzhou Univ Dept Math Zhengzhou 450052 Henan Peoples R China

We consider a single batch machine on-line scheduling problem with delivery times. In this paper on-line means that jobs arrive over time and the characteristics of jobs are unknown until their arrival times. Once the processing of a job is completed it is delivered to the destination. The objective is to minimize the time by which all jobs have been delivered. For each job J(j), its processing time and delivery time are denoted by p(j) and q(j), respectively. We consider two restricted models: (1) the jobs have small delivery times, i.e., for each job J(j), q(j) <= p(j);(2) the jobs have agreeable processing and delivery times, i.e., for any two jobs J(i) and J(j), p(i) > p(j) implies q(i) >= q(j). We provide an on-line algorithm with competitive ratio (root 5 + 1)/2 for both problems, and the results are the best possible.

关键词： Scheduling on-line algorithm Parallel-batching Delivery time

来源：评论

学校读者我要写书评

暂无评论

A best on-line algorithm for single machine scheduling with small delivery times

引用

THEORETICAL COMPUTER SCIENCE 2008年第1-3期393卷 287-293页

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

We consider a single machine on-line scheduling problem with delivery times. All jobs arrive over time. Each job's characteristics, such as processing time and delivery time, become known at its arrival time. Once the processing of a job is completed we deliver it to the destination by a vehicle. The objective is to minimize the time by which all jobs have been delivered. In this paper, we assume that all jobs have small delivery times, i.e., for each job J(j), q(j) <= p(j), where p(j) and q(j) denote the processing time and the delivery time of J(j), respectively. We provide an on-line algorithm with a competitive ratio of root w2, and the result is the best possible. (C) 2008 Published by Elsevier B.V.

关键词： scheduling on-line algorithm single machine delivery time

来源：评论

学校读者我要写书评

暂无评论

An improved randomized on-line algorithm for a weighted interval selection problem

引用

JOURNAL OF SCHEDULING 2004年第4期7卷 293-311页

作者： Miyazawa, H Erlebach, T ETH Comp Engn & Networks Lab TIK CH-8092 Zurich Switzerland Univ Tokyo Grad Sch Engn Dept Math Engn & Informat Phys Bunkyo Ku Tokyo 1138656 Japan

Given a set of weighted intervals, the objective of the weighted interval selection problem (WISP) is to select a maximum-weight subset such that the selected intervals are pairwise disjoint. We consider on-line algorithms that process the intervals in order of non-decreasing left endpoints. Preemption is allowed, but rejections are irrevocable. This problem has natural applications in various scheduling problems. We study the class of monotone instances of WISP, i.e., we require that the order of right endpoints of the given intervals coincides with that of the left endpoints. This class includes the case where all intervals have the same length. For monotone instances of WISP, the best possible competitive ratio for deterministic on-line algorithms is known to be 1/4. It has long been an open question whether there exists a randomized algorithm with better competitive ratio. In this paper, we present a new randomized algorithm and prove that it achieves a better competitive ratio 1/3 for the special case of monotone WISP where the sequence of weights of the arriving intervals is non-decreasing. Thus we provide the first result towards a solution of the long-standing open question. Furthermore, we show that no randomized algorithm achieves a competitive ratio strictly larger than 4/5. This is the first non-trivial upper bound for randomized algorithms for monotone WISP.

关键词： interval scheduling on-line algorithm competitive analysis randomized algorithm upper bound lower bound

来源：评论

学校读者我要写书评

暂无评论

A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2000年第1期13卷 56-63页

作者： Hoogeveen, JA Vestjens, APA Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands Ctr Quantat Methods NL-5600 AK Eindhoven Netherlands

We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on the machine, where preemption is not allowed and the number of jobs is unknown in advance. Each job becomes available at its release date, which is not known in advance, and its characteristics, i.e., processing requirement and delivery time, become known at its arrival. The objective is to minimize the time by which all jobs have been delivered. We propose and analyze an on-line algorithm based on the following idea: As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job. We prove that our algorithm has performance bound (root 5 + 1)/2 approximate to 1.61803, and we show that there cannot exist a deterministic on-line algorithm with a better performance ratio for this problem.

关键词： on-line algorithm single-machine scheduling worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：