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.     

Dynamic Global Constraints in Backtracking Based Environments

Global constraints provide strong filtering algorithms to reduce the search space when solving large combinatorial problems. In this paper we propose to make the global constraints dynamic, i.e., to allow extending the set of constrained variables during search. We describe a generic dynamisation technique for an arbitrary monotonic global constraint and we compare it with the semantic-based dynamisation for the alldifferent constraint. At the end we sketch a dynamisation technique for non-monotonic global constraints. A comparison with existing methods to model dynamic problems is given as well.     

Skorokhod decomposition of reflected diffusions on bounded Lipschitz domains with singular non-reflection part

Let be a compact set with interior G. Let L ¹ (G,dx), >0 dx-a.e. on G, and m:=dx. Let A=(a _ij ) be symmetric, and globally uniformly strictly elliptic on G. Let be such that ; f, , is closable in L ² (G,m) with closure ( ^r ,D( ^r )). The latter is fulfilled if satisfies the Hamza type condition, or _i L ¹ _loc (G,dx), 1id. Conservative, non-symmetric diffusion processes X _t related to the extension of a generalized Dirichlet form where satisfies are constructed and analyzed. If G is a bounded Lipschitz domain, H ^1,1 (G), and a _ij D( ^r ), a Skorokhod decomposition for X _t is given. This happens through a local time that is uniquely associated to the smooth measure 1_{{ Tr ()>0}} d, where Tr denotes the trace and the surface measure on G.This research has been financially supported by TMR grant HPMF-CT-2000-00942 of the European Union. Mathematics Subject Classification (2000): 60J60, 60J55, 31C15, 31C25, 35J25     

Some Limit Theorems in Geometric Processes

Geometric process (GP) was introduced by Lam[4,5], it is defined as a stochastic process {Xn, n = 1, 2,…} for which there exists a real number a > 0, such that {an-1 Xn, n = 1,2, …} forms a renewal process (RP). In this paper, we study some limit theorems in GP. We first derive the Wald equation for GP and then obtain the limit theorems of the age, residual life and the total life at t for a GP. A general limit theorem for Sn with a > 1 is also studied. Furthermore, we make a comparison between GP and RP, including the comparison of their limit distributions of the age, residual life and the total life at t.     

Asymptotic behavior of solutions to scalar conservation laws and optimal convergence orders to N-waves

The goal of this article is to develop a new technique to obtain better asymptotic estimates for scalar conservation laws. General convex flux, f″(u)?0, is considered with an assumption . We show that, under suitable conditions on the initial value, its solution converges to an N-wave in L¹ norm with the optimal convergence order of O(1/t). The technique we use in this article is to enclose the solution with two rarefaction waves. We also show a uniform convergence order in the sense of graphs. A numerical example of this phenomenon is included.     

The Boson Normal Ordering Problem and Generalized Bell Numbers

For any function F(x) having a Taylor expansion we solve the boson normal ordering problem for $F [(a^\dag)^r a^s]$, with r, s positive integers, $F [(a, a^\dag]=1$, i.e., we provide exact and explicit expressions for its normal form $\mathcal{N} \{F [(a^\dag)^r a^s]\} = F [(a^\dag)^r a^s]$, where in $ \mathcal{N} (F) $ all a's are to the right. The solution involves integer sequences of numbers which, for $ r, s \geq 1 $, are generalizations of the conventional Bell and Stirling numbers whose values they assume for $ r=s=1 $. A complete theory of such generalized combinatorial numbers is given including closed-form expressions (extended Dobinski-type formulas), recursion relations and generating functions. These last are special expectation values in boson coherent states.AMS Subject Classification: 81R05, 81R15, 81R30, 47N50.     

On the polynomial-space completeness of intuitionistic propositional logic

We present an alternative, purely semantical and relatively simple, proof of the Statman's result that both intuitionistic propositional logic and its implicational fragment are PSPACE-complete.This paper was supported by grant 401/01/0218 of the Grant Agency of the Czech Republic. % Mathematics Subject Classification (2000):     

The Structure of the (Outer) Automorphism Group of a Bieberbach Group

Referring to Tits alternative, we develop a necessary and sufficient condition to decide whether the normalizer of a finite group of integral matrices is polycyclic-by-finite or is containing a non-Abelian free group. This result is of fundamental importance to conclude whether the (outer) automorphism group of a Bieberbach group is polycyclic-by-finite or has a non-cyclic free subgroup.     

Analytic models for commuting operator tuples on bounded symmetric domains

For a domain in and a Hilbert space of analytic functions on which satisfies certain conditions, we characterize the commuting -tuples of operators on a separable Hilbert space  such that is unitarily equivalent to the restriction of to an invariant subspace, where is the operator -tuple on the Hilbert space tensor product  . For the unit disc and the Hardy space , this reduces to a well-known theorem of Sz.-Nagy and Foias; for a reproducing kernel Hilbert space on such that the reciprocal of its reproducing kernel is a polynomial in and  , this is a recent result of Ambrozie, Müller and the second author. In this paper, we extend the latter result by treating spaces for which ceases to be a polynomial, or even has a pole: namely, the standard weighted Bergman spaces (or, rather, their analytic continuation) on a Cartan domain corresponding to the parameter in the continuous Wallach set, and reproducing kernel Hilbert spaces for which is a rational function. Further, we treat also the more general problem when the operator is replaced by ,  being a certain generalization of a unitary operator tuple. For the case of the spaces on Cartan domains, our results are based on an analysis of the homogeneous multiplication operators on , which seems to be of an independent interest.

     

The Orders of Related Elements of a Finite Field

All finite fields q (q 2, 3, 4, 5, 7, 9, 13, 25, 121) contain a primitive element for which + 1/ is also primitive. All fields of square order q ² (q 3, 5) contain an element of order q + 1 for which + 1/ is a primitive element of the subfield q. These are unconditional versions of general asymptotic results.