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.     

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.     

The impact of order batching and picking area zoning on order picking system performance

This paper proposes an approximation model based on queuing network theory to analyze the impact of order batching and picking area zoning on the mean order throughput time in a pick-and-pass order picking system. The model includes the sorting process needed to sort the batch again by order. Service times at pick zones are assumed to follow general distributions. The first and second moments of service times at zones and the visiting probability of a batch of orders to a pick zone are derived. Based on this information, the mean throughput time of an arbitrary order in the order picking system is obtained. Results from a real application and simulation show that this approximation model provides acceptable accuracy for practical purposes. Furthermore, the proposed method is simple and fast and can be easily applied in the design and selection process of order picking systems.     

Optimal static pricing for a service facility with holding costs

We study a service facility modelled as a single-server queueing system with Poisson arrivals and limited or unlimited buffer size. In systems with unlimited buffer size, the service times have general distributions, whereas in finite buffered systems service times are exponentially distributed. Arriving customers enter if there is room in the facility and if they are willing to pay the posted price. The same price is charged to all customers at all times (static pricing). The service provider is charged a holding cost proportional to the time that the customers spend in the system. We demonstrate that there is a unique optimal price that maximizes the long-run average profit per unit time. We also investigate how optimal prices vary as system parameters change. Finally, we consider buffer size as an additional decision variable and show that there is an optimal buffer size level that maximizes profit.     

Calculation of traffic flow breakdown probability to optimize link throughput

Traffic breakdown phenomenon is prevalent in empirical traffic system observations. Traffic flow breakdown is usually defined as an amount of sudden drop in traffic flow speed when traffic demand exceeds capacity. Modeling and calculating traffic flow breakdown probability remains an important issue when analyzing the stability and reliability of transportation system. The breakdown mechanism is still mysterious to practitioners and researchers in varying manner. Treating breakdown as a random event, this paper use discrete time Markov chain (DTMC) to model traffic state transition path, as a result, a transition probability matrix can be generated from empirical observations. From empirical analysis of breakdown, we found this formulation of breakdown probability follows the Zipf distribution. Therefore, a connection from traffic flow breakdown probability to how many vehicles are occupying a certain freeway segment (e.g. a link) will be established. Following from the results, a quantitative measure of breakdown probability can be obtained to optimize ramp metering rates to achieve optimum system performance measures.     

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.     

The BMAP/PH/N retrial queue with Markovian flow of breakdowns

We consider a multi-server retrial queue with the Batch Markovian Arrival Process (BMAP). The servers are identical and independent of each other. The service time distribution of a customer by a server is of the phase (PH) type. If a group of primary calls meets idle servers the primary calls occupy the corresponding number of servers. If the number of idle servers is insufficient the rest of calls go to the orbit of unlimited size and repeat their attempts to get service after exponential amount of time independently of each other. Busy servers are subject to breakdowns and repairs. The common flow of breakdowns is the MAP. An event of this flow causes a failure of any busy server with equal probability. When a server fails the repair period starts immediately. This period has PH type distribution and does not depend on the repair time of other broken-down servers and the service time of customers occupying the working servers. A customer whose service was interrupted goes to the orbit with some probability and leaves the system with the supplementary probability. We derive the ergodicity condition and calculate the stationary distribution and the main performance characteristics of the system. Illustrative numerical examples are presented.     

Staff optimization for time-dependent acute patient flow

The emergency department is a key element of acute patient flow, but due to high demand and an alternating rate of arriving patients, the department is often challenged by insufficient capacity. Proper allocation of resources to match demand is, therefore, a vital task for many emergency departments.Constrained by targets on patient waiting time, we consider the problem of minimizing the total amount of staff-resources allocated to an emergency department. We test a matheuristic approach to this problem, accounting for both patient flow and staff scheduling restrictions. Using a continuous-time Markov chain, patient flow is modeled as a time-dependent queueing network where inhomogeneous behavior is evaluated using the uniformization method. Based on this modeling approach, we recursively evaluate and allocate staff to the system using integer linear programming until the waiting time targets are respected in all queues of the network. By comparing to discrete-event simulations of the associated system, we show that this approach is adequate for both modeling and optimizing the patient flow. In addition, we demonstrate robustness to the service time distribution and the associated system with multiple classes of patients.     

On the Asymptotic Behavior of the Storage Process Fed by a Markov Modulated Brownian Motion

Consider a storage model fed by a Markov modulated Brownian motion. We prove that the stationary distribution of the model exits and that the running maximum of the storage process over the interval [0, t] grows asymptotically like log t as t→∞.     

Light traffic for workload in queues

