From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective

We design an algorithm, called the fluid synchronization algorithm (FSA), for the job shop scheduling problem with the objective of minimizing the makespan. We round an optimal solution to a fluid relaxation, in which we replace discrete jobs with the flow of a continuous fluid, and use ideas from fair queueing in the area of communication networks in order to ensure that the discrete schedule is close to the one implied by the fluid relaxation. FSA produces a schedule with makespan at most C _max+(I+2)P _max J _max, where C _max is the lower bound provided by the fluid relaxation, I is the number of distinct job types, J _max is the maximum number of stages of any job-type, and P _max is the maximum processing time over all tasks. We report computational results based on all benchmark instances chosen from the OR library when N jobs from each job-type are present. The results suggest that FSA has a relative error of about 10% for N=10, 1% for N=100, 0.01% for N=1000. In comparison to eight different dispatch rules that have similar running times as FSA, FSA clearly dominates them. In comparison to the shifting bottleneck heuristic whose running time and memory requirements are several orders of magnitude larger than FSA, the shifting bottleneck heuristic produces better schedules for small N (up to 10), but fails to provide a solution for larger values of N. Received: September 1999 / Accepted: September 2001?Published online March 14, 2002     

Diophantine Approximations on Fractals

We exploit dynamical properties of diagonal actions to derive results in Diophantine approximations. In particular, we prove that the continued fraction expansion of almost any point on the middle third Cantor set (with respect to the natural measure) contains all finite patterns (hence is well approximable). Similarly, we show that for a variety of fractals in [0, 1]², possessing some symmetry, almost any point is not Dirichlet improvable (hence is well approximable) and has property C (after Cassels). We then settle by similar methods a conjecture of M. Boshernitzan saying that there are no irrational numbers x in the unit interval such that the continued fraction expansions of {nx mod 1}_{n ? \mathbb N}{\{nx\,{\rm mod}\,1\}_{n \in {\mathbb N}}} are uniformly eventually bounded.     

Multiparametric dissipative linear stationary dynamical scattering systems: Discrete case, II: Existence of conservative dilations

In the present paper we introduce the notion of dilation of a multiparametric linear stationary dynamical system (systems of this type, in particular dissipative, and conservative scattering ones were first introduced in [6]). We establish the criterion for existence of a conservative dilation of a multiparametric dissipative scattering system. This allows to distinguish the class of so-calledN-dissipative systems preserving the most important properties of one-parametric dissipative scattering systems.Research supported in part by the Ukrainian-Israeli project of scientific co-operation (contract no. 2M/1516-97).     

A stability property of symplectic packing

We prove that for any closed symplectic 4-manifold (M,Ω) with [Ω]∈H ²(M, Q) there exists a number N ₀ such that for every N≥N ₀, (M,Ω) admits full symplectic packing by N equal balls. We also indicate how to compute this N ₀. Our approach is based on Donaldson's symplectic submanifold theorem and on tools from the framework of Taubes theory of Gromov invariants. Oblatum 9-I-1998 & 1-VII-1998 / Published online: 14 January 1999     

The traffic problem: Modeling of the overtaking

The classical microscopic single line follow‐the‐leader model of a road traffic may collapse in finite time due to a car collision. In order to avoid the collision, the natural action of a driver would be to overtake the slower car. We propose a simple model of overtaking assuming a circular road. The model is a dynamical system with discontinuous right‐hand side (the Filippov system). As a case study, we assumed that the system consists of N =3 identical cars. We studied a particular periodic solution (oscillatory pattern). We explored the possibility to use the standard software (AUTO97) to continue the pattern with respect to a parameter. Copyright © 2009 John Wiley & Sons, Ltd.     

Chaotic Motion of the N-Vortex Problem on a Sphere: I. Saddle-Centers in Two-Degree-of-Freedom Hamiltonians

