Queues with service times and interarrival times depending linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queue with unlimited waiting space and the first-in first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY _n+1=C _n Y _n +X _n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.     

Stopping times

Generalizations of known statements on the stopping times most frequently used in probability theory and its applications are proved.     

Brownian local times

The purpose of this paper is to present in a more or less self-contained way the chief facts about the local times t of one-dimensional Brownian motion due to P. Lévy, F. Knight, D. B. Ray, and Itô-McKean. The deepest part concerns the remarkable fact that for a class of stopping times m, such as passage times and independent exponential holding times, the local time t(m, x) is a diffusion relative to its spatial parameter x. The beautiful methods of D. Williams are employed here as being most in the manner of P. Lévy who began the whole thing. The intent is purely expository, and only the main features of the proofs are indicated. A familiarity with the most elementary facts about Brownian motion is assumed. The paper is dedicated to Norman Levinson with affection and respect.     

Birth times,death times and time substitutions in Markov chains

Summary Given a Markov chain (X _n ) _n0, random times are studied which are birth times or death times in the sense that the post- and pre- processes are independent given the present (X _–1, X ) at time and the conditional post- process (birth times) or the conditional pre- process (death times) is again Markovian. The main result for birth times characterizes all time substitutions through homogeneous random sets with the property that all points in the set are birth times. The main result for death times is the dual of this and appears as the birth time theorem with the direction of time reversed.Part of this work was done while the author was visiting the Department of Mathematics, University of California at San DiegoThe support of The Danish Natural Science Research Council is gratefully acknowledged     

On queues with service and interarrival times depending on waiting times

We consider an extension of the standard G/G/1 queue, described by the equation $W\stackrel{ \mathcal {D}}{=}\max\mathrm{max}\,\{0,B-A+YW\}$ , where ?[Y=1]=p and ?[Y=?1]=1?p. For p=1 this model reduces to the classical Lindley equation for the waiting time in the G/G/1 queue, whereas for p=0 it describes the waiting time of the server in an alternating service model. For all other values of p, this model describes a FCFS queue in which the service times and interarrival times depend linearly and randomly on the waiting times. We derive the distribution of W when A is generally distributed and B follows a phase-type distribution, and when A is exponentially distributed and B deterministic.     

Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.     

Self-intersection local times and collision local times of bifractional Brownian motions

In this paper, we consider the local time and the self-intersection local time for a bifractional Brownian motion, and the collision local time for two independent bifractional Brownian motions. We mainly prove the existence and smoothness of the self-intersection local time and the collision local time, through the strong local nondeterminism of bifractional Brownian motion, L2 convergence and Chaos expansion.     

On the characterisation of honest times that avoid all stopping times

We present a short and self-contained proof of the following result: a random time is an honest time that avoids all stopping times if and only if it coincides with the (last) time of maximum of a nonnegative local martingale with zero terminal value and no jumps while at its running supremum, where the latter running supremum process is continuous. Illustrative examples involving local martingales with discontinuous paths are provided.     

Single machine scheduling with resource dependent release times and processing times

We consider the single machine scheduling problem with resource dependent release times and processing times, in which both the release times and processing times are strictly linear decreasing functions of the amount of resources consumed. The objective is to minimize the makespan plus the total resource consumption costs. We propose a heuristic algorithm for the general problem by utilizing some derived optimal properties and analyze its performance bound. For some special cases, we propose another heuristic algorithm that achieves a tighter performance bound.     

On Whitt's conjecture for queues in which service times and interarrival times depend linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queueing system with infinite waiting space and the first-in-first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. When the waiting-time distributions converge to a proper limit, Whitt [10] proposed a normal approximation for this steady-state limit. In this paper we prove a limit theorem for the steady-state limit of the system. Thus, our result provides a solid foundation for Whitt's normal approximation of the steady-state distribution of the system.Supported in part by a grant from the National Natural Science Foundation of China.     

Smoothness of local times and self-intersection local times of Gaussian random fields

This paper is concerned with the smoothness (in the sense of Meyer- Watanabe) of the local times of Gaussian random fields. Sufficient and necessary conditions for the existence and smoothness of the local times, collision local times, and self-intersection local times are established for a large class of Gaussian random fields, including fractional Brownian motions, fractional Brownian sheets and solutions of stochastic heat equations driven by space-time Gaussian noise.     

On efficient stopping times

This paper is devoted to efficient sequential estimation in stochastic processes whose corresponding sufficient statistics are processes with stationary independent increments. It is proved that a stopping time is efficient if and only if it represents a time of the first attaining of a hyperplane., which cannot ‘be passed’, in the sense which is made precise below. The problem of determining the explicit form of the hyperplanes which cannot ‘be passed’ is also discussed.     

On exactlym times covers

In this paper it is shown that if every integer is covered bya ₁+n ₁ℤ,…,a _k +n _k ℤ exactlym times then for eachn=1,…,m there exist at least ( _n ^m ) subsetsI of {1,…k} such that ∑ _{i ∈ I} 1/n _i equalsn. The bound ( _n ^m ) is best possible. Research supported by the National Nature Science Foundation of P.R. of China.     

Hard times and statistics

Hard times is a satire against mid-Victorian statisticians, those whom Dickens called ‘the representatives of the wickedest and most enormous vice of this time’. Historians of mathematics have seen the novel as a cruel parody of statistical determinism, a fatalistic movement which swept the continent in the 1860s and 1870s. But to see it as such is to credit Dickens with a better understanding of contemporary mathematics than he in fact possessed. The statistics in Hard times are not the probabilistic theories of continental academics. They are the mundane facts and figures of the much more prosaic English statistical movement.