Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

Conditional hitting time estimation in a nonlinear filtering model by the Brownian bridge method

We consider a model composed of a signal process X given by a classic stochastic differential equation and an observation process Y, which is supposed to be correlated to the signal process. We assume that process Y is observed from time 0 to s>0 at discrete times and aim to estimate, conditionally on these observations, the probability that the non-observed process X crosses a fixed barrier after a given time t>0. We formulate this problem as a usual nonlinear filtering problem and use optimal quantization and Monte Carlo simulations techniques to estimate the involved quantities.     

A PTAS for the sparsest 2-spanner of 4-connected planar triangulations

A t-spanner of an undirected, unweighted graph G is a spanning subgraph of G with the added property that for every pair of vertices in G, the distance between them in is at most t times the distance between them in G. We are interested in finding a sparsest t-spanner, i.e., a t-spanner with the minimum number of edges. In the general setting, this problem is known to be NP-hard for all t2. For t5, the problem remains NP-hard for planar graphs, whereas for t{2,3,4}, the complexity of this problem on planar graphs is still unknown. In this paper we present a polynomial time approximation scheme for the problem of finding a sparsest 2-spanner of a 4-connected planar triangulation.     

Tail Behaviour of the Area Under the Queue Length Process of the Single Server Queue with Regularly Varying Service Times

This paper considers a stable GI∨GI∨1 queue with a regularly varying service time distribution. We derive the tail behaviour of the integral of the queue length process Q(t) over one busy period. We show that the occurrence of a large integral is related to the occurrence of a large maximum of the queueing process over the busy period and we exploit asymptotic results for this variable. We also prove a central limit theorem for ∫₀^t Q(s) ds.AMS subject classification: 60K25, 90B22.     

A randomized first-passage problem for drifted Brownian motion subject to hold and jump from a boundary

We study an inverse first-passage-time problem for Wiener process X(t) subject to hold and jump from a boundary c. Let be given a threshold S > X(0) ≥ c, and a distribution function F on [0, +∞). The problem consists in finding the distribution of the holding time at c and the distribution of jumps from c, so that the first-passage time of X(t) through S has distribution F.     

A sample path relation for the sojourn times in G/G/1−PS systems and its applications

For the single server system under processor sharing (PS) a sample path result for the sojourn times in a busy period is proved, which yields a sample path relation between the sojourn times under PS and FCFS discipline. This relation provides a corresponding one between the mean stationary sojourn times in G/G/1 under PS and FCFS. In particular, the mean stationary sojourn time in G/D/1 under PS is given in terms of the mean stationary sojourn time under FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of these results suggest an approximation of the mean stationary sojourn time in G/GI/1 under PS in terms of the mean stationary sojourn time under FCFS. Mathematics Subject Classification (MSC 2000) 60K25· 68M20· 60G17· 60G10 This work was supported by a grant from the Siemens AG.     

A direct approach to sojourn times in a busy period of an M/M/1 queue

In this paper we present a direct approach to obtaining joint distributions of various quantities of interest in a busy period in an M/M/1 queue. These quantities are: the sojourn times and waiting times of all the customers in the busy period, the busy period length and the number of customers served in a busy period. Since the evolution of the total workload process between two successive customer arrivals is deterministic, this work gives statistic of the complete evolution of the workload process within a busy period. This work was done when the author was post doctoral fellow with the MAESTRO group at INRIA, Sophia Antipolis, France, and was supported by project no. 2900-IT-1 from the Centre Franco-Indien pour la Promotion de la Recherche Avancee (CEFIPRA).     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Busy Period and the Waiting Time Analysis of a MAP/M/c Queue with Finite Retrial Group

Abstract

We concentrate on the analysis of the busy period and the waiting time distribution of a multi-server retrial queue in which primary arrivals occur according to a Markovian arrival process (MAP). Since the study of a model with an infinite retrial group seems intractable, we deal with a system having a finite buffer for the retrial group. The system is analyzed in steady state by deriving expressions for (a) the Laplace–Stieltjes transforms of the busy period and the waiting time; (b) the probabiliy generating functions for the number of customers served during a busy period and the number of retrials made by a customer; and (c) various moments of quantites of interest. Some illustrative numerical examples are discussed.     

Solving an Inverse First-Passage-Time Problem for Wiener Process Subject to Random Jumps from a Boundary

We study an inverse first-passage-time problem for Wiener process X(t) subject to random jumps from a boundary c. Let be given a threshold S > X(0); and a distribution function F on [0, + ∞). The problem consists of finding the distribution of the jumps which occur when X(t) hits c, so that the first-passage time of X(t) through S has distribution F.     

Order statistics applications to queueing and scheduling problems

We prove several basic combinatorial identities and use them in two applications: the queue inference engine (QIE) and earliest due date rule (EDD) scheduling. Larson (1990) introduced the QIE. His objective was to deduce the behavior of a multiserver queueing system without observing the queue. With only a Poisson arrival assumption, he analyzed the performance during a busy period. Such a period starts once all servers are busy with the queue empty, and it ends as soon as a server becomes idle. We generalize the standard order statistics result for Poisson processes, and show how to sample a busy period in the M/M/c system. We derive simple expressions for the variance of the total waiting time in the M/M/c and M/D/1 queues given that n Poisson arrivals and departures occur during a busy period. We also perform a probabilistic analysis of the EDD for a one-machine scheduling problem with earliness and tardiness penalties. The schedule is without preemption and with no inserted idle time. The jobs are independent and each may have a different due date. For large n, we show that the variance of the total penalty costs of the EDD is linear in n. The mean of the total penalty costs of the EDD is known to be proportional to the square root of n (see Harel (1993)). This revised version was published online in June 2006 with corrections to the Cover Date.     

