A mathematical programming approach to optimal Markovian switching of Poisson arrival streams to queueing systems

Motivated by certain situations in manufacturing systems and communication networks, we look into the problem of maximizing the profit in a queueing system with linear reward and cost structure and having a choice of selecting the streams of Poisson arrivals according to an independent Markov chain. We view the system as a MMPP/GI/1 queue and seek to maximize the profits by optimally choosing the stationary probabilities of the modulating Markov chain. We consider two formulations of the optimization problem. The first one (which we call the PUT problem) seeks to maximize the profit per unit time whereas the second one considers the maximization of the profit per accepted customer (the PAC problem). In each of these formulations, we explore three separate problems. In the first one, the constraints come from bounding the utilization of an infinite capacity server; in the second one the constraints arise from bounding the mean queue length of the same queue; and in the third one the finite capacity of the buffer reflect as a set of constraints. In the problems bounding the utilization factor of the queue, the solutions are given by essentially linear programs, while the problems with mean queue length constraints are linear programs if the service is exponentially distributed. The problems modeling the finite capacity queue are non-convex programs for which global maxima can be found. There is a rich relationship between the solutions of the PUT and PAC problems. In particular, the PUT solutions always make the server work at a utilization factor that is no less than that of the PAC solutions.

Queue Length Simulations in a Finite Single-line Queueing System with Repeated Calls

2000 Mathematics Subject Classification: 60K25.

Wigner distributions for finite-state systems without redundant phase-point operators

