Maximum flow in a network with fuzzy arc capacities

Our main concern is the maximum flow in a network in which an excess over the beforehand fixed quota of arc capacity is admissible. The problem is represented as a partially fuzzy linear programming task. A theorem equivalent to the Ford and Fulkerson one concerning the classic task of maximum flow is proved in the paper. An algorithm for searching maximum flow assuming integer values of flows on network arcs is presented.     

Real-valued flows in a network with fuzzy arc capacities

The problem of the maximal (minimal) flow in a network with fuzzy capacity constraints is considered. A theorem being a natural direct generalization of the Ford-Fulkerson theorem relating the flow value with cut capacities in the network is proved. A simple algorithm, based on the mentioned theorem, for the determination of optimal real-valued flows is developed.     

突发交通事件非参数诊断的变点统计方法研究

针对智能运输系统(ITS)项目特别是先进的出行信息系统的开发，建立了突发交通事件非线性非参数诊断的变点统计方法。依据交通流理论，结合均值变点模型，对变点搜索的最小二乘法和局部比较法进行了研究。利用在英国南安普敦市检获的实际数据对上述两种算法进行了标定，并对模型进行实际应用。结果显示上述方法对突发事件检测具有很高的灵敏度和有效性。     

An improved algorithm for decomposing arc flows into multipath flows

We consider a multipath maximum flow problem introduced by Kishimoto (Networks 27(4)(1996)279-291). The focus is on efficient transformation from arc flows into multipath flows, where a multipath flow is a nonnegative combination of multipaths. A new algorithm that is more efficient than existing ones is proposed for the transformation.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

最大利润流问题及算法

最大利润流是以运输利润最大为目标的网络优化问题 .一个利润可行流可分解为若干个路流和圈流 ,相应地该可行流的利润也等于这些路流和圈流的利润之和 .本文证明了一个可行流为最大利润流的充要条件是不存在利润增广路 ,并据此提出了求解算法 .文章最后给出了一个计算实例 .     

A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such “combinatorial augmentation algorithm” for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The “pivots” in the algorithm are determined by choosing an >0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by . In this sense, it generalizes the cycle cancelling algorithms for (single source) mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.     

A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time

We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n ² m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214.     

Optimal Scheduling of a Two-stage Hybrid Flow Shop

We present an exact branch-and-bound algorithm for the two-stage hybrid flow shop problem with multiple identical machines in each stage. The objective is to schedule a set of jobs so as to minimize the makespan. This is the first exact procedure which has been specifically designed for this strongly -hard problem. Among other features, our algorithm is based on the exact solution of identical parallel machine scheduling problems with heads and tails. We report the results of extensive computational experiments on instances which show that the proposed algorithm solves large-scale instances in moderate CPU time.     

Fast technique for solving the <Emphasis Type="Italic">N</Emphasis>-body problem in flow simulation by vortex methods

A fast algorithm is proposed for solving the N-body problem arising in flow simulation when the flow is represented as a set of many interacting vortex elements. The algorithm is used to compute the flow over a circular cylinder at high Reynolds numbers.     

Time-harmonic acoustic propagation in the presence of a shear flow

This work deals with the numerical simulation, by means of a finite element method, of the time-harmonic propagation of acoustic waves in a moving fluid, using the Galbrun equation instead of the classical linearized Euler equations. This work extends a previous study in the case of a uniform flow to the case of a shear flow. The additional difficulty comes from the interaction between the propagation of acoustic waves and the convection of vortices by the fluid. We have developed a numerical method based on the regularization of the equation which takes these two phenomena into account. Since it leads to a partially full matrix, we use an iterative algorithm to solve the linear system.     

Adaptive dynamic cost updating procedure for solving fixed charge network flow problems

