Degenerate bifurcation giving rise to a cycle in multiparameter problems in hydrodynamics

An algorithm for constructing the Lyapunov-Schmidt series in multiparameter problems with quadratic non-linearity is proposed, which enables a degenerate bifurcation of cycle generation to be investigated using the Weierstrass preparation theorem. The use of this algorithm to study multiparameter problems of hydrodynamics, namely, Kolmogorov flow and the Couette-Poiseuille flow in a plane channel is considered.     

二维拟定常可压流Euler方程组的简单波

简单波是这样的流动,它在像空间中的像是一条曲线．“简单波理论是除基本流动结构以外构造流动问题的解的基础”,见Courant和Friedrichs的经典著作《超声速流与冲击波》．该文主要研究二维拟定常可压流Euler方程组的简单波的几何结构.根据这些几何诠释,还构造了绕一拟流线弯曲部的疏散和压缩的简单波流动结构．这种流动结构将作为一个局部流动结构出现在4个接触间断的Riemann问题的整体解中．     

The problem of obtaining prescribed distributions of gas parameters

Using one-dimensional cylindrically and spherically symmetric flows as examples, the following problem is investigated in which a prescribed density distribution in a gas is obtained: given a known gas flow (background flow), it is required to continuously attach another, unknown gas flow whose density distribution at a fixed instant of time is described by some previously given function. It is shown that this problem is a characteristic Cauchy problem of standard type for which there is a valid analogue of the Kovalevskaya theorem, provided that the input data are analytic. Other problems of the same type are considered: to ensure that the unknown flow will have a prescribed gas velocity distribution and the prescribed density of the gas in the unknown flow is strictly greater than that of the gas in the background flow (flow with discontinuity). On the assumption that the input data to these problems are analytic, the existence and uniqueness of solutions are proved, in fact—of piecewise analytic solutions. The theorems proved are extended to the case of non-one-dimensional flows.     

The flow circulation sharing problem

The flow circulation sharing problem is defined as a network flow circulation problem with a maximin objective function. The arcs in the network are partitioned into regular arcs and tradeoff arcs where each tradeoff arc has a non-decreasing tradeoff function associated with it. All arcs have lower and upper bounds on their flow while the value of the smallest tradeoff function is maximized. The model is useful in equitable resource allocation problems over time which is illustrated in a coal strike example and a submarine assignment example. Some properties including optimality conditions are developed. Each cut in the network defines a knapsack sharing problem which leads to an optimality condition similar to the max flow/min cut theorem. An efficient algorithm for both the continuous and integer versions of the flow circulation sharing problem is developed and computational experience given. In addition, efficient algorithms are developed for problems where some of the arcs have infinite flow upper bounds.     

广义多品种最小费用流问题的对偶理论

基于广义多品种最小费用流问题的性质，将问题转化成一对含有内、外层问题的双水平规划，内层规划实际是单品种费用流问题，而外层问题是分离的凸规划，使用相关的凸分析理论，导出了广义多品种最小费用流问题的对偶规划，对偶定理和Kuhn-Tucker条件。     

Games,Critical Paths and Assignment Problems in Permutation Flow Shops and Cyclic Scheduling Flow Line Environments

In this paper we address the non-pre-emptive flow shop scheduling problem for makespan minimization in a new modelling framework. A lower bound generation scheme is developed by using appropriately defined linear assignment problems and, based on this new approach, a special class of permutation flow shop problems is identified. We present a game theoretic interpretation of our modelling approach which leads to an integer programming formulation of the scheduling problem. A new branch and bound scheme is developed based on these results. The major advantage of our modelling framework and branch-and- bound approach is that it can be easily extended to address a general class of cyclic scheduling problems for production flow lines with blocking. After a discussion of this extension, we report on computational experience that indicates the very satisfactory performance of the new optimal solution procedure for cyclic scheduling problems with finite capacity buffers.     

Network flow problems with pricing decisions

This paper considers a class of network flow problems in which the demand levels of the nodes are determined through pricing decisions representing the revenue received per unit demand at the nodes. We must simultaneously determine the pricing decisions and the network flow decisions in order to maximize profits, i.e., the revenues received from the pricing decisions minus the cost of the network flow decisions. Specializations of this class of problems have numerous applications in supply chain management. We show that the class of problems with a single pricing decision throughout the network can be solved in polynomial time under both continuous pricing restrictions and integer pricing restrictions. For the class of problems with customer-specific pricing decisions, we provide conditions under which the problem can be solved in polynomial-time for continuous pricing restrictions and prove that the problem is NP-hard for integer pricing restrictions.     

Minimizing makespan in parallel flowshops

