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

On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time

JOURNAL OF SCHEDULING 2012年第3期15卷 391-398页

作者： Ng, C. T. Lu, Lingfa Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

In this paper, we consider the on-line integrated production and outbound distribution scheduling problem to minimize the maximum delivery completion time. All jobs arrive over time, and each job and its processing time become known at its arrival time. The jobs are first processed on a single machine and then delivered by a vehicle to a single customer. The vehicle can deliver at most c jobs to the customer at a time. When preemption is allowed and c >= 2, we can provide an on-line algorithm with the best competitive ratio root 5+1/2 approximate to 1.618. When preemption is not allowed, we provide an on-line algorithm which has the best competitive ratio root 5+1/2 approximate to 1.618 for the case c = 1 and has an asymptotic competitive ratio root 5+1/2 approximate to 1.6182 for the case c >= 2.

关键词： Scheduling on-line algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Grundy number and products of graphs

引用

DISCRETE MATHEMATICS 2010年第9期310卷 1482-1490页

作者： Aste, Marie Havet, Frederic Linhares-Sales, Claudia UNSA CNRS Project Mascotte F-06902 Sophia Antipolis France Univ Fed Ceara Dept Comp BR-60455760 Fortaleza Ceara Brazil

The Grundy number of a graph G, denoted by Gamma(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertices of G. In this paper, we study the Grundy number of the lexicographic and cartesian products of two graphs in terms of the Grundy numbers of these graphs. Regarding the lexicographic product, we show that Gamma(G) x Gamma(H) <= Gamma(G[H]) <= 2(Gamma(G)-1)(Gamma(H) - 1) + Gamma(G). In addition, we show that if G is a tree or Gamma(G) = Delta(G) + 1, then Gamma(G[H]) = Gamma(G) x Gamma(H). We then deduce that for every fixed c >= 1, given a graph G, it is CoNP-Complete to decide if Gamma(G) <= c x chi (G) and it is CoNP-Complete to decide if Gamma(G) <= c x omega(G). Regarding the cartesian product, we show that there is no upper bound of Gamma(G square H) as a function of Gamma(G) and Gamma(H). Nevertheless, we prove that Gamma(G square H) <= Delta(G).2 Gamma((H)-1) + Gamma(H). (C) 2009 Elsevier B.V. All rights reserved.

关键词： Colouring on-line algorithm Greedy algorithm Grundy number Product of graphs

来源：评论

学校读者我要写书评

暂无评论

On-line vertex-covering

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 83-108页

作者： Demange, M Paschos, VT Univ Paris 09 CNRS UMR 7024 LAMSADE F-75775 Paris France Univ Paris 01 CERMSEM F-75231 Paris France ESSEC Dept DIS F-95021 Cergy Pontoise France

We study the minimum vertex-covering problem under two on-line models corresponding to two different ways vertices are revealed. The former one implies that the input-graph is revealed vertex-by-vertex. The second model implies that the input-graph is revealed per clusters, i.e. per induced subgraphs of the final graph. Under the cluster-model, we then relax the constraint that the choice of the part of the final solution dealing with each cluster has to be irrevocable, by allowing backtracking. We assume that one can change decisions upon a vertex membership of the final solution, this change implying, however, some cost depending on the number of the vertices changed. (c) 2004 Elsevier B.V. All rights reserved.

关键词： on-line algorithm competitive ratio approximation graph vertex-covering

来源：评论

学校读者我要写书评

暂无评论

On-line load balancing and network flow

引用

algorithmICA 1998年第3期21卷 245-261页

作者： Phillips, S Westbrook, J Stanford Univ Dept Comp Sci Stanford CA 94305 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA

In this paper we study two problems that can be viewed as on-line games on a dynamic bipartite graph. The first problem is on-line load balancing with preemption. A centralized scheduler must assign tasks to servers, processing on-line a sequence of task arrivals and departures. Each task is restricted to run on some subset of the servers. The scheduler attempts to keep the load well-balanced. If preemptive reassignments are disallowed. Azar et al. [3] proved a lower bound of Omega(root n) on the ratio between the maximum load achieved by an on-line algorithm and the optimum off-line maximum load. We show that this ratio can be greatly reduced by an efficient scheduler using only a small amount of rescheduling. We then apply these ideas to network flow. Cheriyan and Hagerup [6] introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum flow in networks. They described a randomized strategy to play the game. King et al. [11] studied a modified version of this game, called "node kill," and gave a deterministic strategy. We obtain an improved deterministic algorithm for the node kill game land hence for maximum flow) in all but the sparsest graphs. The running time achieved is O (mn log(m/n) n + n(2) log(2+epsilon) n), compared with King et al.'s O (mn + n(2+epsilon)). These problems combine a demand for good competitive ratios with more traditional requirements of implementation efficiency. Our solutions deal with the tradeoffs between these measures.