We approximate the objective function of the fixed charge network flow problem (FCNF) by a piecewise linear one, and construct a concave piecewise linear network flow problem (CPLNF). A proper choice of parameters in the CPLNF problem guarantees the equivalence between those two problems. We propose a heuristic algorithm for solving the FCNF problem, which requires solving a sequence of CPLNF problems. The algorithm employs the dynamic cost updating procedure (DCUP) to find a solution to the CPLNF problems. Preliminary numerical experiments show the effectiveness of the proposed algorithm. In particular, it provides a better solution than the dynamic slope scaling procedure in less CPU time. Research was partially supported by NSF and Air Force grants.     

加权完工时间和的调整时间可分离Flow shop排序问题

讨论了2台机器调整时间可分离的FlowShop排序问题,目标函数为极小化加权完工时间和.给出了对于一种特殊情况,问题存在多项式最优算法的充分条件.接着又给出了求解该问题的一个分枝定界法.     

On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks

In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network, where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of flow on an arc. The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum time. The main contribution of this paper is the time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent minimum time dynamic flow problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink. An optimal solution to the latter problem is guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the time-dependent evacuation and the time-dependent quickest transshipment problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

Coupling nonlinear Stokes and Darcy flow using mortar finite elements

We study a system composed of a nonlinear Stokes flow in one subdomain coupled with a nonlinear porous medium flow in another subdomain. Special attention is paid to the mathematical consequence of the shear-dependent fluid viscosity for the Stokes flow and the velocity-dependent effective viscosity for the Darcy flow. Motivated by the physical setting, we consider the case where only flow rates are specified on the inflow and outflow boundaries in both subdomains. We recast the coupled Stokes–Darcy system as a reduced matching problem on the interface using a mortar space approach. We prove a number of properties of the nonlinear interface operator associated with the reduced problem, which directly yield the existence, uniqueness and regularity of a variational solution to the system. We further propose and analyze a numerical algorithm based on mortar finite elements for the interface problem and conforming finite elements for the subdomain problems. Optimal a priori error estimates are established for the interface and subdomain problems, and a number of compatibility conditions for the finite element spaces used are discussed. Numerical simulations are presented to illustrate the algorithm and to compare two treatments of the defective boundary conditions.     

On the Decay Rates of Buffers in Continuous Flow Lines

Consider a tandem system of machines separated by infinitely large buffers. The machines process a continuous flow of products, possibly at different speeds. The life and repair times of the machines are assumed to be exponential. We claim that the overflow probability of each buffer has an exponential decay, and provide an algorithm to determine the exact decay rates in terms of the speeds and the failure and repair rates of the machines. These decay rates provide useful qualitative insight into the behavior of the flow line. In the derivation of the algorithm we use the theory of Large Deviations.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.     

无容量限制的最小费用流问题

本文研究了无容量限制的带固定费用和可变费用的单物资和二物资的最小费用流问题,并分别给出了多项式算法.最后应用该算法,计算了一个二物资的最小费用流问题的实例.     

A specialized network simplex algorithm for the constrained maximum flow problem

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.     

Dynamic responses of shear flows over a deformable porous surface layer in a cylindrical tube

This paper investigates dynamic responses of a viscous fluid flow introduced under a time dependent pressure gradient in a rigid cylindrical tube that is lined with a deformable porous surface layer. With the Darcy’s law and a linear elasticity assumption, we have solved the coupling effect of the fluid movement and the deformation of the porous medium in the Laplace transform space. Governing equations are deduced for the solid displacement and the fluid velocity in the porous layer. Analytical solutions in the transformed domain are derived and the time dependent variables are inverted numerically using Durbin’s algorithm. Interaction between the solid and the fluid phases in the porous layer and its effects on fluid flow in tube are investigated under steady and unsteady flow conditions when the solid phase is either rigid or deformable. Examples are presented for flows driven by a Heaviside or a sinusoid pressure gradient. Significant effects of the porous surface layer on the flow in the tube are observed. The analytical solutions can be used to test more complicated numerical schemes.