Optimal admission policies for a finite queue with bursty arrivals

We consider a service system with a single server, a finite waiting room and two classes of customers with deterministic service time. Primary jobs arrive at random and are admitted whenever there is room in the system. At the beginning of each period, secondary jobs can be admitted from an infinite pool. A revenue is earned upon admission of each job, with the primary jobs bringing a higher contribution than the secondary jobs, the objective being to maximize the total discounted revenue over an infinite horizon. We model the system as a discrete time Markov decision process and show that a monotone admission policy is optimal when the number of primary arrivals has a fixed distribution. Moreover, when the primary arrival distribution varies with time according to a finite state Markov chain, we show that the optimal policy is conditionally monotone and that the numerical computation of an optimal policy, in this case, is substantially more difficult than in the case of stationary arrivals.This research was supported in part by the National Science Foundation, under grant ECS-8803061, while the author was at the University of Arizona.     

Queues with group arrivals and exhaustive service discipline

Queues with compound Poisson arrivals, phase-type service and exhaustive service discipline are studied. An algorithmic method is developed to compute the steady-state probability distribution of the number of customers in the system with unlimited or limited queue capacities. Examples with different model parameters are given to show the computational efficiency of the method. In the Appendix, the stochastic decomposition property for the queues with single arrivals and with exhaustive service discipline is extended to queues with group arrivals.     

Vehicle routing with dynamic travel times: A queueing approach

Transportation is an important component of supply chain competitiveness since it plays a major role in the inbound, inter-facility, and outbound logistics. In this context, assigning and scheduling vehicle routes is a crucial management problem. In this paper, a vehicle routing problem with dynamic travel times due to potential traffic congestion is considered. The approach developed introduces mainly the traffic congestion component based on queueing theory. This is an innovative modeling scheme to capture travel times. The queueing approach is compared with other approaches and its potential benefits are described and quantified. Moreover, the optimization of the starting times of a route at the distribution center is evaluated. Finally, the trade-off between solution quality and calculation time is discussed. Numerous test instances are used, both to illustrate the appropriateness of the approach as well as to show that time-independent solutions are often unrealistic within a congested traffic environment, which is usually the case on European road networks.     

An algorithm for repairable item inventory system with depot spares and general repair time distribution

We consider the problem of determining the initial spare inventory level for a multi-echelon repairable item inventory system. We extend the previous results to the system, which has an inventory at the central depot as well as at bases and with a general repair time distribution. We propose an algorithm which finds spare inventory level to minimize the total expected cost and simultaneously to satisfy a specified minimum service rate. Extensive computational experiments show that the algorithm is accurate and efficient.     

Simulation-based Selectee Lane queueing design for passenger checkpoint screening

There are two kinds of passenger checkpoint screening lanes in a typical US airport: a Normal Lane and a Selectee Lane that has enhanced scrutiny. The Selectee Lane is not effectively utilized in some airports due to the small amount of passengers selected to go through it. In this paper, we propose a simulation-based Selectee Lane queueing design framework to study how to effectively utilize the Selectee Lane resource. We assume that passengers are classified into several risk classes via some passenger prescreening system. We consider how to assign passengers from different risk classes to the Selectee Lane based on how many passengers are already in the Selectee Lane. The main objective is to maximize the screening system’s probability of true alarm. We first discuss a steady-state model, formulate it as a nonlinear binary integer program, and propose a rule-based heuristic. Then, a simulation framework is constructed and a neighborhood search procedure is proposed to generate possible solutions based on the heuristic solution of the steady-state model. Using the passenger arrival patterns from a medium-size airport, we conduct a detailed case study. We observe that the heuristic solution from the steady-state model results in more than 4% relative increase in probability of true alarm with respect to the current practice. Moreover, starting from the heuristic solution, we obtain even better solutions in terms of both probability of true alarm and expected time in system via a neighborhood search procedure.     

Basic optimality results for Bayesian group replacement policies

The optimal structure of Bayesian group replacement policies for a parallel system of n items with exponential failure times and random failure parameter is presented. The paper contains a proof of the fact that it is optimal to observe the system only at failure times. For the case of two items operating in parallel the exact form of the policy is derived.     

Analysis of the adaptive MMAP[K]/PH[K]/1 queue: A multi-type queue with adaptive arrivals and general impatience