General exact light traffic limit theorems are given for the distribution of steadystate workloadV, in open queueing networks having as input a general stationary ergodic marked point process {(t _n ,K _n )n0 (where t_n denotes the arrival time and K_n the routing and service times of the nth customer). No independence assumptions of any kind are required of the input. As the light traffic regime, it is only required that the Palm distribution for the exogenous interarrival time converges weakly to infinity (while the service mechanism is not allowed to change much). As is already known in the context of a single-server queue, work is much easier to deal with mathematically in light traffic than is customer delayD, and consequently, our results are far more general than existing results forD. We obtain analogous results for multi-channel and infinite-channel queues. In the context of open queueing networks, we handle both the total workload in the network as well as the workload at isolated nodes.Research supported in part by the Japan Society for the Promotion of Science during the author's fellowship in Tokyo, and by NSF Grant DDM 895 7825.     

Distribution sensitivity in a highway flow model

We examine a model of traffic flow on a highway segment, where traffic can be impaired by random incidents (usually, collisions). Using analytical and numerical methods, we show the degree of sensitivity that the model exhibits to the distributions of service times (in the queueing model) and incident clearance times. Its sensitivity to the distribution of time until an incident is much less pronounced. Our analytical methods include an M/G_t/∞ analysis (G_t denotes a service process whose distribution changes with time) and a fluid approximation for an M/M/c queue with general distributions for the incident clearance times. Our numerical methods include M/PH₂/c/K models with many servers and with phase‐type distributions for the time until an incident occurs or is cleared. We also investigate different time scalings for the rate of incident occurrence and clearance. Copyright © 2009 John Wiley & Sons, Ltd.     

索赔到达过程为马氏跳过程的一类风险模型

论将索赔到达点过程由Poisson点过程推广为由马氏链的跳跃点形成的点过程，保费收取由净收入随机确定，我们得到破产概率ψ（u)及条件破产概率φi(u)满足的积分方程．     

Optimal investment and reinsurance for an insurer under Markov-modulated financial market

This study examines optimal investment and reinsurance policies for an insurer with the classical surplus process. It assumes that the financial market is driven by a drifted Brownian motion with coefficients modulated by an external Markov process specified by the solution to a stochastic differential equation. The goal of the insurer is to maximize the expected terminal utility. This paper derives the Hamilton–Jacobi–Bellman (HJB) equation associated with the control problem using a dynamic programming method. When the insurer admits an exponential utility function, we prove that there exists a unique and smooth solution to the HJB equation. We derive the explicit optimal investment policy by solving the HJB equation. We can also find that the optimal reinsurance policy optimizes a deterministic function. We also obtain the upper bound for ruin probability in finite time for the insurer when the insurer adopts optimal policies.     

Analysis of optimal and nearly optimal sequencing policies for a closed queueing network

We analyze sequencing policies designed to most effectively utilize the resources of a closed queueing network representation of a manufacturing system. A continuous time Markov decision process formulation is used to compare the performance of optimal sequencing policies and a heuristic developed by analyzing a heavy traffic approximation of the system.     

Validating state-dependent queueing models for uninterrupted traffic flows using simulation

In this paper, the effectiveness of state-dependent queueing models for analyzing traffic flows is tested by comparing the speeds generated by the queueing models with the ones obtained by simulation. Simulation is thus used to evaluate speeds generated by the different queueing models. Different state-dependency functions are described and their performance is assessed. An M/G/1 queueing model with Gaussian state-dependency outperforms all other state-dependent queueing models. Different test results and insights are provided. Received: July 2004, Revised: September 2005 AMS classification: 60K25, 60K30     

Fluid queue driven by anM/M/1 queue

A fluid queue receiving its input from the output of a precedingM/M/1 queue is considered. The input can be characterized as a Markov modulated rate process and the well known spectral decomposition technique can be applied. The novel features in this system relate to the nature of the spectrum, which is shown to be composed of a continuous part and one or two discrete points depending on whether the load of the fluid queue is less or greater than the output to input rate ratio. Explicit expressions of the generalized eigenvectors are given in terms of Chebyshev polynomials of the second kind, and the resolution of unity is determined. The solution for the buffer content distribution is obtained as a simple integral expression. Numerical examples are given.     

Analysis of multi-level queueing systems with servers breakdown by using recursive solution technique

In this paper we construct a multi-level queueing model that alternates between three modes of an operation system. The service times have followed an Erlang type K   distribution with parameter μ$\mu$. Customers arrive in batches according to a time-homogeneous compound Poisson process with mean rate λ$\lambda$ for the batches. Our aim is to give a recursive scheme for the solution of the steady state equations. Next we derive some important measures of performance which may affect the efficiency of the system under consideration such as the expected waiting time per customer, the expected number of customers who arrive to a full system. The expected number of customers will also be calculated. Finally, we can also calculate the efficiency measures of the system by using the recursive results through an example.     

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.