We study the motion of N point vortices with N∈ℕ on a sphere in the presence of fixed pole vortices, which are governed by a Hamiltonian dynamical system with N degrees of freedom. Special attention is paid to the evolution of their polygonal ring configuration called the N -ring, in which they are equally spaced along a line of latitude of the sphere. When the number of the point vortices is N=5n or 6n with n∈ℕ, the system is reduced to a two-degree-of-freedom Hamiltonian with some saddle-center equilibria, one of which corresponds to the unstable N-ring. Using a Melnikov-type method applicable to two-degree-of-freedom Hamiltonian systems with saddle-center equilibria and a numerical method to compute stable and unstable manifolds, we show numerically that there exist transverse homoclinic orbits to unstable periodic orbits in the neighborhood of the saddle-centers and hence chaotic motions occur. Especially, the evolution of the unstable N-ring is shown to be chaotic.      

Truncated Erlangian queueing system with fuzzy arrival rate,balking and reneging

In this paper, we derive the performance measures of the truncated Erlangian service queueing system with state-dependent rate, balking and reneging with fuzzy arrival rate _n\tilde \lambda _n so for the (M/E _r /1/N(α, β)), we have obtained P _n,s the steady state probabilities in the system with the unit in the service being at stage s (s=1, 2, …, r); k is the boundary state for the number of customer more than the one that the rate of service increases. We treat this queueing system for general values of r, k and N and derive the Fuzzy effective measures for the operation of the system at any time.     

On the number of points of bounded height¶on arithmetic projective spaces

Let K be a number field and its ring of integers. Let be a Hermitian vector bundle over . In the first part of this paper we estimate the number of points of bounded height in (generalizing a result by Schanuel). We give then some applications: we estimate the number of hyperplanes and hypersurfaces of degree d>1 in of bounded height and containing a fixed linear subvariety and we estimate the number of points of height, with respect to the anticanonical line bundle, less then T (when T goes to infinity) of ℙ ^N _K blown up at a linear subspace of codimension two. Received: 20 February 1998 / Revised version: 9 November 1998     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

Minimal subsystems of affine dynamics on local fields

We describe the dynamics of an arbitrary affine dynamical system on a local field by exhibiting all its minimal subsystems. In the special case of the field \mathbbQ_p{\mathbb{Q}_p} of p-adic numbers, for any non-trivial affine dynamical system, we prove that the field \mathbbQ_p{\mathbb{Q}_p} is decomposed into a countable number of invariant balls or spheres each of which consists of a finite number of minimal subsets. Consequently, we give a complete classification of topological conjugacy for non-trivial affine dynamics on \mathbbQ_p{\mathbb{Q}_p} . For each given prime p, there is a finite number of conjugacy classes.     

Vortex Motion and the Geometric Phase. Part II. Slowly Varying Spiral Structures

Summary. We derive formulas for the long time evolution of passive interfaces in three ``canonical' incompressible, inviscid, two-dimensional flow models. The point vortex models, introduced in Part 1 [1] are (i) a ``restricted' three-vortex problem, (ii) a vortex and a particle in a closed circular domain, and (iii) a particle in the flowfield of a mixing layer model undergoing a vortex pairing instability. In each configuration, it was shown in Part 1 that the passive particle exhibits a geometric or Hannay-Berry phase over long time periods induced by the slowly varying periodic background field. In this paper we show how the formula for the evolution of a passive interface driven by the dynamics of the vortices inherits this geometric phase effect. The interface wraps into a spiral formation around the ``parent' vortex, with a slowly varying component induced by the farfield vorticity. The length formula for the long time growth of the slowly rotating spiral decomposes into a ``dynamic' part and a ``geometric' part. The dynamic part is the length in the ``unperturbed' system—i.e., in the absence of the background field—and the geometric part is the contribution of the geometric phase θ _g for a passive particle in the flow. We derive the following simple formula for an interface along a smooth curve joining two arbitrary particles labelled A and B . Define as the difference in interface lengths between the ``unperturbed' system and the ``perturbed' slowly varying system at the end of the long time period T . In each case, , where ξ is the radial coordinate parametrizing the interface at t=0 . Received September 4, 1997; second revision received January 16, 1998; accepted January 27, 1998     

