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

online algorithms to schedule a proportionate flexible flow shop of batching machines

JOURNAL OF SCHEDULING 2022年第6期25卷 643-657页

作者： Hertrich, Christoph Weiss, Christian Ackermann, Heiner Heydrich, Sandy Krumke, Sven O. Tech Univ Kaiserslautern Dept Math D-67663 Kaiserslautern Germany Tech Univ Berlin Inst Math D-10623 Berlin Germany Fraunhofer Inst Ind Math ITWM Dept Optimizat D-67663 Kaiserslautern Germany

This paper is the first to consider online algorithms to schedule a proportionate flexible flow shop of batching machines (PFFB). The scheduling model is motivated by manufacturing processes of individualized medicaments, which are used in modern medicine to treat some serious illnesses. We provide two different online algorithms, proving also lower bounds for the offline problem to compute their competitive ratios. The first algorithm is an easy-to-implement, general local scheduling heuristic. It is 2-competitive for PFFBs with an arbitrary number of stages and for several natural scheduling objectives. We also show that for total/average flow time, no deterministic algorithm with better competitive ratio exists. For the special case with two stages and the makespan or total completion time objective, we describe an improved algorithm that achieves the best possible competitive ratio phi = 1+root 5/2 the golden ratio. All our results also hold for proportionate (non-flexible) flow shops of batching machines (PFB) for which this is also the first paper to study online algorithms.

关键词： Planning of pharmaceutical production Proportionate flow shop Flexible flow shop Botching machines online algorithms Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online algorithms for scheduling unit length jobs on parallel-batch machines with lookahead

引用

INFORMATION PROCESSING LETTERS 2012年第7期112卷 292-297页

作者： Li, Wenhua Zhang, Zhenkun Yang, Sufang Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China Huanghuai Univ Dept Math Zhumadian 463000 Henan Peoples R China

We consider online scheduling of unit length jobs on m parallel-batch machines with lookahead to minimize makespan. A parallel-batch machine can handle up to b jobs simultaneously as a batch with processing time equal to the maximum processing time of the jobs included in the batch. In the lookahead model, at a time instant t, an online algorithm can foresee all the jobs that will arrive in the time segment (t, t + beta). In this paper, we deal with two variants: the unbounded model with b = infinity and the bounded model with b < infinity. For the unbounded model, we present an optimal online algorithm for beta >= 1/m, and provide a best possible online algorithm of competitive ratio 1 + alpha(m) for 0 <= beta < 1/m, where alpha(m) is the positive root of (1 + alpha)((m+1)) = alpha + 2 - beta Sigma(m)(i=1)(1 + alpha)(i). For the bounded model, we establish a lower bound with a form of piecewise function, and provide an online algorithm with competitive ratios 1 + alpha* for 0 <= beta <= 1/6 and 3/2 for beta > 1/6, respectively, where alpha* is the positive root of alpha(2) + (beta + 1)alpha + beta - 1 = 0. The online algorithm is the best possible when 0 <= beta <= 1/6. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithms Parallel batch Lookahead Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online algorithms for the maximum k-colorable subgraph problem

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 91卷 209-224页

作者： Hertz, Alain Montagne, Romain Gagnon, Francois Ecole Polytech Gerad Dept Math & Ind Engn Montreal PQ Canada Ecole Technol Super Dept Elect Engn Montreal PQ Canada

The maximum k-colorable subgraph problem (k-MCSP) is to color as many vertices as possible with at most k colors, such that no two adjacent vertices share the same color. We consider online algorithms for this NP-hard problem, and give bounds on their competitive ratio. We then consider a large family A of online sequential coloring algorithms and determine the smallest graphs for which no algorithm in A can produce an optimal solution to the k-MCSP. We then compare the performance of several online sequential coloring algorithms, using DIMACS benchmark instances. We finally consider the case where vertices colored at an early stage can receive a new color later on, as long as they remain colored. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： online algorithms Maximum k-colorable subgraph Sequential vertex coloring Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online algorithms for maximizing weighted throughput of unit jobs with temperature constraints

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第2期26卷 237-250页

作者： Birks, Martin Cole, Daniel Fung, Stanley P. Y. Xue, Huichao Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England Univ Pittsburgh Dept Comp Sci Pittsburgh PA 15260 USA

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We first give an optimally competitive randomized algorithm. Then we give a constant competitive randomized algorithm that allows a tradeoff between the maximum heat contribution of jobs and the competitiveness. Finally we consider the multiple processor case and give several tight upper and lower bounds.