In this study, a new class of proportional parallel flow shop problems with the objective of minimizing the makespan has been addressed. A special case for this problem in which jobs are processed on only one machine as opposed to two or more machines in a flow shop, is the well-known multiple processor problem which is NP-complete. The parallel processor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic and simulation approaches to solve large scale problems, while using exact procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the truncated integer programming solution are reported. The performance of the heuristics and the simulation results were encouraging.     

Optimal Two-commodity Flows with Non-linear Cost Functions

We consider networks in which two different commodities have to be transported across undirected arcs, subject to a shared capacity on the arcs. For each arc and commodity there is an associated non-linear cost that depends on the amount of the commodity transported across the arc. The aim is to minimize the sum of the costs over all arcs and commodities. Efficient algorithms for solving this problem for two types of objective functions will be presented: in the first the cost depends on the absolute value of the flow and in the second the cost is a quadratic function of the flow. Previous work on multi-commodity flow has concentrated on linear cost problems or tackled non-linear cost problems with Lagrangian relaxation methods and other more general techniques. The algorithms in this paper, on the other hand, provide a very efficient way of dealing with two types of non-linear two-commodity optimal flow problems.     

Heuristic and stochastic methods in optimization

The shifting bottleneck (SB) heuristic is among the most successful approximation methods for solving the job shop problem. It is essentially a machine based decomposition procedure where a series of one machine sequencing problems (OMSPs) are solved. However, such a procedure has been reported to be highly ineffective for the flow shop problems. In particular, we show that for the 2-machine flow shop problem, the SB heuristic will deliver the optimal solution in only a small number of instances. We examine the reason behind the failure of the machine based decomposition method for the flow shop. An optimal machine based decomposition procedure is formulated for the 2-machine flow shop, the time complexity of which is worse than that of the celebrated Johnson’s rule. The contribution of the present study lies in showing that the same machine based decomposition procedures which are so successful in solving complex job shops can also be suitably modified to optimally solve the simpler flow shops.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

Analysis of traffic flow by the finite element method

A finite elernent methodology is developed for the numerical solution of traffic flow problems encountered in arterial streets. The simple continuum traffic flow model consisting of the equation of continuity and an equilibrium flow-density relationship is adopted. A Galerkin type finite element method is used to formulate the problem in discrete form and the solution is obtained by a step-by-step time integration in conjunction with the Newton-Raphson method. The proposed finite element methodology, which is of the shock capturing type, is applied to flow traffic problems. Two numerical examples illustrate the method and demonstrate its advantages over other analytical or numerical techniques.     

Gas dynamics applications of a characteristic Cauchy problem

Some initial-boundary-value problems for a system of quasilinear partial differential equations of gas dynamics with the initial data prescribed on the characteristic surface (characteristic Cauchy problem) are considered. The following three-dimensional flow problems are investigated: the flow produced by a motion of an impermeable piston; the flow produced by a permeable piston with a given pressure; and the flow produced by the moving free boundary. In the first two problems, the piston motion is prescribed; in the last problem, the free boundary motion cannot be prescribed in advance and must be determined as a part of the problem. It is shown that those problems can be reduced to a characteristic Cauchy problem of a certain standard type that satisfies the analog of Cauchy-Kowalewski's existence theorem in the class of analytical functions (Differential Equations 12 (1977) 1438-1444). Thus, it is proved that, in the case of the analyticity of the input data, the considered problems have unique piecewise analytic solutions which may be expressed by infinite power series (the procedure of constructing the power series solution is described in Differential Equations 12 (1977) 1438-1444 as a part of the proof of the theorem).     

Viscosity-splitting scheme for the Navier-Stokes equations

A viscosity-splitting scheme for the initial boundary value problems of the Navier-Stokes equations is considered. In the scheme, the Stokes equation is solved in conjunction with a nonhomogeneous boundary condition which connects the tangent flow with a no-slip flow. Convergence is proved.     

On the Theory of Mixed-Type Equations

We briefly review different well-posed boundary-value problems for mixed-type equations and their applications in transonic gas dynamics. We present barotropic relations for plane-parallel flow of a compressible gas that leads to mixed-type model equations on the hodograph plane. We also discuss the question on the existence of transonic solutions of profile flow problems, which is closely related to Dirichlet problems in mixed-type domains.__________Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 10, Suzdal Conference-4, 2003.     

Opposing flows in a one dimensional convection-diffusion problem

In this paper, we examine a particular class of singularly perturbed convection-diffusion problems with a discontinuous coefficient of the convective term. The presence of a discontinuous convective coefficient generates a solution which mimics flow moving in opposing directions either side of some flow source. A particular transmission condition is imposed to ensure that the differential operator is stable. A piecewise-uniform Shishkin mesh is combined with a monotone finite difference operator to construct a parameter-uniform numerical method for this class of singularly perturbed problems.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems

Traditionally, minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.