Elliptic curves of odd modular degree

The modular degree m _E of an elliptic curve E/Q is the minimal degree of any surjective morphism X ₀(N) → E, where N is the conductor of E. We give a necessary set of criteria for m _E to be odd. In the case when N is prime our results imply a conjecture of Mark Watkins. As a technical tool, we prove a certain multiplicity one result at the prime p = 2, which may be of independent interest. Supported in part by the American Institute of Mathematics. Supported in part by NSF grant DMS-0401545.     

Dynamic of Threshold Solutions for Energy-Critical NlS

We consider the energy-critical non-linear focusing Schr?dinger equation in dimension N = 3, 4, 5. An explicit stationary solution, W, of this equation is known. In [KeM], the energy E(W) has been shown to be a threshold for the dynamical behavior of solutions of the equation. In the present article, we study the dynamics at the critical level E(u) = E(W) and classify the corresponding solutions. This gives in particular a dynamical characterization of W. Received: March 2007, Accepted: October 2007     

Coexistence of domains of attraction of nonautonomous neural networks with time-varying delays

This paper presents new dynamical behavior, i.e., the coexistence of 2^N domains of attraction of N-dimensional nonautonomous neural networks with time-varying delays. By imposing some new assumptions on activation functions and system parameters, we construct 2^N invariant basins for neural system and derive some criteria on the boundedness and exponential attractivity for each invariant basin. Particularly, when neural system degenerates into periodic case, we not only attain the coexistence of 2^N periodic orbits in bounded invariant basins but also give their domains of attraction. Moreover, our results are suitable for autonomous neural systems. Our new results improve and generalize former ones. Finally, computer simulation is performed to illustrate the feasibility of our results.     

Attractors for autonomous double‐diffusive convection systems based on Brinkman–Forchheimer equations

In this paper, we consider the existence of global attractor and exponential attractor for some dynamical system generated by nonlinear parabolic equations in bounded domains with the dimension N≤4 which describe double‐diffusive convection phenomena in a porous medium. We deal with both of homogeneous Dirichlet and Neumann boundary condition cases. Especially, when Neumann condition is imposed, we need some assumptions and restrictions for the external forces and the average of initial data, since the mass conservation law holds. Copyright © 2015 John Wiley & Sons, Ltd.     

Conservation of Geometric Structures for Non-Homogeneous Inviscid Incompressible Fluids

In this article we get a result on propagation of geometric properties for solutions of the non-homogeneous incompressible Euler system in any dimension N ≥ 2. In particular, we investigate conservation of striated and conormal regularity, which generalize the 2-D structure of vortex patches. The results we get are only local in time, even for N = 2; however, we provide an explicit lower bound for the lifespan of the solution. In the case of physical dimension N = 2 or 3, we investigate also propagation of Hölder regularity in the interior of a bounded domain.     

Tensor product methods for stochastic problems

In the solution of stochastic partial differential equations (SPDEs) the generally already large dimension N of the algebraic system resulting from the spatial part of the problem is blown up by the huge number of degrees of freedom P coming from the stochastic part. The number of degrees of freedom of the full system will be NP, which poses severe demands on memory and processor time. We present a method how to approximate the system by a data-sparse tensor product (based on the Karhunen-Loève decomposition with M terms), which uses only memory in the order of M (N + P), and how to keep this representation also inside the iterative solvers. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dynamics groups of asynchronous cellular automata

We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is π-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate the dynamics group. We have previously shown that exactly 104 of the possible 2²³=2562^{2^{3}}=256 cellular automaton rules are π-independent. In the article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.     

On Powerful Normal Subgroups of a p-Group

 In this paper we investigate the action of a p-group G on its powerful normal subgroup N. We shall mainly be concerned to find conditions which guarantee that G acts uniserially on N. We shall also study what consequences uniserial action on N has on the structure of N. (Received 21 August 1998; in revised form 28 June 1999)