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

SCHEDULING TWO GROUPS OF JOBS WITH INCOMPLETE INFORMATION

Systems Science and Systems Engineering 2003年第1期12卷 73-81页

作者： GuochuanZHANG XiaoqiangCAI C.K.WONG DepartmentofMathematics ZhejiangUniversityHangzhou30027P.R.China DepartmentofSystemsEngineeringandEngineeringManagement TheChineseUniversityofHongKongShatinN.T.HongKong DepartmentofComputerScienceandEngineering TheChineseUniversityofHangKongShatinN.T.HongKong

In real world situations, most scheduling problems occur neither as complete off-line nor as complete on-line models. Most likely, a problem arises as an on-line model with some partial information. In this article, we consider such a model. We study the scheduling problem P(n1,n2), where two groups of jobs are to be scheduled. The first job group is available beforehand. As soon as all jobs in the first group are assigned, the second job group appears. The objective is to minimize the longest job completion time (makespan). We show a lower bound of 3/2 even for very special cases. Best possible algorithms are presented for a number of cases. Furthermore, a heuristic is proposed for the general case. The main contribution of this paper is to discuss the impact of the quantity of available information in designing an on-line algorithm. It is interesting to note that the absence of even a little bit information may significantly affect the performance of an algorithm.

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

来源：评论

学校读者我要写书评

暂无评论

A novel system for on-farm fertility monitoring based on milk progesterone

引用

JOURNAL OF DAIRY SCIENCE 2018年第9期101卷 8369-8382页

作者： Adriaens, Ines Saeys, Wouter Huybrechts, Tjebbe Lamberigts, Chris Francois, Liesbeth Geerinckx, Katleen Leroy, Jo De Ketelaere, Bart Aernouts, Ben Katholieke Univ Leuven Div Mech Biostat & Sensors MeBioS Dept Biosyst Kasteelpk Arenberg 30 B-3001 Heverlee Belgium Katholieke Univ Leuven Livestock Physiol Dept Biosyst Kasteelpk Arenberg 30 B-3001 Heverlee Belgium Katholieke Univ Leuven Livestock Genet Dept Biosyst Kasteelpk Arenberg 30 B-3001 Heverlee Belgium Hooibeeksedijk 1 B-2440 Geel Belgium Univ Antwerp Fac Pharmaceut Biomed & Vet Sci Univ Pl 1 Antwerp Belgium Katholieke Univ Leuven Cluster Bioengn Technol Dept Microbial & Mol Syst Campus Geel B-2440 Geel Belgium

Timely identification of a cow's reproduction status is essential to minimize fertility-related losses on dairy farms. This includes optimal estrus detection, pregnancy diagnosis, and the timely recognition of early embryonic death and ovarian problems. On-farm milk progesterone (P4) analysis can indicate all of these fertility events simultaneously. However, milk P4 measurements are subject to a large variability both in terms of measurement errors and absolute values between cycles. The objective of this paper is to present a newly developed methodology for detecting luteolysis preceding estrus and give an indication of its on-farm use. The innovative monitoring system presented is based on milk P4 using the principles of synergistic control. Instead of using filtering techniques and fixed thresholds, the present system employs an individually on-line updated model to describe the P4 profile, combined with a statistical process control chart to identify the cow's fertility status. The inputs for the latter are the residuals of the on-line updated model, corrected for the concentration-dependent variability that is typical for milk P4 measurements. To show its possible use, the system was validated on the P4 profiles of 38 dairy cows. The positive predictive value for luteolysis followed by estrus was 100%, meaning that the monitoring system picked up all estrous periods identified by the experts. Pregnancy or embryonic mortality was characterized by the absence or detection of luteolysis following an insemination, respectively. For 13 cows, no luteolysis was detected by the system within the 25 to 32 d after insemination, indicating pregnancy, which was confirmed later by rectal palpation. It was also shown that the system is able to cope with deviating P4 profiles having prolonged follicular or luteal phases, which may suggest the occurrence of cysts. Future research is recommended for optimizing sampling frequency, predicting the optimal insemination window, and

关键词： milk progesterone monitoring fertility on-line algorithm statistical process control

来源：评论

学校读者我要写书评

暂无评论

On-line load balancing made simple: Greedy strikes back

引用

JOURNAL OF DISCRETE algorithmS 2007年第1期5卷 162-175页