In this paper we introduce the adaptive MMAP[K] arrival process and analyze the adaptive MMAP[K]/PH[K]/1 queue. In such a queueing system, customers of K different types with Markovian inter-arrival times and possibly correlated customer types, are fed to a single server queue that makes use of r thresholds. Service times are phase-type and depend on the type of customer in service. Type k customers are accepted with some probability a_i,k if the current workload is between threshold i − 1 and i. The manner in which the arrival process changes its state after generating a type k customer also depends on whether the customer is accepted or rejected.     

The achievable region method in the optimal control of queueing systems; formulations,bounds and policies

We survey a new approach that the author and his co-workers have developed to formulate stochastic control problems (predominantly queueing systems) asmathematical programming problems. The central idea is to characterize the region of achievable performance in a stochastic control problem, i.e., find linear or nonlinear constraints on the performance vectors that all policies satisfy. We present linear and nonlinear relaxations of the performance space for the following problems: Indexable systems (multiclass single station queues and multiarmed bandit problems), restless bandit problems, polling systems, multiclass queueing and loss networks. These relaxations lead to bounds on the performance of an optimal policy. Using information from the relaxations we construct heuristic nearly optimal policies. The theme in the paper is the thesis that better formulations lead to deeper understanding and better solution methods. Overall the proposed approach for stochastic control problems parallels efforts of the mathematical programming community in the last twenty years to develop sharper formulations (polyhedral combinatorics and more recently nonlinear relaxations) and leads to new insights ranging from a complete characterization and new algorithms for indexable systems to tight lower bounds and nearly optimal algorithms for restless bandit problems, polling systems, multiclass queueing and loss networks.     

A Markovian queueing model for ambulance offload delays

Ambulance offload delays are a growing concern for health care providers in many countries. Offload delays occur when ambulance paramedics arriving at a hospital Emergency Department (ED) cannot transfer patient care to staff in the ED immediately. This is typically caused by overcrowding in the ED. Using queueing theory, we model the interface between a regional Emergency Medical Services (EMS) provider and multiple EDs that serve both ambulance and walk-in patients. We introduce Markov chain models for the system and solve for the steady state probability distributions of queue lengths and waiting times using matrix-analytic methods. We develop several algorithms for computing performance measures for the system, particularly the offload delays for ambulance patients. Using these algorithms, we analyze several three-hospital systems and assess the impact of system resources on offload delays. In addition, simulation is used to validate model assumptions.     

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.     

A two-class discrete-time queueing model with two dedicated servers and global FCFS service discipline

This paper considers a simple discrete-time queueing model with two types (classes) of customers (types 1 and 2) each having their own dedicated server (servers A and B resp.). New customers enter the system according to a general independent arrival process, i.e., the total numbers of arrivals during consecutive time slots are i.i.d. random variables with arbitrary distribution. Service times are deterministically equal to 1 slot each. The system uses a “global FCFS” service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their types. As a consequence of the “global FCFS” rule, customers of one type may be blocked by customers of the other type, in that they may be unable to reach their dedicated server even at times when this server is idle, i.e., the system is basically non-workconserving. One major aim of the paper is to estimate the negative impact of this phenomenon on the queueing performance of the system, in terms of the achievable throughput, the system occupancy, the idle probability of each server and the delay. As it is clear that customers of different types hinder each other more as they tend to arrive in the system more clustered according to class, the degree of “class clustering” in the arrival process is explicitly modeled in the paper and its very direct impact on the performance measures is revealed. The motivation of our work are systems where this kind of blocking is encountered, such as input-queueing network switches or road splits.     

Performance evaluation for general queueing networks in manufacturing systems: Characterizing the trade-off between queue time and utilization

Performance evaluation plays a key role in manufacturing system design and productivity improvement. Characterizing performance objectively is the first step. Inspired by the underlying structure of tandem queues, we have derived an approximate model to characterize the system performance. The model decomposes system queue time and variability into bottleneck and non-bottleneck parts while capturing the dependence among workstations. Compared the new model with prior approaches, the new model not only is more accurate but also requires less information. The property of manufacturing system performance is given based on the insight from the model.     

A complete and simple solution for a discrete-time multi-server queue with bulk arrivals and deterministic service times

A complete distribution for the system content of a discrete-time multi-server queue with an infinite buffer is presented, where each customer arriving in a group requires a deterministic service time that could be greater than one slot. In addition, when the service time equals one slot, a complete distribution for the delay is also presented.     

A dynamic model for optimal design quality and return policies

