Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

Data and queueing analysis of a Japanese air-traffic flow

Congestion is a major cause of inefficiency in air transportation. A question is whether delays during the arrival phase of a flight can be absorbed more fuel-efficiently in the future. In this context, we analyze Japan’s flow strategy empirically and use queueing techniques in order to gain insight into the generation of the observed delays. Based on this, we derive a rule to balance congestion delays more efficiently between ground and en-route. Whether fuel efficiency can be further improved or not will depend on the willingness to review the concept of runway pressure.     

The impact of stochastic lead time reduction on inventory cost under order crossover

We use exponential lead times to demonstrate that reducing mean lead time has a secondary reduction of the variance due to order crossover. The net effect is that of reducing the inventory cost, and if the reduction in inventory cost overrides the investment in lead time reduction, then the lead time reduction strategy would be tenable.We define lead time reduction as the process of decreasing lead time at an increased cost. To date, decreasing lead times has been confined to deterministic instances. We examine the case where lead times are exponential, for when lead times are stochastic, deliveries are subject to order crossover, so that we must consider effective lead times rather than the actual lead times. The result is that the variance of these lead times is less than the variance of the original replenishment lead times.Here we present a two-stage procedure for reducing the mean and variance for exponentially distributed lead times. We assume that the lead time is made of one or several components and is the time between when the need of a replenishment order is determined to the time of receipt.     

Modeling sequence scrambling and related phenomena in mixed-model production lines

In this paper we examine the various effects that workstations and rework loops with identical parallel processors and stochastic processing times have on the performance of a mixed-model production line. Of particular interest are issues related to sequence scrambling. In many production systems (especially those operating on just-in-time or in-line vehicle sequencing principles), the sequence of orders is selected carefully to optimize line efficiency while taking into account various line balancing and product spacing constraints. However, this sequence is often altered due to stochastic factors during production. This leads to significant economic consequences, due to either the degraded performance of the production line, or the added cost of restoring the sequence (via the use of systems such as mix banks or automated storage and retrieval systems). We develop analytical formulas to quantify both the extent of sequence scrambling caused by a station of the production line, and the effects of this scrambling on downstream performance. We also develop a detailed Markov chain model to analyze related issues regarding line stoppages and throughput. We demonstrate the usefulness of our methods on a range of illustrative numerical examples, and discuss the implications from a managerial point of view.     

Sensitivity of optimal prices to system parameters in a steady-state service facility

We consider the problem of maximizing the long-run average reward in a service facility with dynamic pricing. We investigate sensitivity of optimal pricing policies to the parameters of the service facility which is modelled as an M/M/s/K$M/M/s/K$ queueing system. Arrival process to the facility is Poisson with arrival rate a decreasing function of the price currently being charged by the facility. We prove structural results on the optimal pricing policies when the parameters in the facility change. Namely, we show that optimal prices decrease when the capacity of the facility or the number of servers in the facility increase. Under a reasonable assumption, we also show that optimal prices increase as the overall demand for the service provided by the facility increases or when the service rate of the facility decreases. We illustrate how these structural results simplify the required computational effort while finding the optimal policy.     

The selection efficiency of tournaments

We discuss tournaments in terms of their efficiency as probabilistic mechanisms that select high-quality alternatives (“players”) in a noisy environment. We characterize the selection efficiency of three such mechanisms – contests, binary elimination tournaments, and round-robin tournaments – depending on the shape of the distribution of players’ quality, the number of players, and noise level. The results have implications as to how, and under what circumstances, the efficiency of tournament-based selection can be manipulated.     

On Lp -Theory of stochastic partialdifferential equations of divergence form with continuous coefficients

We develop an L_p -theory of stochastic PDEs of divergence form. Under natural assumptions on the coefficients and the data, we show that the solutions belong to some modified stochastic Sobolev spaces. As a consequence of this result and certain embedding theorem, we also show that the solutions are Holder continuous in space and time a.s. for sufficiently large p     

