摘要:

AbstractVariations and extensions of the Open‐Shop Scheduling Problem are presented with an emphasis on models suitable for some automated production systems. Complexity results are given and polynomially solvable cases are described. © 1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230803

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThis paper presents two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles. Indeed, using a simple implementation of taboo search as an iterative search method, every best‐known solution to classical problems was found. The first partition method (based on a partition into polar regions) is appropriate for Euclidean problems whose cities are regularly distributed around a central depot. The second partition method is suitable for any problem and is based on the arborescence built from the shortest paths from any city to the depot. Finally, solutions that are believed to be optimum are given for problems generated on a grid. © 1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230804

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractThis paper considers a generalized version of the stochastic spanning tree problem in which edge costs are random variables and the objective is to find a spectrum of optimal spanning trees satisfying a certain chance constraint whose right‐hand side also is treated as a decision variable. A special case of this problem with fixed right‐hand side has been solved polynomially using a parameteric approach. Also, the same parametric method without increasing the complexity order has been extended to include the right‐hand side also as a decision variable. In this paper, two different methods are given for solving the generalized problem. First, a different parametric method better than the earlier one is given. Then, a method that makes use of the efficient extreme points of the convex hull of the mappings of all the spanning trees in a bicriteria spanning tree problem is presented. But it is shown that in the worst case the bicriteria method is superior. © 1993 by John Wiley&Son

ISSN:0028-3045    

DOI:10.1002/net.3230230805

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractOne important issue being addressed in the design of Distributed Computer Networks is how to increase the availability of time‐changing information even in the event of failures. Recently, a technique called “stashing” was proposed. Stashing a file signifies placing a copy of that file in several nodes of the network. In addition, a “predicate” has been defined as a consistency requirement for a particular file copy with respect to the original. We address the problem of minimizing the propagation cost of stashed copies subject to predicate restrictions imposed by the user. In the version of the problem that we tackle, the user may receive a copy with a predicate better than requested. We call this problem the Dynamic Predicate Stashing Copy Problem (DPSCP) and propose a formulation to solve it. Resolution approaches, numerical results, and properties of the problem are also discussed. © 1993 by John Wiley

ISSN:0028-3045    

DOI:10.1002/net.3230230806

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe consider the problem of efficient information exchange in a communication network whose nodes and/or links are subject to Byzantine faults that are randomly and independently distributed through the network. The goal is almost safe communication, i.e., getting to every fault‐free node information about every other fault‐free node, with probability converging to one as the number of nodes grows. We present nonadaptive almost‐safe communication schemes working for various networks in asymptotically optimal time and using an asymptotically optimal number of message

ISSN:0028-3045    

DOI:10.1002/net.3230230807

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

摘要:

AbstractWe propose a new method for ordering the candidate nodes in label correcting methods for shortest path problems. The method tries to scan nodes with small labels as early as possible and may be viewed as a low‐overhead approximation to Dijkstra's algorithm. Compared with the D'Esopo–Pape algorithm, our method is equally simple but much faster. Our method can also be combined with the threshold algorithm, thereby considerably improving its practical performance. © 1993 by John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230230808

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230802

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1993

数据来源: WILEY