关键词： online algorithms Scheduling Competitive analysis Temperature Resource augmentation

来源：评论

学校读者我要写书评

暂无评论

online algorithms supporting emergence in distributed CAD systems

引用

ADVANCES IN ENGINEERING SOFTWARE 2001年第10-11期32卷 779-787页

作者： Feijó, B Gomes, PCR Scheer, S Bento, J Pontificia Univ Catolica Rio de Janeiro Dept Comp Intelligent CAD Lab BR-22453900 Rio De Janeiro Brazil UFPF TC CESEC BR-81531990 Curitiba Parana Brazil Univ Tecn Lisboa Inst Super Tecn DECivil P-1096 Lisbon Portugal

The rule-based approach from traditional Al and the conventional constraint satisfaction algorithms are not adequate to cope with the unpredictable events and interactive computations in distributed CAD environments. This paper claims that the problems faced by distributed CAD systems require solutions based on the concepts of emergence, reactivity, and online algorithms, The present paper presents Extended Constraints Graphs (ECGs) as online algorithms supporting emergence in a network of reactive agents. ECGs represent an effective solution for the nonlinear constraint problem in cyclic graphs, which are distributed over a heterogeneous computer network. The relationships between agents in an ECG are generic, distributed, recursive and nonlinear - a problem not solved in the literature. Also this paper presents a CORBA model integrated with a Geometry Bus to support distributed virtual prototype whose variables can be defined in terms of ECGs. (C) 2001 Civil-Comp Ltd and Elsevier Science Ltd. All rights reserved.

关键词： CAD distributed objects online algorithms emergence

来源：评论

学校读者我要写书评

暂无评论

online algorithms for market clearing

引用

JOURNAL OF THE ACM 2006年第5期53卷 845-879页

作者： Blum, Avrim Sandholm, Tuomas Zinkevich, Martin Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. The auctioneer is faced with an online clearing problem of deciding which buy and sell bids to match without knowing what bids will arrive in the future. For maximizing profit, we present a (randomized) online algorithm with a competitive ratio of ln(p(max) - p(min)) + 1, when bids are in a range [p(min), p(max)], which we show is the best possible. A simpler algorithm has a ratio twice this, and can be used even if expiration times are not known. For maximizing the number of trades, we present a simple greedy algorithm that achieves a factor of 2 competitive ratio if no money-losing trades are allowed. We also show that if the online algorithm is allowed to subsidize matches-match money-losing pairs if it has already collected enough money from previous pairs to pay for them-then it can actually be 1-competitive with respect to the optimal offline algorithm that is not allowed subsidy. That is, for maximizing the number of trades, the ability to subsidize is at least as valuable as knowing the future. We also consider objectives of maximizing buy or sell volume and social welfare. We present all of these results as corollaries of theorems on online matching in an incomplete interval graph. We also consider the issue of incentive compatibility, and develop a nearly optimal incentive-compatible algorithm for maximizing social welfare. For maximizing profit, we show that no incentive-compatible algorithm can achieve a sublinear competitive ratio, even if only one buy bid and one sell bid are alive at a time. However, we provide an algorithm that, under certain mild assumptions on the bids, performs nearly as well as the best fixed pair of buy and sell prices, a weaker

关键词： algorithms economics theory Competitive analysis double auctions exchanges online algorithms

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Basestation Allocation

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2014年第5期13卷 2966-2975页

作者： Thangaraj, Andrew Vaze, Rahul IIT Madras Dept Elect Engn Madras Tamil Nadu India TIFR Mumbai Sch TCS Bombay Maharashtra India

Design of online algorithms for assigning mobile users to basestations is considered with the objective of maximizing the sum-rate, when all users associated to any one basestation equally share each basestation's resources. Each user on its arrival reveals the rates it can obtain if connected to each of the basestations, and the problem is to assign each user to any one basestation irrevocably and without delay so that the sum-rate is maximized at the end of all user arrivals. In online algorithms, at each user arrival, the rates of future users are assumed to be unknown, and no assumptions are made about their statistics. online algorithms with constant factor loss in comparison to offline algorithms (that know both the user arrival and user rates profile in advance) are derived. The proposed online algorithms are motivated from the famous online k-secretary problem and online maximum weight matching problem.

关键词： Basestation allocation online algorithms K-secretary problem online matching

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Network Robustness Under Connectivity Constraints

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第4期9卷 2266-2277页