Analysis of event-based, single-server nonstationary simulation responses using classical time-series models

In this article, we present a metamodeling methodology for analyzing event-based, single-server nonstationary simulation responses that is based on the use of classical ARIMA (or SARIMA) time-series models. Some analytical results are derived for a Markovian queue and are used to evaluate the proposed methodology. The use of the corresponding procedure is illustrated on a traffic example from the simulation literature. Some conclusions are drawn and recommendations for further work are stated.     

Computational results of an O(n) volume algorithm

Recently an O^∗(n⁴) volume algorithm has been presented for convex bodies by Lovász and Vempala, where n is the number of dimensions of the convex body. Essentially the algorithm is a series of Monte Carlo integrations. In this paper we describe a computer implementation of the volume algorithm, where we improved the computational aspects of the original algorithm by adding variance decreasing modifications: a stratified sampling strategy, double point integration and orthonormalised estimators. Formulas and methodology were developed so that the errors in each phase of the algorithm can be controlled. Some computational results for convex bodies in dimensions ranging from 2 to 10 are presented as well.     

The cross-entropy method in multi-objective optimisation: An assessment

Solving multi-objective problems requires the evaluation of two or more conflicting objective functions, which often demands a high amount of computational power. This demand increases rapidly when estimating values for objective functions of dynamic, stochastic problems, since a number of observations are needed for each evaluation set, of which there could be many. Computer simulation applications of real-world optimisations often suffer due to this phenomenon. Evolutionary algorithms are often applied to multi-objective problems. In this article, the cross-entropy method is proposed as an alternative, since it has been proven to converge quickly in the case of single-objective optimisation problems. We adapted the basic cross-entropy method for multi-objective optimisation and applied the proposed algorithm to known test problems. This was followed by an application to a dynamic, stochastic problem where a computer simulation model provides the objective function set. The results show that acceptable results can be obtained while doing relatively few evaluations.     

Measurement and optimization of robust stability of multiclass queueing networks: Applications in dynamic supply chains

Multiclass queueing networks are an essential tool for modeling and analyzing complex supply chains. Roughly speaking, stability of these networks implies that the total number of customers/jobs in the network remains bounded over time. In this context robustness characterizes the ability of a multiclass queueing network to remain stable, if the expected values of the interarrival and service times distributions are subject to uncertain shifts. A powerful starting point for the stability analysis of multiclass queueing networks is the associated fluid network. Based on the fluid network analysis we present a measure to quantify the robustness, which is indicated by a single number. This number will be called the stability radius. It represents the magnitude of the smallest shift of the expected value of the interarrival and/or service times distributions so that the associated fluid network looses the property of stability. The stability radius is a worst case measure and is a conceptual adaptation from the dynamical systems literature. Moreover, we provide a characterization of the shifts that destabilize the network. Based on these results, we formulate a mathematical program that minimizes the required network capacity, while ensuring a desired level of robustness towards shifts of the expected values of the interarrival times distributions. This approach provides a new view on long-term robust production capacity allocation in supply chains. The capabilities of our method are demonstrated using a real world supply chain.     

Stochastic comparisons of residual lifetimes and inactivity times of coherent systems with dependent identically distributed components

In this paper we compare the residual lifetime of a used coherent system of age t>0$t>0$ with the lifetime of the similar coherent system made up of used components of age t. Here ‘similar’ means that the system has the same structure and the component lifetimes have the same dependence (joint reliability copula). Some comparison results are obtained for the likelihood ratio order, failure rate order, reversed failure rate order and the usual stochastic order. Similar results are reported for comparing inactivity time of a coherent system with lifetime of similar coherent system having component lifetimes same as inactivity times of failed components.     

Single observation adaptive search for discrete and continuous stochastic optimization

Solving a stochastic optimization problem often involves performing repeated noisy function evaluations at points encountered during the algorithm. Recently, a continuous optimization framework for executing a single observation per search point was shown to exhibit a martingale property so that associated estimation errors are guaranteed to converge to zero. We generalize this martingale single observation approach to problems with mixed discrete–continuous variables. We establish mild regularity conditions for this class of algorithms to converge to a global optimum.     