We set up Wigner distributions for N-state quantum systems following a Dirac-inspired approach. In contrast to much of the work in this study, requiring a 2N x 2N phase space, particularly when N is even, our approach is uniformly based on an N x N phase-space grid and thereby avoids the necessity of having to invoke a `quadrupled' phase space and hence the attendant redundance. Both N odd and even cases are analysed in detail and it is found that there are striking differences between the two. While the N odd case permits full implementation of the marginal property, the even case does so only in a restricted sense. This has the consequence that in the even case one is led to several equally good definitions of the Wigner distributions as opposed to the odd case where the choice turns out to be unique.

Exact static polarizabilities of correlated finite model systems

A finite-field method for calculating exact polarizabilities of correlated conjugated model systems within the valence bond (VB) framework is presented. The correlations reduce the polarizabilities from their noninteracting values and extend the range of linearity to higher external fields. The large nonlinear polarizabilities observed in strongly correlated conjugated organic molecules cannot be directly attributed to electron correlations. The method described can be employed to calculate static polarizabilities for any desired state of a correlated system.

Performability Analysis of Fork-Join Queueing Systems

Fork-join queueing systems offer a natural modelling paradigm for parallel processing systems and for assembly operations in automated manufacturing. The analysis of fork-join queueing systems has been an important subject of research in recent years. Existing analysis methodologies-both exact and approximate-assume that the servers are failure-free. In this study, we consider fork-join queueing systems in the presence of server failures and compute the cumulative distribution of performability with respect to the response time of such systems. For this, we employ a computational methodology that uses a recent technique based on randomization. We compare the performability of three different fork-join queueing models proposed in the literature: the distributed model, the centralized splitting model, and the split-merge model. The numerical results show that the centralized splitting model offers the highest levels of performability, followed by the distributed splitting and split-merge models.

On the optimality of exhaustive service policies in multiclass queueing systems with modulated arrivals and switchovers

Consider a single-server multiclass queueing system with K classes where the individual queues are fed by K-correlated interrupted Poisson streams generated in the states of a K-state stationary modulating Markov chain. The service times for all the classes are drawn independently from the same distribution. There is a setup time (and/or a setup cost) incurred whenever the server switches from one queue to another. It is required to minimize the sum of discounted inventory and setup costs over an infinite horizon. We provide sufficient conditions under which exhaustive service policies are optimal. We then present some simulation results for a two-class queueing system to show that exhaustive, threshold policies outperform non-exhaustive policies.

Statistical theory of finite Fermi systems with chaotic excited eigenstates

A theory of strongly interacting Fermi systems of a few particles is developed. At high excit at ion energies (a few times the single-parti cle level spacing) these systems are characterized by an extreme degree of complexity due to strong mixing of the shell-model-based many-part icle basis st at es by the residual two- body interaction. This regime can be described as many-body quantum chaos. Practically, it occurs when the excitation energy of the system is greater than a few single-particle level spacings near the Fermi energy. Physical examples of such systems are compound nuclei, heavy open shell atoms (e.g. rare earths) and multicharged ions, molecules, clusters and quantum dots in solids. The main quantity of the theory is the strength function which describes spreading of the eigenstates over many-part icle basis states (determinants) constructed using the shell-model orbital basis. A nonlinear equation for the strength function is derived, which enables one to describe the eigenstates without diagonalization of the Hamiltonian matrix. We show how to use this approach to calculate mean orbital occupation numbers and matrix elements between chaotic eigenstates and introduce typically statistical variable s such as t emperature in an isolated microscopic Fermi system of a few particles.

Correlation approach to work extraction from finite quantum systems

Reversible work extraction from identical quantum systems via collective operations was shown to be possible even without producing entanglement among the sub-parts. Here, we show that implementing such global operations necessarily imply the creation of quantum correlations, as measured by quantum discord. We also reanalyze the conditions under which global transformations outperform local gates as far as maximal work extraction is considered by deriving a necessary and sufficient condition that is based on classical correlations.

Average ground-state energy of finite Fermi systems

Semiclassical theories such as the Thomas-Fermi and Wigner-Kirkwood methods give a good description of the smooth average part of the total energy of a Fermi gas in some external potential when the chemical potential is varied. However, in systems with a fixed number of particles N, these methods overbind the actual average of the quantum energy as N is varied. We describe a theory that accounts for this effect. Numerical illustrations are discussed for fermions trapped in a harmonic oscillator potential and in a hard-wall cavity, and for self-consistent calculations of atomic nuclei. In the latter case, the influence of deformations on the average behavior of the energy is also considered.

Back-to-back correlations in finite expanding systems

Back-to-Back Correlations (BBC) of particle-antiparticle pairs are predicted to appear if hot and dense hadronic matter is formed in high energy nucleus-nucleus collisions. The BBC are related to in-medium mass-modification and squeezing of the quanta involved. Although the suppression of finite emission times were already known, the effects of finite system sizes and of collective phenomena had not been studied yet. Thus, for testing the survival and magnitude of the effect in more realistic situations, we study the BBC when mass-modification occurs in a finite sized, thermalized medium, considering a non-relativistically expanding fireball with finite emission time, and evaluating the width of the back-to-back correlation function. We show that the BBC signal indeed survives the expansion and flow effects, with sufficient magnitude to be observed at RHIC.

Strong Local Passivity in Finite Quantum Systems

Passive states of quantum systems are states from which no system energy can be extracted by any cyclic (unitary) process. Gibbs states of all temperatures are passive. Strong local (SL) passive states are defined to allow any general quantum operation, but the operation is required to be local, being applied only to a specific subsystem. Any mixture of eigenstates in a system-dependent neighborhood of a nondegenerate entangled ground state is found to be SL passive. In particular, Gibbs states are SL passive with respect to a subsystem only at or below a critical system-dependent temperature. SL passivity is associated in many-body systems with the presence of ground state entanglement in a way suggestive of collective quantum phenomena such as quantum phase transitions, superconductivity, and the quantum Hall effect. The presence of SL passivity is detailed for some simple spin systems where it is found that SL passivity is neither confined to systems of only a few particles nor limited to the near vicinity of the ground state.

Block envelope solution of finite difference systems /

"November, 1975."--T.p.

Finite connectivity systems as error-correcting codes

We investigate the performance of parity check codes using the mapping onto spin glasses proposed by Sourlas. We study codes where each parity check comprises products of K bits selected from the original digital message with exactly C parity checks per message bit. We show, using the replica method, that these codes saturate Shannon's coding bound for K?8 when the code rate K/C is finite. We then examine the finite temperature case to asses the use of simulated annealing methods for decoding, study the performance of the finite K case and extend the analysis to accommodate different types of noisy channels. The analogy between statistical physics methods and decoding by belief propagation is also discussed.

Some algorithms for discrete time queues with finite capacity

We consider a discrete time queue with finite capacity and i.i.d. and Markov modulated arrivals, Efficient algorithms are developed to calculate the moments and the distributions of the first time to overflow and the regeneration length, Results are extended to the multiserver queue. Some illustrative numerical examples are provided.

Representations and algorithms for finite-state bisimulations of linear discrete-time control systems

While a large amount of research over the past two decades has focused on discrete abstractions of infinite-state dynamical systems, many structural and algorithmic details of these abstractions remain unknown. To clarify the computational resources needed to perform discrete abstractions, this paper examines the algorithmic properties of an existing method for deriving finite-state systems that are bisimilar to linear discrete-time control systems. We explicitly find the structure of the finite-state system, show that it can be enormous compared to the original linear system, and give conditions to guarantee that the finite-state system is reasonably sized and efficiently computable. Though constructing the finite-state system is generally impractical, we see that special cases could be amenable to satisfiability based verification techniques. ©2009 IEEE.