Stochastic Models for the Amount of Overflow in a Finite Dam with Random Inputs,Random Outputs,and Exponential Release Policy

In this article, we discuss finite dam models to study the expected amount of overflow in a given time. The inputs into the dam are taken as random and there are two types of outputs—one is random and the other is deterministic which is proportional to the content of the dam. The master equation for the expected amount of overflow is an one dimensional equation with separable kernel. For this class of master equation, the integral equation for the expected amount of overflow has been transformed exactly into ordinary differential equation with variable coefficients. The imbedding method is used to study the expected amount of overflow in a given time without emptiness in this period. We also consider the model for the expected amount of overflow in a given time with any number of emptiness of the dam in this period. The results are derived in the form of a third order differential Equation for the Laplace transformation function for the expected overflow. The closed form analytical solutions are obtained in terms of beta functions and degenerate hyper-geometric functions of two variables.     

Random walks on colored graphs

We initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly-exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time-inhomogeneous Markov chains. © 1994 John Wiley & Sons, Inc.     

On cumulative jump random variables

Stochastic models for phenomena that can exhibit sudden changes involve the use of processes whose sample functions may have discontinuities. This paper provides some tools for working with such processes. We develop a sample path formula for the cumulative jump height over a given time interval. From this formula an expression for the expected value of the cumulative jump random variable is developed under reasonable conditions. The results are applied to finding the expected number of failures in the separate maintenance model over a stated time interval and to the expected number of occurrences of a regenerative event over a stated time interval.     

Random walks and the regeneration time

Consider a graph G and a random walk on it. We want to stop the random walk at certain times (using an optimal stopping rule) to obtain independent samples from a given distribution ρ on the nodes. For an undirected graph, the expected time between consecutive samples is maximized by a distribution equally divided between two nodes, and so the worst expected time is 1/4 of the maximum commute time between two nodes. In the directed case, the expected time for this distribution is within a factor of 2 of the maximum. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 57–62, 1998     

The discrete time Geom/Geom/1 queue with multiple working vacations

In this paper, we study a discrete time Geom/Geom/1 queue with multiple working vacations. Using the quasi birth and death chain and matrix-geometric solution method, we give distributions for the number of customers in system and the waiting time of a customer and their stochastic decomposition structures, and obtain distributions of the additional number of customers and additional delay. Furthermore, we derive the formulae of expected regular busy period and expected busy cycle. Finally, by numerical examples, we analyze the effect of the parameters on the expected queue length and sojourn time.     

计划评审技术的改进

由于计划评审技术存在的不足,导致项目管理存在一定的偏差.对计划评审技术中的活动期望时间和方差的公式做了改进,从而提高了项目管理的精确性.还指出计划评审技术中活动期望时间和方差的计算公式,实际上是改进后公式的特殊情形.     

Approximation results in parallel machnies stochastic scheduling

We consider scheduling a batch of jobs with stochastic processing times on parallel machines. We derive various new formulae for the expected flowtime and weighted flowtime under general scheduling rules. Smith's Rule, which orders job starts by decreasing ratio of weight to expected processing time provides a natural heuristic for this problem. We obtain a bound on the worst case difference between the expected weighted flow time under Smith's Rule and under an optimal policy. For a wide class of processing time distributions, this bound is of oderO(1) and does not increase with the number of jobs.This research was supported in part by NSF Grant ECS-8712798.     

The impact of process deterioration on production and maintenance policies

This paper examines a single-stage production system that deteriorates with production actions, and improves with maintenance. The condition of the process can be in any of several discrete states, and transitions from state to state follow a semi-Markov process. The firm can produce multiple products, which differ by profit earned, expected processing time, and impact on equipment deterioration. The firm can also perform different maintenance actions, which differ by cost incurred, expected down time, and impact on the process condition. The firm needs to determine the optimal production and maintenance choices in each state in a way that maximizes the long-run expected average reward per unit time.     

关于反失效率序,DRHR和IEIT寿命分布类的几个结论

在这篇论文中,首先提出了一个基于期望休止时间序的反失效率序的等价刻画,并且利用膨胀序给出了递增期望休止时间分布类的一个新的刻画.然后,研究了当元件属于某个寿命分布类时所揭示的k-out-t-n系统的休止时间的变化情况,以及同一K-out-t-n系统不同的休止时间变化情况.类似的,考虑了在k-out-t-n系统中最先失效元件的休止时间的情况.     

Parallel Speed-Up of Monte Carlo Methods for Global Optimization

We introduce the notion of expected hitting time to a goal as a measure of the convergence rate of a Monte Carlo optimization method. The techniques developed apply to simulated annealing, genetic algorithms, and other stochastic search schemes. The expected hitting time can itself be calculated from the more fundamental complementary hitting time distribution (CHTD) which completely characterizes a Monte Carlo method. The CHTD is asymptotically a geometric series, (1/s)/(1 − λ), characterized by two parameters, s, λ, related to the search process in a simple way. The main utility of the CHTD is in comparing Monte Carlo algorithms. In particular we show that independent, identical Monte Carlo algorithms run in parallel, IIP parallelism, and exhibit superlinear speedup. We give conditions under which this occurs and note that equally likely search is linearly sped up. Further we observe that a serial Monte Carlo search can have an infinite expected hitting time, but the same algorithm when parallelized can have a finite expected hitting time. One consequence of the observed superlinear speedup is an improved uniprocessor algorithm by the technique of in-code parallelism.     

