3族新的不含紧优与几乎紧优的有向双环网络无限族

给出了3族新的不含紧优与几乎紧优的有向双环网络.     

Optimal location of interconnected facilities on tree networks subject to distance constraints

Optimal location of interconnected facilities on tree networks is considered in the case when some of the nodes of the network contain existing facilities. The distances between the facilities must satisfy maximum constraints. Polynomial algorithms for the solution of this problem are proposed.     

In Search of Sensitivity in Network Optimization

Queueing Systems - This paper concerns the following questions regarding policy synthesis in large queueing networks: (i) It is well known that an understanding of variability is important in the...     

Equitable transit charges for multiadministration telecommunications networks

We study a multi-administration telecommunications network that is an abstraction of an international network. The nodes represent separate telecommunications administrations that are linked such that alternately-routed calls go through one tandem administration. The cost of the group of circuits between a pair of administrations is borne by them; and when a call between the pair is alternately routed through the tandem node, then the two administrations share the call revenue and pay transit fees to the tandem administration. The numbers of circuits between the administrations are selected to yield a least-cost network that provides a desired level of service, in terms of blocking probabilities, over an entire day. We address the problem of determining transit charges for the alternately-routed calls that are equitable for all of the administrations. Our approach is to derive such charges by equating the system-optimal circuit group sizes to certain hypothetical administration-optimal circuit group sizes. This approach may be of use in other system design problems involving cost sharing among several companies.This research was supported in part by Grant AFOSR 84-0367.     

8族新的2-紧优的有向双环网络无限族

给出了8族新的2-紧优的有向双环网络无限族.     

Stability and performance analysis of rate-based feedback flow controlled ATM networks

Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals (variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments) that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational results. This revised version was published online in June 2006 with corrections to the Cover Date.     

2族3-紧优的有向双环网络无限族

该文给出一种寻找k-紧优的双环网络无限族(k≥0)的方法,利用此方法得到了2族 3-紧优的有向双环网络无限族．     

k-紧优有向双环网络无限族的构建

本文给出了一种方法用于构造k-紧优双环网络无限族(k≥1),并用此方法构造出了4族3-紧优无限族,3族新的4-紧比无限族,3族5-紧优无限族及2族6-紧优无限族．     

Queueing Networks of Random Link Topology: Stationary Dynamics of Maximal Throughput Schedules

In this paper, we study the stationary dynamics of a processing system comprised of several parallel queues and a single server of constant rate. The connectivity of the server to each queue is randomly modulated, taking values 1 (connected) or 0 (severed). At any given time, only the currently connected queues may receive service. A key issue is how to schedule the server on the connected queues in order to maximize the system throughput. We investigate two dynamic schedules, which are shown to stabilize the system under the highest possible traffic load, by scheduling the server on the connected queue of maximum backlog (workload or job number). They are analyzed under stationary ergodic traffic flows and connectivity modulation. The results also extend to the more general case of random server rate.We then investigate the dynamics of acyclic (feed-forward) queueing networks with nodes of the previous type. Their links (connectivities) are stochastically modulated, inducing fluctuating network topologies. We focus on the issue of network throughput and show that it is maximized by simple node server schedules. Rate ergodicity of the traffic flows traversing the network is established, allowing the computation of the maximal throughput.Queueing networks of random topology model several practical systems with unreliable service, including wireless communication networks with extraneous interference, flexible manufacturing systems with failing components, production management under random availability of resources etc.Research supported in part by the National Science Foundation.This revised version was published online in June 2005 with corrected coverdate     

水面舰队建立最佳防空编队的数学模型

防空反导是水面舰艇编队最重要的任务之一,我国南海海域辽阔,水面舰艇执行外围岛礁附近海域巡航任务时,往往超出了空中掩护的作战半径,需要自身的对空防御,这时,水面舰艇的编队阵型至关重要.同时,空中目标意图识别是战场态势分析的一个重要部分.以我海军在南海某开阔海域巡逻的水面舰艇编队为例,探究了最佳编队队形的数学模型,并根据所提供的战场空中目标信息,判断目标可能的意图,为威胁判断、火力分配和抗击来袭目标奠定基础.     

Domain Decomposition of Optimal Control Problems for Dynamic Networks of Elastic Strings

We consider optimal control problems related to exact- and approximate controllability of dynamic networks of elastic strings. In this note we concentrate on problems with linear dynamics, no state and no control constraints. The emphasis is on approximating target states and velocities in part of the network using a dynamic domain decomposition method (d³m) for the optimality system on the network. The decomposition is established via a Uzawa-type saddle-point iteration associated with an augmented Lagrangian relaxation of the transmission conditions at multiple joints. We consider various cost functions and prove convergence of the infinite dimensional scheme for an exemplaric choice of the cost. We also give numerical evidence in the case of simple exemplaric networks.     

Optimal Design of Two Road Networks Based on their Properties

In this paper,we discuss some fundamental properties of two idealized typical networks,namely,grid type and radial-circular type.The discussion is based on SPCP (Shortest Path Counting Problem),whichreflects the traffic density of a road segment.Furthermore,we compare their effectiveness based on the obtainedresults of the above two road networks,and suggest some proposals on the design of car lanes by consideringthe direction of a road segment in relation to these road networks.     