作者： Crescenzi, Pilu Gambosi, Giorgio Nicosia, Gaia Penna, Paolo Unger, Walter Univ Florence Dipartimento Sistemi & Informat Via Lombroso 6-17 I-50134 Florence Italy Univ Roma Tor Vergata Dipartimento Matemat I-00133 Rome Italy Univ Rome Tre Dipartimento Automat & Informat I-00146 Rome Italy Univ Salerno Dipartimento Informat & Applicaz RM Capocelli I-84081 Baronissi SA Italy Rhein Westfal TH Aachen D-52056 Aachen Germany

We provide a new approach to the on-line load balancing problem in the case of restricted assignment of temporary weighted tasks. The approach is very general and allows us to derive on-line algorithms whose competitive ratio is characterized by some combinatorial properties of the underlying graph G representing the problem: in particular, the approach consists in applying the greedy algorithm to a suitably constructed subgraph of G. In the paper, we prove the NP-hardness of the problem of computing an optimal or even a c-approximate subgraph, for some constant c > 1. Nevertheless, we show that, for several interesting problems, we can easily compute a subgraph yielding an optimal on-line algorithm. As an example, the effectiveness of this approach is shown by the hierarchical server model introduced by Bar-Noy et al. ( 2001). In this case, our method yields simpler algorithms whose competitive ratio is at least as good as the existing ones. Moreover, the algorithm analysis turns out to be simpler. Finally, we give a sufficient condition for obtaining, in the general case, O(root n)-competitive algorithms with our technique: this condition holds in the case of several problems for which a Omega(root n) lower bound is known. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Approximation algorithm Computational complexity Load balancing on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved Lower Bounds on the On-line Chain Partitioning of Posets of Bounded Dimension

引用

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 2023年第3期40卷 683-690页

作者： Biro, Csaba Curbelo, Israel R. Univ Louisville Dept Math Louisville KY 40292 USA Kean Univ Dept Math Sci Union NJ 07083 USA

An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemeredi proved that any on-line algorithm could be forced to use (2(w+1)) chains to partition a poset of width w. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In a survey paper by Bosek et al., it is shown that Szemeredi's argument could be improved to obtain a lower bound almost twice as good. Variants of the problem were considered where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size d. In this paper, we prove two results. First, we prove that any on-line algorithm can be forced to use (2 - o(1))(2(w+1)) chains to partition a 2-dimensional poset of width w. Second, we prove that any on-line algorithm can be forced to use (2 - 1/d-1 - o(1))(2(w+1)) chains to partition a poset of width w presented via a realizer of size d.

关键词： on-line algorithm Chain partitioning Poset dimension

来源：评论

学校读者我要写书评

暂无评论

An on-line wavelet transform for de-noising of high performance liquid chromatograms

引用

ANALYTICAL LETTERS 1999年第12期32卷 2507-2520页

作者： Shao, XG Hou, SQ Univ Sci & Technol China Dept Chem Hefei 230026 Anhui Peoples R China

A novel algorithm of wavelet transform, called the on-line wavelet transform, which can be used in on-line processing of signals of an instrumental analysis, is proposed. And application of the on-line wavelet transform in de-noising of high performance liquid chromatograms was investigated. Results showed that the noise in chromatograms was cleanly removed by the method, peak position after the on-line de-noising dose not change, and the linearity of calibration curves of concentration versus peak area remained and even was improved. Quantitative determination of three mixed samples were investigated with five standard samples;the recoveries were between 94.0-105.0%.

关键词： wavelet transform on-line algorithm de-noising chromatogram

来源：评论

学校读者我要写书评

暂无评论

On-line scheduling of equal-length intervals on parallel machines

引用

INFORMATION PROCESSING LETTERS 2012年第10期112卷 376-379页

作者： Fung, Stanley P. Y. Poon, Chung Keung Yung, Duncan K. W. City Univ Hong Kong Hong Kong Hong Kong Peoples R China Univ Leicester Leicester Leics England

We consider the on-line preemptive scheduling of weighted equal-length intervals on multiple machines to maximize the total weight of completed intervals. We design an algorithm that is 2-competitive when the number of machines m is even;and (2 + 2/2m-1)-competitive when m is an odd number at least 3. For example, when m = 3, it is 2.4-competitive. As m increases, the competitive ratio approaches 2. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Interval scheduling Parallel scheduling on-line algorithm Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Evolvable fuzzy systems from data streams with missing values: With application to temporal pattern recognition and cryptocurrency prediction

引用

PATTERN RECOGNITION LETTERS 2019年 128卷 278-282页