On the analysis of a dynamic evolutionary algorithm

Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the (1+1) EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static (1+1) EAs with a fixed mutation probability are compared with dynamic (1+1) EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1) EA. More precisely, functions are presented where each static (1+1) EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic (1+1) EA has exponential expected run time while a static (1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.     

Flexible supply contracts under price uncertainty

This article develops supply contracts covering environments with changing prices. We investigate characterization properties of the price processes, while considering costs and discount factors. We determine expressions of the contract’s expected low price and its second moment for a given horizon. We then employ these expected price and second moment values to identify an expected optimum time before the contract expires at which the lowest price occurs. Simulation experiments verify our analysis, and they illustrate how the optimum purchase time decreases as the drift term increases.     

带随机收入离散时间风险模型的常数壁分红效用问题

考虑一类带随机收入的离散时间风险模型.通过常数分红边界的引入,考虑分红总量的期望折现以及该分红总量的期望效用.     

Mean reversal for stochastic hybrid systems

Consider two discrete time Markov chains on a finite state space with ±1 win or lose payoff subject to transition between the states. We introduce a class of processes whose cumulative expected payoffs are decreasing in time but, whenever the processes are chosen at random by flipping a fair coin, the expected payoff for the randomized process becomes increasing in time. The seemingly counterintuitive long time run mean reversal generalizes the idea of combining two losing games into a winning one, known as Parrondo’s Paradox.     

Stochastic analysis of a n-unit repairable system with slow switch

This paper deals with the costn–benefit analysis of a cold standby system composed of n identical repairable units, subject to slow switch. Two models of system functioning are studied in this paper. In model 1, the repair time of a unit is assumed to follow exponential distribution and the other time distributions as arbitrary, while in model 2, the repair time of a unit is assumed to be arbitrarily distributed and the other time distributions follow exponential law. For both the models, the system characteristics, namely

(i) the expected upn–time of the system during the period (O,t]

(ii) the expected busyn–period of the repair facility during the period (0,t] and

(iii) the expected time the units spend in the switchover/installation state during the period (O,t]

are studied by identifying the system a t suitable regeneration epochs. The cost-benefit analysis is carried out using these characteristics     

Optimal inspection policy for three-state systems monitored by control charts

This paper presents the formulations of the expected long-run cost per time unit for a system monitored by a static control chart and by an adaptive control chart respectively. The static chart has a fixed sampling interval and a fixed sample size. The adaptive chart has a fixed sample size but variable sampling intervals. The system is supposed to have three states, normal working state, failure delay time state, and failed state. Two levels of repair are used to maintain the system. A minor repair is used to restore the system if a detectable defect is confirmed by an inspection. A major repair will be performed if the system fails. The expected cost per time unit for maintaining such a system is obtained. The objective of such analysis is to find an optimal sampling policy for the inspection process. An artificially generated data example and a real data example are used to compare the expected cost per time unit for both the static and adaptive control charts.     

Some Expressions of a Generalized Version of the Expected Time in the Red and the Expected Area in Red

Methodology and Computing in Applied Probability - In this paper, we study a generalized version of the expected time in the red and the expected area in red introduced in Loisel (2005). We derive...     

Coupling and mixing times in a Markov chain

The derivation of the expected time to coupling in a Markov chain and its relation to the expected time to mixing (as introduced by the author [J.J. Hunter, Mixing times with applications to perturbed Markov chains, Linear Algebra Appl. 417 (2006) 108-123] are explored. The two-state cases and three-state cases are examined in detail.     

Online stochastic UAV mission planning with time windows and time-sensitive targets

In this paper we simultaneously consider three extensions to the standard Orienteering Problem (OP) to model characteristics that are of practical relevance in planning reconnaissance missions of Unmanned Aerial Vehicles (UAVs). First, travel and recording times are uncertain. Secondly, the information about each target can only be obtained within a predefined time window. Due to the travel and recording time uncertainty, it is also uncertain whether a target can be reached before the end of its time window. Finally, we consider the appearance of new targets during the flight, so-called time-sensitive targets, which need to be visited immediately if possible. We tackle this online stochastic UAV mission planning problem with time windows and time-sensitive targets using a re-planning approach. To this end, we introduce the Maximum Coverage Stochastic Orienteering Problem with Time Windows (MCS-OPTW). It aims at constructing a tour with maximum expected profit of targets that were already known before the flight. Secondly, it directs the planned tour to predefined areas where time-sensitive targets are expected to appear. We have developed a fast heuristic that can be used to re-plan the tour, each time before leaving a target. In our computational experiments we illustrate the benefits of the MCS-OPTW planning approach with respect to balancing the two objectives: the expected profits of foreseen targets, and expected percentage of time-sensitive targets reached on time. We compare it to a deterministic planning approach and show how it deals with uncertainty in travel and recording times and the appearance of time-sensitive targets.