Performance measures of a multi-layer Markovian fluid model

Our goal is to model the behaviour of the fluid in a buffer with threshold controls with a wide range of behaviour possible at the boundaries. To model this, we consider a class of Markovian fluid flow models with several layers, each with their own parameters, separated by boundaries. The behaviour of the fluid at each boundary is modelled by parameters unique to that boundary. We derive the Laplace-Stieltjes transforms of time-related performance measures of this model. This is illustrated with numerical examples. All results are obtained via techniques within the fluid flow environment, and useful physical interpretations are presented.     

The joint distribution of sojourn times for a customer traversing an overtake-free series of queues: The discrete time case

We investigate a cycle of Bernoulli servers in discrete time. We show that the joint distribution of a customer’s sojourn times at the nodes during a round trip is of product form and can explicitly be written down. The results are used to prove independence of sojourn times in an open series of Bernoulli servers. This revised version was published online in June 2006 with corrections to the Cover Date.     

Relating polling models with zero and nonzero switchover times

We consider a system ofN queues served by a single server in cyclic order. Each queue has its own distinct Poisson arrival stream and its own distinct general service-time distribution (asymmetric queues), and each queue has its own distinct distribution of switchover time (the time required for the server to travel from that queue to the next). We consider two versions of this classical polling model: In the first, which we refer to as the zero-switchover-times model, it is assumed that all switchover times are zero and the server stops traveling whenever the system becomes empty. In the second, which we refer to as the nonzero-switchover-times model, it is assumed that the sum of all switchover times in a cycle is nonzero and the server does not stop traveling when the system is empty. After providing a new analysis for the zero-switchover-times model, we obtain, for a host of service disciplines, transform results that completely characterize the relationship between the waiting times in these two, operationally-different, polling models. These results can be used to derive simple relations that express (all) waiting-time moments in the nonzero-switchover-times model in terms of those in the zero-switchover-times model. Our results, therefore, generalize corresponding results for the expected waiting times obtained recently by Fuhrmann [Queueing Systems 11 (1992) 109—120] and Cooper, Niu, and Srinivasan [to appear in Oper. Res.].Research supported in part by the National Science Foundation under grant DDM-9001751.     

Renewal analysis of a replacement process

We consider a unit with a random lifetime which is replaced at renewal times by a new identical one regardless of whether it has failed before or not. For this random periodic replacement policy, we derive exact formulas for the cycle length, defined as the time between the replacements of two successive failed units, the stationary probability of the current unit to have failed, and the stationary and the transient distributions of the residual lifetime of the current unit.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

Hitting and returning to rare events for all alpha-mixing processes

We prove that for any α-mixing stationary process the hitting time of any n-string A_n converges, when suitably normalized, to an exponential law. We identify the normalization constant λ(A_n). A similar statement holds also for the return time.To establish this result we prove two other results of independent interest. First, we show a relation between the rescaled hitting time and the rescaled return time, generalizing a theorem of Haydn, Lacroix and Vaienti. Second, we show that for positive entropy systems, the probability of observing any n-string in n consecutive observations goes to zero as n goes to infinity.     

Nonlinear oscillations in business cycle model with time lags

In this paper we analyse the dynamics of the Kaldor–Kalecki business cycle model. This model is based on the classical Kaldor model in which capital stock changes are caused by past investment decisions. This lag is connected with time delay needed for new capital to be installed. The dynamics of the model is reduced to the form of damped oscillator with negative feedback connected with lag parameter and next it is analysed in terms of bifurcation theory. We find conditions for existence and persistence of oscillatory behaviour which is represented by limit cycle on some central manifold in phase space, i.e., single Hopf bifurcation. We demonstrate that the Hopf cycles may be exhibited for nonzero measure set of the parameter space. The conditions for bifurcation of co-dimension two connected with interaction of bifurcations as well as bifurcation diagrams are also given. Finally, we obtain numerical values describing an amplitude and a period of oscillation for different parameter of the system. It is also proved that while the investment function is not nonlinear a quasi-periodic solution (a 1:2 resonant double Hopf point) can appear. The source of such a behaviour is rather a consequence of time lag than nonlinearity of the investment function. Our results confirm the existence of asymmetric (two periodic) cycles in the Kaldor–Kalecki model with time-to-build.     

Optimal preventive maintenance for equipment with two quality states and general failure time distributions

We present an economic model for the optimization of preventive maintenance in a production process with two quality states. The equipment starts its operation in the in-control state but it may shift to the out-of-control state before failure or scheduled preventive maintenance. The time of shift and the time of failure are generally distributed random variables. The two states are characterized by different failure rates and revenues. We first derive the structure of the optimal maintenance policy, which is defined by two critical values of the equipment age that determine when to perform preventive maintenance depending on the actual (observable) state of the process. We then provide properties of the optimal solution and show how to determine the optimal values of the two critical maintenance times accurately and efficiently. The proposed model and, in particular, the behavior of the optimal solution as the model parameters and the shift and failure time distributions change are illustrated through numerical examples.     

On conditions for regularity of solutions for a piecewise linear system

We study a piecewise linear system approximating the behaviour of a switched DC/DC converter. We give conditions for a unique limit cycle in our different cases and give examples of complicated phenomena that might occur. The stability of a state space trajectory controlled converter is addressed.     

Asymptotics of stochastic networks with subexponential service times

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i ₀ ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i ₀ asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i ₀. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered. This revised version was published online in June 2006 with corrections to the Cover Date.     

On conditions for regularity of solutions for a piecewise linear system