关键词： network flow optimization on-line algorithm competitive analysis load balancing preemption scheduling

来源：评论

学校读者我要写书评

暂无评论

On-line integrated production-distribution scheduling problems with capacitated deliveries

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期200卷 377-384页

作者： Averbakh, Igor Univ Toronto Dept Management Scarborough ON M1C 1A4 Canada

In on-line integrated production-distribution problems, customers release jobs to a manufacturer that has to process the jobs and deliver them to the customers. The jobs are released on-line, that is, at any time there is no information about future jobs. Processed jobs are grouped into batches, which are delivered to the customers as single shipments. The total cost (to be minimized) is the sum of the total weighted flow time and the total delivery cost. Such on-line integrated production-distribution problems have been studied for the case of uncapacitated batches. We consider the capacitated case with an upper bound on the size of a batch. For several versions of the problem, we present efficient on-line algorithms, and use competitive analysis to study their worst-case performance. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Supply chain scheduling Integrated production-distribution problems on-line algorithm Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

FULLY DYNAMIC POINT LOCATION IN A MONOTONE SUBDIVISION

引用

SIAM JOURNAL ON COMPUTING 1989年第4期18卷 811-830页

作者： PREPARATA, FP TAMASSIA, R UNIV ILLINOIS DEPT ELECT & COMP ENGNURBANAIL 61801

In this paper a dynamic technique for locating a point in a monotone planar subdivision, whose current number of vertices is n, is presented. The (complete set of) update operations are insertion of a point on an edge and of a chain of edges between two vertices, and their reverse operations. The data structure uses space O(n). The query time is O(log n), the time for insertion/deletion of a point is O(log n), and the time for insertion/deletion of a chain with k edges is O(log n + k), all worst-case. The technique is conceptually a special case of the chain method of Lee and Preparata and uses the same query algorithm. The emergence of full dynamic capabilities is afforded by a subtle choice of the chain set (separators), which induces a total order on the set of regions of the planar subdivision.

关键词： Point Location Computational geometry on-line algorithm Dynamic data structures Analysis of algorithms planar subdivision monotone polygon

来源：评论

学校读者我要写书评

暂无评论

On-line and off-line approximation algorithms for vector covering problems

引用

algorithmICA 1998年第1期21卷 104-118页

作者： Alon, N Azar, Y Csirik, J Epstein, L Sevastianov, SV Vestjens, APA Woeginger, GJ Tel Aviv Univ Raymond & Beverly Sackler Fac Exact Sci Dept Math IL-69978 Tel Aviv Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Univ Szeged Dept Comp Sci H-6720 Szeged Hungary Russian Acad Sci Inst Math Novosibirsk 630090 Russia Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Graz Tech Univ Inst Math B A-8010 Graz Austria

This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1](d). The goal is to partition X into a maximum number of parts, subject to the constraint that in every part the sum of all vectors is at least one in every coordinate. This problem is known to be NP-complete, and we are mainly interested in its on-line and off-line approximability. For the on-line version, we construct approximation algorithms with worst case guarantee arbitrarily close to 1/(2d) in d greater than or equal to 2 dimensions. This result contradicts a statement of Csirik and Frenk in [5] where it is claimed that, for d greater than or equal to 2, no on-line algorithm can have a worst case ratio better than zero. Moreover, we prove that, for d greater than or equal to 2, no on-line algorithm can have a worst case ratio better than 2/(2d + 1). For the off-line version, we derive polynomial time approximation algorithms with worst case guarantee Theta(1/log d). For d = 2, we present a very fast and very simple off-line approximation algorithm that has worst case ratio 1/2. Moreover, we show that a method from the area of compact vector summation can be used to construct off-line approximation algorithms with worst case ratio 1/d for every d greater than or equal to 2.