Inactivity times of coherent systems with dependent components under periodical inspections

If we know that a coherent system has failed before a time t, the inactivity time is the period (from t) in which the system has been broken. If T is the system lifetime, the inactivity time at t is (t?T|T<t). Under periodical inspections, we may typically know that the system was working at a time t₁, but that is broken at another time t₂>t₁. Under this assumption, we obtain representations for the reliability function of the system inactivity time (t₂?T|t₁<T<t₂). We consider both the cases of independent and dependent components. Similar representations are obtained under other assumptions with partial information about component failures at times t₁ and t₂. These representations are used to compare stochastically the inactivity times under different assumptions. Some illustrative examples are provided.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1+<Emphasis Type="Italic">G</Emphasis> queue revisited

We consider an M/G/1 queue with the following form of customer impatience: an arriving customer balks or reneges when its virtual waiting time, i.e., the amount of work seen upon arrival, is larger than a certain random patience time. We consider the number of customers in the system, the maximum workload during a busy period, and the length of a busy period. We also briefly treat the analogous model in which any customer enters the system and leaves at the end of his patience time or at the end of his virtual sojourn time, whichever occurs first.     

Revisiting the model of servicing machines with repairable service facility-a new analyzing idea and some new results

In this paper the model of servicing machines with repairable facility is further studied.By standard conditioning decomposition argument,two reliability indices-the probability that the service facility fails at time t and the expected number of failure occurring during（0,t] are discussed.Some important relations of them are given.Furthermore,some new reliability problems are presented and discussed as follows：1） The numbers of the service facility failures during the generalized service time and the generalized busy period;2） The asymptotic expansion of the expected failure number of the service facility during（0,t].A series of new reliability results of the service facility are obtained.     

Continuity theorems for the M/M/1/n queueing system

In this paper continuity theorems are established for the number of losses during a busy period of the M/M/1/n queue. We consider an M/GI/1/n queueing system where the service time probability distribution, slightly different in a certain sense from the exponential distribution, is approximated by that exponential distribution. Continuity theorems are obtained in the form of one or two-sided stochastic inequalities. The paper shows how the bounds of these inequalities are changed if further assumptions, associated with specific properties of the service time distribution (precisely described in the paper), are made. Specifically, some parametric families of service time distributions are discussed, and the paper establishes uniform estimates (given for all possible values of the parameter) and local estimates (where the parameter is fixed and takes only the given value). The analysis of the paper is based on the level crossing approach and some characterization properties of the exponential distribution. Dedicated to Vladimir Mikhailovich Zolotarev, Victor Makarovich Kruglov, and to the memory of Vladimir Vyacheslavovich Kalashnikov.     

Feeble Fish in Time-Dependent Waters and Homogenization of the G-equation

We study the following control problem. A fish with bounded aquatic locomotion speed swims in fast waters. Can this fish, under reasonable assumptions, get to a desired destination? It can, even if the flow is time dependent. Moreover, given a prescribed sufficiently large time t , it can be there at exactly the time t . The major difference from our previous work is the time dependence of the flow. We also give an application to homogenization of the G-equation. © 2019 Wiley Periodicals, Inc.     

Total Completion Time in a Two-machine Flowshop with Deteriorating Tasks

This paper deals with two-machine flowshop problems with deteriorating tasks, i.e. tasks whose processing times are a nondecreasing function that depend on the length of the waiting periods. We consider the so-called Restricted Problem. This problem can be defined as follows: for a given permutation of tasks, find an optimal placement on two machines so that the total completion time is minimized. We will show that the Restricted Problem is nontrivial. We give some properties for the optimal placement and we propose an optimal placement algorithm.      

<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1/∞ batch arrival queueing system with a single exponential vacation

In the article the queueing system of GI/G/1 type with batch arrival of customers and a single exponentially distributed vacation period at the end of every busy period is considered. Basic characteristics of transient state of the system are investigated: the first busy period, the first vacation period and the number of customers served during the first busy period. New results for the Laplace transform of the joint distribution of these three variables are obtained in dependence on the initial conditions of the system. This material is based upon work supported by the Polish Ministry of Scientific Research and Information Technology under Grant No. 3 T11C 014 26.     

Some new results on waiting time and busy time in M/G/1 queue

This paper considers an M/G/1 queue with Poisson rate λ > 0 and service time distribution G(t) which is supposed to have finite mean 1/μ. The following questions are first studied: (a) The closed bounds of the probability that waiting time is more than a fixed value; (b)The total busy time of the server, which including the distribution, probability that are more than a fixed value during a given time interval (0, t], and the expected value. Some new and important results are obtained by theories of the classes of life distributions and renewal process.     

Hyperbolic heat conduction in two semi-infinite bodies in contact

We find, under the viewpoint of the hyperbolic model of heat conduction, the exact analytical solution for the temperature distribution in all points of two semi-infinite homogeneous isotropic bodies that initially are at uniform temperatures T ₀ ¹ and T ₀ ² , respectively, suddenly placed together at time t = 0 and assuming that the contact between the bodies is perfect. We make graphics of the obtained temperature profiles of two bodies at different times and points. And finally, we compare the temperature solution obtained from hyperbolic model to the parabolic or classical solution, for the same problem of heat conduction.This work was partially supported by MEC and FEDER, project MTM-2004-02262 and AVCIT group 03/050.This revised version was published online in April 2005 with a corrected issue number.