Optimal server allocation in general,finite, multi‐server queueing networks

Queueing networks with finite buffers, multiple servers, arbitrary acyclic, series‐parallel topologies, and general service time distributions are considered in this paper. An approach to optimally allocate servers to series, merge, and split topologies and their combinations is demonstrated. The methodology builds on two‐moment approximations to the service time distribution embedded in the generalized expansion method for computing the performance measures in complex finite queueing networks and Powell's algorithm for optimally allocating servers to the network topology. Convexity of the objective function along with results from computational experiments is presented for showing the efficacy of the methodology. Copyright © 2009 John Wiley & Sons, Ltd.     

Value iteration and optimization of multiclass queueing networks

This paper considers in parallel the scheduling problem for multiclass queueing networks, and optimization of Markov decision processes. It is shown that the value iteration algorithm may perform poorly when the algorithm is not initialized properly. The most typical case where the initial value function is taken to be zero may be a particularly bad choice. In contrast, if the value iteration algorithm is initialized with a stochastic Lyapunov function, then the following hold: (i) a stochastic Lyapunov function exists for each intermediate policy, and hence each policy is regular (a strong stability condition), (ii) intermediate costs converge to the optimal cost, and (iii) any limiting policy is average cost optimal. It is argued that a natural choice for the initial value function is the value function for the associated deterministic control problem based upon a fluid model, or the approximate solution to Poisson’s equation obtained from the LP of Kumar and Meyn. Numerical studies show that either choice may lead to fast convergence to an optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multi-objective optimal allocation of resources to increase the seismic reliability of highways

To reduce the risk of disruption of lifeline systems during the emergency following an earthquake (or any other disaster) preventive interventions on the existing concerned facilities are necessary, but often hindered by the limitation of the available economic resources. In this paper, procedures for the optimal allocation of these resources are presented, with special reference to the case of road networks. It is assumed that the bridges are the only vulnerable elements, and an example of application on a specific network is developed in detail. In the first part of the paper, optimization with respect to several alternative objective functions is dealt with, while in the second part multi-objective optimization is tackled. The results obtained are compared and discussed.Dedicated to Haresh Shah on the occasion of his retirement from Stanford University.     

An efficient method to determine the optimal configuration of a flexible manufacturing system

A frequently encountered design issue for a flexible manufacturing system (FMS) is to find the lowest cost configuration, i.e. the number of resources of each type (machines, pallets, ...), which achieves a given production rate. In this paper, an efficient method to determine this optimal configuration is presented. The FMS is modelled as a closed queueing network. The proposed procedure first derives a heuristic solution and then the optimal solution. The computational complexity for finding the optimal solution is very reasonable even for large systems, except in some extreme cases. Moreover, the heuristic solution can always be determined and is very close (and often equal) to the optimal solution. A comparison with the previous method of Vinod and Solberg shows that our method performs very well.     

Optimal control of generalized multiobjective games with application to traffic networks modeling

The purpose of this paper is to study some new results on the existence and convergence of the solutions to controlled systems of generalized multiobjective games, controlled systems of traffic networks, and optimal control problems (OCPs). First, we introduce the controlled systems of generalized multiobjective games and establish the existence of the solutions for these systems using Browder-type fixed point theorem in the noncompact case and the $C_i$-quasi-concavity. Results on the convergence of controlled systems of the solutions for such problems using the auxiliary solution sets and the extended $C_i$-convexity of the objective functions are studied. Second, we investigate OCPs governed by generalized multiobjective games. The existence and convergence of the solutions to these problems are also obtained. Finally, as a real-world application, we consider the special case of controlled systems of traffic networks. Many examples are given for the illustration of our results.     

关于紧优双环网络的无限族

双环网络是计算机互连网络和通讯系统的一类重要拓扑结构．1993年,李乔等人提出一个系统的构造方法,构造出69类0紧优和33类1紧优双环网络的无限族,并提出研究下述问题:求k(k>1)紧优双环网络的无限族．2003年,徐俊明等人给出一个4紧优双环网络的无限族．本文首先证明从每一个具体的0紧优双环网络出发,都可以构造若干0紧优双环网络无限族;结合同余方程组理论和数论中的素数理论,给出若干求一般k(k≥0)紧优双环网络无限族(包括非单位步长双环网络无限族)的方法．     

k紧优双环网的无限族的构造

双环网是计算机互连网络和通讯系统的一类重要拓扑结构,已广泛应用于计算机互连网络拓扑结构的设计中.利用L形瓦理论,结合中国剩余定理和二次同余方程的性质,给出了不同于参考文献中的任意k紧优双环网的无限族的构造方法,证明了对任意正整数k,若n(t)=3t2 At B,A=1,3,5,对于一定的B＞(k 1)2,均存在正整数t,使得{G(n(t);s(t))}是k紧优双环网的无限族,而且这样的无限族有无穷多类.作为定理的应用,给出了多类新的k紧优双环网的无限族.