作者： Muthirayan, Deepan Khargonekar, Pramod P. Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92697 USA

In this paper, we present algorithms for designing networks that are robust to node failures with minimal or limited number of links. We present algorithms for both the static network setting and the dynamic network setting;setting where new nodes can arrive in the future. For the static setting, we present algorithms for constructing the optimal network in terms of the number of links used for a given node size and the number of nodes that can fail. We then consider the dynamic setting where it is disruptive to remove any of the older links. For this setting, we present online algorithms for two cases: (i) when the number of nodes that can fail remains constant and (ii) when only the proportion of the nodes that can fail remains constant. We show that the proposed algorithm for the first case saves nearly 3/4th of the total possible links at any point of time. We then present algorithms for various levels of the fraction of the nodes that can fail and characterize their link usage. We show that when 1/2 the number of nodes can fail at any point of time, the proposed algorithm saves nearly 1/2 of the total possible links at any point of time. We show that when the number of nodes that can fail is limited to the fraction 1/(2 m) (m is an element of N), the proposed algorithm saves nearly as much as (1 - 1/2 m) of the total possible links at any point of time. We also show that when the number of nodes that can fail at any point of time is 1/2 of the number of nodes plus n, n is an element of N, the number of links saved by the proposed algorithm reduces only linearly in n. We conjecture that the saving ratio achieved by the algorithms we present is optimal for the dynamic setting.

关键词： Dynamic networks online algorithms Network robustness optimal networks

来源：评论

学校读者我要写书评

暂无评论

online algorithms for Multilevel Aggregation

引用

OPERATIONS RESEARCH 2020年第1期68卷 214-232页

作者： Bienkowski, Marcin Bohm, Martin Byrka, Jaroslaw Chrobak, Marek Durr, Christoph Folwarczn, Lukas Jez, Lukasz Sgall, Jiri Nguyen Kim Thang Vesely, Pavel Univ Wroclaw Inst Comp Sci PL-50137 Wroclaw Poland Univ Bremen CSLog D-28359 Bremen Germany Charles Univ Prague Comp Sci Inst CR-11800 Prague Czech Republic Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Sorbonne Univ Lab Informat Paris 6 CNRS F-75252 Paris France Czech Acad Sci Inst Math Prague 11000 Czech Republic Univ Evry Val Essonne Lab Informat Bioinformat & Syst Complexes F-91034 Evry France Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

In the multilevel aggregation problem (MLAP), requests arrive at the nodes of an edge-weighted tree J and have to be served eventually. A service is defined as a subtree X of J that contains the root of J. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subbees. MLAP is a generalization of some well-studied optimization problems;for example, for trees of depth 1, MLAP is equivalent to the Transmission Control Protocol acknowledgment problem, whereas for trees of depth 2, it is equivalent to the joint replenishment problem. Aggregation problems for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and supply chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant-competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant-competitive online algorithm for trees of arbitrary (fixed) depth. The competitive ratio is O(D(4)2(D)), where D is the depth of J. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.

关键词： algorithmic aspects of networks online algorithms scheduling and resource allocation Iot sizing multistage assembly problem

来源：评论

学校读者我要写书评

暂无评论

online algorithms with advice for bin packing and scheduling problems

引用

THEORETICAL COMPUTER SCIENCE 2015年 600卷 155-170页

作者： Renault, Marc P. Rosen, Adi van Stee, Rob CNRS F-75700 Paris France Univ Paris Diderot Paris France Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England

We consider the setting of online computation with advice and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of 1 with only a constant number of bits of advice per request. For the bin packing problem, we give an online algorithm with advice that is (1 + epsilon)-competitive and uses O (1/epsilon log 1/epsilon) bits of advice per request. For scheduling on m identical machines, with the objective function of any of makespan, machine covering and the minimization of the l(p) norm, p > 1, we give similar results. We give online algorithms with advice which are (1 + epsilon)-competitive ((1/(1-epsilon))-competitive for machine covering) and also use O (1/epsilon log 1/epsilon) bits of advice per request. We complement our results by giving a lower bound that shows that for any online algorithm with advice to be optimal, for any of the above scheduling problems, a non-constant number (namely, at least (1 -2m/n) log m, where n is the number of jobs and m is the number of machines) of bits of advice per request is needed. (C) 2015 Elsevier B.V. All rights reserved.

关键词： online algorithms online computation with advice Competitive analysis Bin packing Machine scheduling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：