Strong ergodicity of monotone transition functions

By revealing close links among strong ergodicity, monotone, and the Feller–Reuter–Riley (FRR) transition functions, we prove that a monotone ergodic transition function is strongly ergodic if and only if it is not FRR. An easy to check criterion for a Feller minimal monotone chain to be strongly ergodic is then obtained. We further prove that a non-minimal ergodic monotone chain is always strongly ergodic. The applications of our results are illustrated using birth-and-death processes and branching processes.

Ergodicity and stability of generalised Markov branching processes with resurrection

This paper concentrates on investigating ergodicity and stability for generalised Markov branching processes with resurrection. Easy checking criteria including several clear-cut corollaries are established for ordinary and strong ergodicity of such processes. The equilibrium distribution is given in an elegant closed form for the ergodic case. The probabilistic interpretation of the results is clear and thus explained.

Preemptive scheduling on uniform parallel machines with controllable job processing times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.