摘要:

AbstractAn algorithm is derived for a class of continuous‐time minimum‐cost network flow problems. The algorithm is based on some recent results in the theory of separated continuous linear programs and works with a sequence of discrete approximations to the continuous‐time problem. We prove the convergence of the algorithm and present some numerical results which compare its performance against that of linear network flow algorithms applied to a uniform discrete approximation of the continuous‐time

ISSN:0028-3045    

DOI:10.1002/net.3230260102

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

年代:1995

数据来源: WILEY

摘要:

AbstractA dynamic database in a communications network consists of a set of messages, where a sequence of different versions of each message is generated over time in a repeated and uncoordinated process and where the appearances of the various message versions are distributed among the nodes. The message versions are to be disseminated in the network so that each message version eventually resides at each node. Flooding is a distributed procedure for disseminating message versions. The use of flooding to disseminate repeated and uncoordinated message versions is an integral part of a generic adaptive routing mechanism similar to that used in ARPANET and proposed for the INTERNET and is an element of a method proposed for improving survivability in intra‐LATA networks. A model is formulated to analyze the performance of the dissemination by flooding of repeated and uncoordinated message versions. The worst‐case time complexity is established, showing that flooding is an optimal procedure in terms of this measure. Special properties of flooding in a tree are also established. A key parameter is a separator, which is a lower bound on the time interval between the initial generation of a particular version of any message and the initial generation of the next version of that mess

ISSN:0028-3045    

DOI:10.1002/net.3230260103

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

年代:1995

数据来源: WILEY

摘要:

AbstractIn the period vehicle routing problem, each customer requires a certain number of deliveries per week. Given these frequency requirements, customers must be allocated to days. A vehicle routing problem is solved over each day. We have improved upon best‐known solutions to problems from the literature using a new heuristic procedure. The heuristic also works well on 19 newly generated test problem

ISSN:0028-3045    

DOI:10.1002/net.3230260104

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

年代:1995

数据来源: WILEY

摘要:

AbstractGraphs with weights and delays associated with their edges and/or vertices are often used to model communication and signal flow networks. Network performance can be improved by upgrading the network vertices. Such an upgrade reduces the edge/vertex delays and comes at a cost. We study different formulations of this network performance improvement problem and show that these areNP‐hard. We then consider one of the formulations and develop polynomial time algorithms for some special cases and pseudopolynomial time algorithms for other

ISSN:0028-3045    

DOI:10.1002/net.3230260105

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

年代:1995

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230260101

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

年代:1995

数据来源: WILEY