作者： Garcia, Cristiano Esmin, Ahmed Leite, Daniel Skrjanc, Igor Univ Fed Lavras Dept IT Management Lavras Brazil Univ Fed Lavras Dept Comp Sci Lavras Brazil Univ Fed Lavras Dept Engn Lavras Brazil Univ Ljubljana Fac Elect Engn Ljubljana Slovenia

Data streams with missing values are common in real-world applications. This paper presents an evolving granular fuzzy-rule-based model for temporal pattern recognition and time series prediction in online nonstationary context, where values may be missing. The model has a modified rule structure that includes reduced-term consequent polynomials, and is supplied by an incremental learning algorithm that simultaneously impute missing data and update model parameters and structure. The evolving Fuzzy Granular Predictor (eFGP) handles single and multiple Missing At Random (MAR) and Missing Completely At Random (MCAR) values in nonstationary data streams. Experiments on cryptocurrency prediction show the usefulness, accuracy, processing speed, and eFGP robustness to missing values. Results were compared to those provided by fuzzy and neuro-fuzzy evolving modeling methods. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Temporal pattern recognition on-line algorithm Real-time system Fuzzy system Machine learning

来源：评论

学校读者我要写书评

暂无评论

Mean analysis of an online algorithm for the vertex cover problem

引用

INFORMATION PROCESSING LETTERS 2009年第9期109卷 436-439页

作者： Birmele, Etienne Delbot, Francois Laforest, Christian Univ Evry INRA 1152 CNRS UMR 8071Lab Stat & Genome F-91000 Evry France Univ Evry CNRS FRE 3190 Lab IBISC F-91000 Evry France Univ B Pascal CNRS UMR 6158 LIMOS F-63173 Aubiere France

In 2005, Demange and Paschos proposed in [M. Demange, ***. Paschos, On-line vertex-covering, Theoret. Comput. Sci. 332 (2005) 83-108] an online algorithm (noted LR here) for the classical vertex cover problem. They shown that. for any graph of maximum degree Delta, LR constructs a vertex cover whose size is at most Delta times the optimal one (this bound is tight in the worst case). Very recently, two of the present authors have shown in [F. Delbot, C. Laforest, A better list heuristic for vertex cover, Inform. Process. Lett. 107 (2008) 125-127] that LR has interesting properties (it is a good "list algorithm" and it can easily be distributed). In addition, LR has good experimental behavior in spite of its 6 approximation (or competitive) ratio and the fact that it can be executed without the knowledge of the full instance at the beginning. In this paper we analyze it deeper and we show that LR has good "average" performances: we prove that its mean approximation ratio is strictly less than 2 for any graph and is equal to 1 + e(-2) approximate to 1.13 in paths. LR is then a very interesting algorithm for constructing small vertex covers, despite its bad worst case behavior. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Graphs Vertex cover Approximation algorithm Mean analysis on-line algorithm

来源：评论

学校读者我要写书评

暂无评论

A new version of on-line variable-sized bin packing

引用

DISCRETE APPLIED MATHEMATICS 1997年第3期72卷 193-197页

作者： Zhang, GC Institut für Mathematik Technische Universität Graz Austria

This paper investigates a new version of the on-line variable-sized bin packing problem. Suppose that bin capacities can vary. Given a list of items, the goal is to pack items in the bins which arrive in an on-line way such that the total size of bins used is minimized. It is shown that next fit and first fit (decreasing) algorithms all have a worst-case performance bound of 2.

关键词： bin packing on-line algorithm worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

Restarts can help in the on-line minimization of the maximum delivery time on a single machine

引用

Journal of Scheduling 2000年第6期3卷 333-341页

作者： Van, den Akker, Marjan Hoogeveen, Han Vakhania, Nodari Department of Mathematical Models National Aerospace Laboratory NLR P.O. Box 90502 1006 BM Amsterdam Netherlands Department of Computer Science Utrecht University P.O. Box 80089 3508 TB Utrecht Netherlands Science Faculty State University of Morelos AV. Universidad 1001 Cuernavaca 62210 Mor. Mexico

We consider a single-machine on-line scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on a single machine. 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. In our model preemption is not allowed, but we are allowed to restart a job, that is, the processing of a job can be broken off to have the machine available to process an urgent job, but the time already spent on processing this interrupted job is considered to be lost. We propose an on-line algorithm and show that its performance bound is equal to 1.5, which matches a known lower bound due to Vestjens. For the same problem without restarts the optimal worst-case bound is known to be equal to ( root 5 + 1)/2 approximately equals 1.61803;this is the first example of a situation in which the possibility of applying restarts reduces the worst-case performance bound, even though the processing times are known. Copyright © 2000 John Wiley and Sons, Ltd.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：