We study a piecewise linear system approximating the behaviour of a switched DC/DC converter. We give conditions for a unique limit cycle in our different cases and give examples of complicated phenomena that might occur. The stability of a state space trajectory controlled converter is addressed.     

Fibers of Polynomial Mappings at Infinity and a Generalized Malgrange Condition

Let f be a complex polynomial mapping. We relate the behaviour of f at infinity to the characteristic cycle associated to the projective closures of fibres of f. We obtain a condition on the characteristic cycle which is equivalent to a condition on the asymptotic behaviour of some of the minors of the Jacobian matrix of f. This condition generalizes the condition in the hypersurface case known as Malgrange's condition. The relation between this condition and the behavior of the characteristic cycle is a partial generalization of Parusinski's result in the hypersurface case. We show that the new condition implies the C-triviality of f.     

On an asymptotic evaluation of the cycle index of the symmetric group

We give a short derivation of an extension of a result of Schwenk on the limiting behaviour of the cycle index of the symmetric group when it is evaluated for a given power series at a given point.     

The discrete-time single-server queue

In this paper we consider the discrete-time single server queueing model with exceptional first service. For this model we cannot define the steady-state waiting-time distribution simply as the limiting distribution of the waiting times, since this limit does not always exist. Instead, we use the Cesaro limit to define the limiting waiting-time distribution. We give an exact relation between the generating functions of the steady-state waiting-time distribution and of the idle-time distribution in the case of general interarrival-time and service-time distributions. Once we have this relation, we can give more explicit results when the generating function of either the interarrival-time distribution or the service-time distribution is rational. We also derive some results on the asymptotic behaviour of the waiting-time distribution.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

Brown运动的逗留时与首中时

设为中的标准Brown运动,对0＜α,记本文求出了X在首中球面之前逗留在Bα内的时间的Laplace变换,在首中之前逗留在Bαb内的时间的Laplace变换以及在首中之前逗留在Bαb内的时间的Laplace变换．作为推论,求出了X关于球面首中时的Laplace变换,逗留在球内总的时间的Laplace变换及逗留在球壳内的总的时间的LaPlace变换．     

Prediction of Continuous Time Processes by C[0,1]‐Valued Autoregressive Process

In order to predict a continuous time process on an entire‐time interval, we introduce the C_[0,1]‐valued autoregressive process of first order. We show, under mild regularity conditions the convergence almost sure of the predictor. We propose an estimator of the dimension of the projecting space of observations and illustrate the results by a numerical example. This revised version was published online in June 2006 with corrections to the Cover Date.     

Branch and bound procedures for solving the Assembly Line Worker Assignment and Balancing Problem: Application to Sheltered Work centres for Disabled

In this paper a new problem called Assembly Line Worker Assignment and Balancing Problem (ALWABP) is introduced. This problem arises in those assembly lines where we have certain limited resources available (normally workers) in which the operation time for every task is different depending on who executes the task, and where there are also some task-worker incompatibilities defined. The problem consists of providing a simultaneous solution to a double assignment: (1) tasks to stations; and (2) available workers to stations.After defining the mathematical model for this problem, a basic Branch and Bound approach with three possible search strategies and different parameters is presented. We also propose the use of a Branch and Bound-based heuristic for large problems and analyse the behaviour of both exact and heuristic methods through experimental studies. Finally the implementation of these procedures in a Sheltered Work centre for Disabled—the real environment which has inspired this research—is described. In these centres the adoption of assembly lines provide many advantages, since the traditional division of work in single tasks may become a perfect tool for making certain worker disabilities invisible. Efficiently applying this configuration helps these centres to achieve their primary aim: growth in order to provide more jobs for more disabled people, but always considering the specific limitations that the disabled workers have. In this sense this paper shows one of the possible real applications where Operations Research can help not only to get economic and productive benefits but also certain social aims.     

Some minimal bimolecular mass-action systems with limit cycles

We discuss three examples of bimolecular mass-action systems with three species, due to Feinberg, Berner, Heinrich, and Wilhelm. Each system has a unique positive equilibrium which is unstable for certain rate constants and then exhibits stable limit cycles, but no chaotic behaviour. For some rate constants in the Feinberg–Berner system, a stable equilibrium, an unstabe limit cycle, and a stable limit cycle coexist. All three networks are minimal in some sense.By way of homogenising these three examples, we construct bimolecular mass-conserving mass-action systems with four species that admit a stable limit cycle. The homogenised Feinberg–Berner system and the homogenised Wilhelm–Heinrich system admit the coexistence of a stable equilibrium, an unstable limit cycle, and a stable limit cycle.     

A Geometric Space-Time Multigrid Algorithm for the Heat Equation

We study the time-dependent heat equation on its space-time domain that is discretised by a $k$-spacetree. $k$-spacetrees are a generalisation of the octree concept and are a discretisation paradigm yielding a multiscale representation of dynamically adaptive Cartesian grids with low memory footprint. The paper presents a full approximation storage geometric multigrid implementation for this setting that combines the smoothing properties of multigrid for the equation's elliptic operator with a multiscale solution propagation in time. While the runtime and memory overhead for tackling the all-in-one space-time problem is bounded, the holistic approach promises to exhibit a better parallel scalability than classical time stepping, adaptive dynamic refinement in space and time fall naturally into place, as well as the treatment of periodic boundary conditions of steady cycle systems, on-time computational steering is eased as the algorithm delivers guesses for the solution's long-term behaviour immediately, and, finally, backward problems arising from the adjoint equation benefit from the the solution being available for any point in space and time.