Queueing Dynamics and Maximal Throughput Scheduling in Switched Processing Systems

We study a processing system comprised of parallel queues, whose individual service rates are specified by a global service mode (configuration). The issue is how to switch the system between various possible service modes, so as to maximize its throughput and maintain stability under the most workload-intensive input traffic traces (arrival processes). Stability preserves the job inflow–outflow balance at each queue on the traffic traces. Two key families of service policies are shown to maximize throughput, under the mild condition that traffic traces have long-term average workload rates. In the first family of cone policies, the service mode is chosen based on the system backlog state belonging to a corresponding cone. Two distinct policy classes of that nature are investigated, MaxProduct and FastEmpty. In the second family of batch policies (BatchAdapt), jobs are collectively scheduled over adaptively chosen horizons, according to an asymptotically optimal, robust schedule. The issues of nonpreemptive job processing and non-negligible switching times between service modes are addressed. The analysis is extended to cover feed-forward networks of such processing systems/nodes. The approach taken unifies and generalizes prior studies, by developing a general trace-based modeling framework (sample-path approach) for addressing the queueing stability problem. It treats the queueing structure as a deterministic dynamical system and analyzes directly its evolution trajectories. It does not require any probabilistic superstructure, which is typically used in previous approaches. Probability can be superposed later to address finer performance questions (e.g., delay). The throughput maximization problem is seen to be primarily of structural nature. The developed methodology appears to have broader applicability to other queueing systems.     

General Solution for Hamiltonians with Extended Cubic and Quartic Potentials

In terms of hyperelliptic functions, we integrate a two-particle Hamiltonian with quartic potential and additional linear and nonpolynomial terms in the Liouville integrable cases 1:6:1 and 1:6:8.     

Higher-Order Convex Approximations of Young Measures in Optimal Control

The general theory of approximation of (possibly generalized) Young measures is presented, and concrete cases are investigated. An adjoint-operator approach, combined with quasi-interpolation of test integrands, is systematically used. Applicability is demonstrated on an optimal control problem for an elliptic system, together with one-dimensional illustrative calculations of various options.     

BV estimates of Lax-Friedrichs' scheme for a class of nonlinear hyperbolic conservation laws

We give uniform BV estimates and -stability of Lax-Friedrichs' scheme for a class of systems of strictly hyperbolic conservation laws whose integral curves of the eigenvector fields are straight lines, i.e., Temple class, under the assumption of small total variation. This implies that the approximate solutions generated via the Lax-Friedrichs' scheme converge to the solution given by the method of vanishing viscosity or the Godunov scheme, and then the Glimm scheme or the wave front tracking method.

     

<Emphasis Type="Italic">X</Emphasis>-Trees and Weighted Quartet Systems

In this note, we consider a finite set X and maps W from the set $ \mathcal{S}_{2|2} (X) $ of all 2, 2- splits of X into $ \mathbb{R}_{\geq 0} $. We show that such a map W is induced, in a canonical way, by a binary X-tree for which a positive length $ \mathcal{l} (e) $ is associated to every inner edge e if and only if (i) exactly two of the three numbers W(ab|cd),W(ac|bd), and W(ad|cb) vanish, for any four distinct elements a, b, c, d in X, (ii) $ a \neq d \quad\mathrm{and}\quad W (ab|xc) + W(ax|cd) = W(ab|cd) $ holds for all a, b, c, d, x in X with #{a, b, c, x} = #{b, c, d, x} = 4 and $ W(ab|cx),W(ax|cd) $ > 0, and (iii) $ W (ab|uv) \geq \quad \mathrm{min} (W(ab|uw), W(ab|vw)) $ holds for any five distinct elements a, b, u, v, w in X. Possible generalizations regarding arbitrary $ \mathbb{R} $-trees and applications regarding tree-reconstruction algorithms are indicated.AMS Subject Classification: 05C05, 92D15, 92B05.     

Strongly meager sets of size continuum

We will construct several models where there are no strongly meager sets of size 2⁰. First author partially supported by NSF grant DMS 0200671.Second author partially supported by Israel Science Foundation and NSF grant DMS 0072560. Publication 807. Mathematics Subject Classification (2000):03E15, 03E20     

Two-Step High Order Starting Values for Implicit Runge–Kutta Methods

In this article a simple form of expressing and studying the order conditions to be satisfied by starting algorithms for Runge–Kutta methods, which use information from the two previous steps is presented. In particular, starting algorithms of highest order for Runge–Kutta–Gauss methods up to seven stages are derived. Some numerical experiments with Hamiltonian systems to compare the behaviour of the new starting algorithms with other existing ones are presented.     

A New Technique for Ill-Conditioned Linear Systems

The technique we propose for solving ill-conditioned linear systems consists of two steps. First we compute the regularized solution on some values of the regularization parameter . Then we use these solutions either to extrapolate at =0 or to estimate the regularized solution with determined by the generalized cross validation or by the L-curve method.     

Discrete groups actions and corresponding modules

We address the problem of interrelations between the properties of an action of a discrete group on a compact Hausdorff space and the algebraic and analytical properties of the module of all continuous functions over the algebra of invariant continuous functions . The present paper is a continuation of our joint paper with M. Frank and V. Manuilov. Here we prove some statements inverse to the ones obtained in that paper: we deduce properties of actions from properties of modules. In particular, it is proved that if for a uniformly continuous action the module is finitely generated projective over , then the cardinality of orbits of the action is finite and fixed. Sufficient conditions for existence of natural conditional expectations are obtained.

     

On generalized hamiltonian systems

1. PreliminaryIt is well known that{1] a 8ymPlectic form is invariant along the trajectory of a Hamilto-nian system. Based on this fundamental property, certain techniques have been developed.The purpose of this paper is to extend such an approach to a wider class of dynamic systeIns,namely, genera1ized Hamiltonian systems. Our purpose is to investigate a class of dynaInicsystems, which possess a certain "geometric structure".Deflnition 1.1[1'2]. Let M be a tIlallifo1d. w E fl'(M) is call…