关键词： approximation algorithm worst case ratio competitive analysis on-line algorithm packing problem covering problem

来源：评论

学校读者我要写书评

暂无评论

Searching for Zimin patterns

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期571卷 50-57页

作者： Rytter, Wojciech Shur, Arseny M. Warsaw Univ Inst Informat Warsaw Poland Ural Fed Univ Inst Math & Comp Sci Ekaterinburg Russia

In the area of pattern avoidability the central role is played by special words called Zimin patterns. The symbols of these patterns are treated as variables and the rank of the pattern is its number of variables. Zimin type of a word x is introduced here as the maximum rank of a Zimin pattern matching x. We show how to compute Zimin type of a word on-line in linear time. Consequently we get a quadratic time, linear-space algorithm for searching Zimin patterns in words. Then we demonstrate how the Zimin type of the length n prefix of the infinite Fibonacci word is related to the representation of n in the Fibonacci numeration system. Using this relation, we prove that Zimin types of such prefixes and Zimin patterns inside them can be found in logarithmic time. Finally, we give some upper bounds on the function f (n, k) such that every k-ary word of length at least f (n, k) has a factor that matches the rank n Zimin pattern. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Zimin word Unavoidable pattern on-line algorithm Fibonacci word

来源：评论

学校读者我要写书评

暂无评论

On the on-line rent-or-buy problem in probabilistic environments

引用

JOURNAL OF GLOBAL OPTIMIZATION 2007年第1期38卷 1-20页

作者： Xu, Yinfeng Xu, Weijun Li, Hongyi S China Univ Technol Sch Business Adm Guangzhou 510641 Peoples R China Xian Jiaotong Univ Sch Management State Key Lab Mfg Syst Xian 710049 Peoples R China Chinese Univ Hong Kong Fac Business Adm Shatin Hong Kong Peoples R China

Fujiwara and Iwama [In: The 13th Annual International Symposium on algorithms and Computation, pp. 476-488 (2002)] first integrated probability distribution into the classical competitive analysis to study the rental problem. They assumed that the future inputs are drawn from an exponential distribution, and obtained the optimal competitive strategy and the competitive ratio by the derivative method. In this paper, we introduce the interest rate and tax rate into the continuous model of Fujiwra and Iwama [In: The 13th Annual International Symposium on algorithms and Computation, pp. 476-488 (2002)]. Moreover, we use the forward difference method in different probabilistic environments to consider discrete leasing models both with and without the interest rate. We not only give the optimal competitive strategies and their competitive ratios in theory, but also give numerical results. We find that with the introduction of the interest rate and tax rate, the uncertainty involved in the process of decision making will diminish and the optimal purchasing date will be put off.

关键词： on-line algorithm rent-or-buy problem probabilistic distribution competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Applying extra-resource analysis to load balancing

引用

Journal of Scheduling 2000年第5期3卷 273-288页

作者： Brehob, Mark Torng, Eric Uthaisombut, Patchrawat Department of Computer Science Michigan State University East Lousing MI 48824 United States Department of Computer Science 3115 Engineering Building Michigan State University East Lansing MI 48824 United States

Previously, extra-resource analysis has been used to argue that certain on-line algorithms arc good choices for solving specific problems because these algorithms perform well with respect to the optimal off-line algorithm when given extra resources. We now introduce a new application for extra-resource analysis: deriving a qualitative divergence between off-line and on-line algorithms. We do this for the load-balancing problem, the problem of assigning a list of jobs on m identical machines to minimize the makespan, the maximum load on any machine. We analyze the worst-case performance of on-line and off-line approximation algorithms relative to performance of the optimal off-line algorithm when the approximation algorithms have k extra machines. Our main result are the following: The Longest-Processing-Time (L P J) algorithm will produce a schedule with makespan no larger than that of the optimal off-line algorithm if L P J has at least (4m -1)/3 machines while the optimal off-line algorithm has m machines. In contrast, no on-line algorithm can guarantee the same with any number of extra machines. Copyright © 2000 John Wiley and Sons, Ltd.

关键词： load balancing extra-resource analysis longest-processing-time algorithm on-line algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：