A clearly explained and generous return policy has been established as a competitive weapon to enhance sales. From the firm’s point of view, a generous return policy will increase sales revenue, but will also increase cost due to increased likelihood of return. Design quality of the product has been used as a competitive weapon for a long time. This paper recognizes the relationship between design quality and price of the product, and the firm’s return policy. Quality level in the product would influence the amount of return directly. When the product quality is higher, the customer satisfaction rate will increase and the probability of return will decrease. We develop a profit-maximization model to jointly obtain optimal policies for the product quality level, price and the return policy over time. The model presented in this paper is dynamic in nature and considers the decisions as the product moves through the life cycle. We obtain a number of managerial guidelines for using marketing and operational strategy variables to obtain the maximum benefit from the market. We mention several future research possibilities.     

An optimal solution for the stochastic version of the Wagner–Whitin dynamic lot-size model

We present an algorithm for determining the optimal solution over the entire planning horizon for the dynamic lot-size model where demand is stochastic and non-stationary. The optimal solution to the deterministic problem is the well-known Wagner–Whitin algorithm. The present work contributes principally to knowledge building and provides a tool for researchers. One potentially useful contribution to practice is the solution to an important special case, where demand follows normal distributions. Other contributions to practice will likely flow from the development of improved heuristics and the improved basis to evaluate heuristic performance.     

An extended queueing control model for facilities with front room and back room operations and mixed-skilled workers

Three related problems arising in retail facilities with front room and back room operations, and cross-trained workers, are considered. In the first problem, the goal is to determine an optimal policy for switching workers between the two rooms. In the second and third problems, the goal is to determine the minimum number of workers that should be hired by the facility such that a satisfactory switching policy exists. We analyze two questions arising from previous work on these problems. Firstly, we demonstrate that the previously proposed policy definition is sub-optimal and cannot represent a set of solutions that are reasonable in practice, and propose an alternative definition. Secondly, we examine the problem of finding the optimal combination of cross-trained and specialized workers under a complete set of assumptions regarding worker costs. This analysis shows that the structure of the optimal solution depends on the policy definition that is employed. Moreover, under some assumptions the cost of the ‘optimal’ solution with the original policy definition will be greater than the cost of the optimal solution with the new one.     

A new dynamic programming algorithm for the single item capacitated dynamic lot size model

We develop a new dynamic programming method for the single item capacitated dynamic lot size model with non-negative demands and no backlogging. This approach builds the Optimal value function in piecewise linear segments. It works very well on the test problems, requiring less than 0.3 seconds to solve problems with 48 periods on a VAX 8600. Problems with the time horizon up to 768 periods are solved. Empirically, the computing effort increases only at a quadratic rate relative to the number of periods in the time horizon.This research was supported in part by NSF grants DDM-8814075 and DMC-8504786.     

A queueing model for mixed loss-delay systems with general interarrival processes for wide-band calls

We investigate the single link mixed loss-delay FIFO system with the exponential holding time distribution, the Markovian interarrival process for the narrow-band calls, and the general independently and identically distributed interarrival process for the wide-band calls. This is achieved by combining the embedded Markov chain method and the matrix-analytic technique.     

Optimal policies for inventory systems with two types of product sharing common hardware platforms: Single period and finite horizon

In this paper, we consider an inventory system whose products share a common hardware platform but are differentiated by two types of software. Choice of different software results in different installation cost and different selling price of the whole product. Product with different software also faces different customer demand. We investigate the optimal proportion of an order to be installed with software 1 or 2, that maximizes expected profit in the single and multiple period scenarios, respectively. The optimal policy is analytically obtained and proved to be an order-up-to policy in each scenario. Our investigation reveals that whether to replenish, and how much to replenish each product depend not only on its own initial inventory level, and system parameters, but also the initial inventory level of the other product. We perform numerical experiments using the optimal policies we have derived in the paper.     

Optimal monotone hysteretic Markov policies in anM/M/1 queueing model with switching costs and finite time horizon

In anM/M/1 queueing model, a decision maker can choosem pairs of arrival- and service rates. He can change his action at any time epoch, a switch of action costs an amount depending on the size of the switch. Besides that there are continuously incurring costs. Over a finite time horizon, there exists an optimal monotone hysteretic Markov policy. This is shown essentially by the technique of time discretization.The work producing this article was done during a half year stay at the University of Leiden, The Netherlands, with Prof. Arie Hordijk. A technical report (a more detailled version of this article) was written there [6]. The opportunity for this stay was given by the University of Bonn, Germany, where the author, at that time, worked as scientific assistant of Prof. M. Schäl.