Joint-optimization of inventory policies on a multi-product multi-echelon pharmaceutical system with batching and ordering constraints

This paper presents a methodology to find near-optimal joint inventory control policies for the real case of a one-warehouse, n-retailer distribution system of infusion solutions at a University Medical Center in France. We consider stochastic demand, batching and order-up-to level policies as well as aspects particular to the healthcare setting such as emergency deliveries, required service level rates and a new constraint on the ordering policy that fits best the hospital’s interests instead of abstract ordering costs. The system is modeled as a Markov chain with an objective to minimize the stock-on-hand value for the overall system. We provide the analytical structure of the model to show that the optimal reorder point of the policy at both echelons is easily derived from a simple probability calculation. We also show that the optimal policy at the care units is to set the order-up-to level one unit higher than the reorder point. We further demonstrate that optimizing the care units in isolation is optimal for the joint multi-echelon, n-retailer problem. A heuristic algorithm is presented to find the near-optimal order-up-to level of the policy of each product at the central pharmacy; all other policy parameters are guaranteed optimal via the structure provided by the model. Comparison of our methodology versus that currently in place at the hospital showed a reduction of approximately 45% in the stock-on-hand value while still respecting the service level requirements.     

The matched queueing system GIoPh/Ph/1

We study the matched queueing system GIoPH/PH/1, where the type-I input is a renewal process, the type-II input is a PH renewal process, and the service times are i.i.d. random variables with PH-distributions. First, a condition is given for the stationarity of the system. Then the distributions of the number of type-I customers at the arrival epoches of type-I customers and the number of type-I customers at an arbitrary epoch are derived. We also discuss the occupation time and the waiting time. Their L.S. transforms are derived. Finally, we discuss some problems in numerical computation.This research is supported by the National Natural Science Foundation of China and partially by the Institute of Mathematics, the Chinese Academy of Sciences.     

Stochastic Simulation and Monte Carlo methods applied to the assessment of hydro-thermal generating system operation

Summary Simulation can be defined as a numerical technique for conducting experiments on a digital computer, which involves certain types of mathematical and logical models that describe the behaviour of a system over extended periods of real time. Simulation is, in a wide sense, a technique for performing sampling experiments on a model of the system. Stochastic simulation implies experimenting with the model over time including sampling stochastic variates from probability distributions. This paper describes the main concepts of the application of Stochastic Simulation and Monte Carlo methods to the analysis of the operation of electric energy systems, in particular to hydro-thermal generating systems. These techniques can take into account virtually all contingencies inherent in the operation of the system. Also, the operating policies that have an important effect on the performance of these systems can be realistically represented.     

The coding complexity of diffusion processes under -norm distortion

We investigate the high resolution quantization and entropy coding problem for solutions of stochastic differential equations under L^p[0,1]-norm distortion. We find explicit high resolution formulas in terms of the average diffusion coefficient seen by the process. The proof is based on a decoupling method introduced in a former article by the author. Given that link it remains to analyze the coding problem for a concatenation of Wiener processes and to solve the corresponding rate allocation problem.     

Modeling and analysis of a Canadian Forces Geomatics division workflow

This paper addresses workflow issues of a Geomatics division in the Canadian Forces. This division is dedicated to the production of Geomatics Information under the US National Geospatial-Intelligence Agency’s Foundation Based Operations concept. This paper outlines a methodology for modeling and analyzing the workflow of the Canadian Forces Geomatics division. A discrete event simulation model is developed and applied to measure the performance of the workflow system for developing Geomatics products. A hybrid queueing network/optimization model is also developed to support the simulation model. The objective of the queueing network/optimization formulation is to provide the optimal configuration of the Geomatics division. The paper successfully addresses a complex workflow problem in the context of real world system and provides insights into the performance of the Canadian Forces Geomatics processing.