Capacity expansion under a service‐level constraint for uncertain demand with lead times

For a service provider facing stochastic demand growth, expansion lead times and economies of scale complicate the expansion timing and sizing decisions. We formulate a model to minimize the infinite horizon expected discounted expansion cost under a service‐level constraint. The service level is defined as the proportion of demand over an expansion cycle that is satisfied by available capacity. For demand that follows a geometric Brownian motion process, we impose a stationary policy under which expansions are triggered by a fixed ratio of demand to the capacity position, i.e., the capacity that will be available when any current expansion project is completed, and each expansion increases capacity by the same proportion. The risk of capacity shortage during a cycle is estimated analytically using the value of an up‐and‐out partial barrier call option. A cutting plane procedure identifies the optimal values of the two expansion policy parameters simultaneously. Numerical instances illustrate that if demand grows slowly with low volatility and the expansion lead times are short, then it is optimal to delay the start of expansion beyond when demand exceeds the capacity position. Delays in initiating expansions are coupled with larger expansion sizes. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Service design at diagnostic service centers

We study a service design problem in diagnostic service centers, call centers that provide medical advice to patients over the phone about what the appropriate course of action is, based on the caller's symptoms. Due to the tension between increased diagnostic accuracy and the increase in waiting times more in‐depth service requires, managers face a difficult decision in determining the optimal service depth to guide the diagnostic process. The specific problem we consider models the situation when the capacity (staffing level) at the center is fixed, and when the callers have both congestion‐ and noncongestion‐related costs relating to their call. We develop a queueing model incorporating these features and find that the optimal service depth can take one of two different structures, depending on factors such as the nurses' skill level and the maximum potential demand. Sensitivity analyses of the two optimal structures show that they are quite different. In some situations, it may (or may not) be optimal for the manager to try to expand the demand at the center, and increasing skill level may (or may not) increase congestion. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Revenue sharing contracts in a supply chain with uncontractible actions

We consider a supplier–customer relationship where the customer faces a typical Newsvendor problem of determining perishable capacity to meet uncertain demand. The customer outsources a critical, demand‐enhancing service to an outside supplier, who receives a fixed share of the revenue from the customer. Given such a linear sharing contract, the customer chooses capacity and the service supplier chooses service effort level before demand is realized. We consider the two cases when these decisions are made simultaneously (simultaneous game) or sequentially (sequential game). For each game, we analyze how the equilibrium solutions vary with the parameters of the problem. We show that in the equilibrium, it is possible that either the customer's capacity increases or the service supplier's effort level decreases when the supplier receives a larger share of the revenue. We also show that given the same sharing contract, the sequential game always induces a higher capacity and more effort. For the case of additive effort effect and uniform demand distribution, we consider the customer's problem of designing the optimal contract with or without a fixed payment in the contract, and obtain sensitivity results on how the optimal contract depends on the problem parameters. For the case of fixed payment, it is optimal to allocate more revenue to the supplier to induce more service effort when the profit margin is higher, the cost of effort is lower, effort is more effective in stimulating demand, the variability of demand is smaller or the supplier makes the first move in the sequential game. For the case of no fixed payment, however, it is optimal to allocate more revenue to the supplier when the variability of demand is larger or its mean is smaller. Numerical examples are analyzed to validate the sensitivity results for the case of normal demand distribution and to provide more managerial insights. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Optimal staffing in nonstationary service centers with constraints

This paper considers optimal staffing in service centers. We construct models for profit and cost centers using dynamic rate queues. To allow for practical optimal controls, we approximate the queueing process using a Gaussian random variable with equal mean and variance. We then appeal to the Pontryagin's maximum principle to derive a closed form square root staffing (SRS) rule for optimal staffing. Unlike most traditional SRS formulas, the main parameter in our formula is not the probability of delay but rather a cost‐to‐benefit ratio that depends on the shadow price. We show that the delay experienced by customers can be interpreted in terms of this ratio. Throughout the article, we provide theoretical support of our analysis and conduct extensive numerical experiments to reinforce our findings. To this end, various scenarios are considered to evaluate the change in the staffing levels as the cost‐to‐benefit ratio changes. We also assess the change in the service grade and the effects of a service‐level agreement constraint. Our analysis indicates that the variation in the ratio of customer abandonment over service rate particularly influences staffing levels and can lead to drastically different policies between profit and cost service centers. Our main contribution is the introduction of new analysis and managerial insights into the nonstationary optimal staffing of service centers, especially when the objective is to maximize profitability. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 615–630, 2017     

Optimal control of an M/G/1 queue with impatient priority customers

An optimal operating policy is characterized for the infinite‐horizon average‐cost case of a single server queueing control problem. The server may be turned on at arrival epochs or off at departure epochs. Two classes of customers, each of them arriving according to an independent Poisson processes, are considered. An arriving 1‐customer enters the system if the server is turned on upon his arrival, or if the server is on and idle. In the former case, the 1‐customer is selected for service ahead of those customers waiting in the system; otherwise he leaves the system immediately. 2‐Customers remain in the system until they complete their service requirements. Under a linear cost structure, this paper shows that a stationary optimal policy exists such that either (1) leaves the server on at all times, or (2) turns the server off when the system is empty. In the latter case, we show that the stationary optimal policy is a threshold strategy, this feature being commonplace in most of priority queueing systems and inventory models. However, the optimal policy in our model is determined by two thresholds instead of one. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 201–209, 2001     

Optimal state-dependent pricing policies for a class of stochastic multiunit service systems

This paper models a k-unit service system (e.g., a repair, maintenance, or rental facility) with Poisson arrivals, exponential service times, and no queue. If we denote the number of units that are busy as the state of the system, the state-dependent pricing model formalizes the intuitive notion that when most units are idle, the price (i.e., the service charge per unit time) should be low, and when most units are busy, the price should be higher than the average. A computationally efficient algorithm based on a nonlinear programming formulation of the problem is provided for determination of the optimal state-dependent prices. The procedure ultimately reduces to the search on a single variable in an interval to determine the unique intersection point of a concave increasing function and a linear decreasing function. The algorithm takes, on the average, only about 1/2 second per problem on the IBM 360/65 (FORTRAN G Compiler). A discrete optimal-control approach to the problem is shown to result in essentially the same procedure as the nonlinear-programming formulation. Several properties of the optimal state-dependent prices are given. Comparisons of the optimal values of the objective function for the state-dependent and state-independent pricing policies show that the former is on the average, only about 0.7% better than the latter, which may explain partly why state-dependent pricing is not prevalent in many service systems. Potential generalizations of the model are discussed.     

Determination of the optimal investment in end products and repair resources

This paper demonstrates how to determine the minimal cost combination of end products and repair service capability in order to maintain a given level of operating end products. It is shown that the general rule for optimal resource allocation requires simply that the absolute value of the marginal factor cost of repair services divided by the marginal factor cost of end products be equal to the arrival rate of end products to repair. The model is applied to the problem of determining the resources required to support an operating level of Navy F-4 aircraft.     

Dynamic service rate control for a single‐server queue with Markov‐modulated arrivals

We consider the problem of service rate control of a single‐server queueing system with a finite‐state Markov‐modulated Poisson arrival process. We show that the optimal service rate is nondecreasing in the number of customers in the system; higher congestion levels warrant higher service rates. On the contrary, however, we show that the optimal service rate is not necessarily monotone in the current arrival rate. If the modulating process satisfies a stochastic monotonicity property, the monotonicity is recovered. We examine several heuristics and show where heuristics are reasonable substitutes for the optimal control. None of the heuristics perform well in all the regimes and the fluctuation rate of the modulating process plays an important role in deciding the right heuristic. Second, we discuss when the Markov‐modulated Poisson process with service rate control can act as a heuristic itself to approximate the control of a system with a periodic nonhomogeneous Poisson arrival process. Not only is the current model of interest in the control of Internet or mobile networks with bursty traffic, but it is also useful in providing a tractable alternative for the control of service centers with nonstationary arrival rates. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 661–677, 2013     

Requirements planning for modular products

The focus of this paper is on determining the requirements of different component options of a modular end‐product in an uncertain environment. We explicitly model two distinct sources of uncertainty: stochastic end‐product demand and unknown market proportions for the different product options available. Our cost minimizing model focuses on determining the optimal requirements policies for component options that meet a pre‐set service level. We show that simple common‐sense requirements policies are not generally optimal; there is a non‐linear connection between service level and component requirements that is hard to characterize without a detailed analysis. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Robustness of efficient server assignment policies to service time distributions in finite‐buffered lines

We study the assignment of flexible servers to stations in tandem lines with service times that are not necessarily exponentially distributed. Our goal is to achieve optimal or near‐optimal throughput. For systems with infinite buffers, it is already known that the effective assignment of flexible servers is robust to the service time distributions. We provide analytical results for small systems and numerical results for larger systems that support the same conclusion for tandem lines with finite buffers. In the process, we propose server assignment heuristics that perform well for systems with different service time distributions. Our research suggests that policies known to be optimal or near‐optimal for Markovian systems are also likely to be effective when used to assign servers to tasks in non‐Markovian systems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Distribution free bounds for service constrained (Q,r) inventory systems

A classical and important problem in stochastic inventory theory is to determine the order quantity (Q) and the reorder level (r) to minimize inventory holding and backorder costs subject to a service constraint that the fill rate, i.e., the fraction of demand satisfied by inventory in stock, is at least equal to a desired value. This problem is often hard to solve because the fill rate constraint is not convex in (Q, r) unless additional assumptions are made about the distribution of demand during the lead‐time. As a consequence, there are no known algorithms, other than exhaustive search, that are available for solving this problem in its full generality. Our paper derives the first known bounds to the fill‐rate constrained (Q, r) inventory problem. We derive upper and lower bounds for the optimal values of the order quantity and the reorder level for this problem that are independent of the distribution of demand during the lead time and its variance. We show that the classical economic order quantity is a lower bound on the optimal ordering quantity. We present an efficient solution procedure that exploits these bounds and has a guaranteed bound on the error. When the Lagrangian of the fill rate constraint is convex or when the fill rate constraint does not exist, our bounds can be used to enhance the efficiency of existing algorithms. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 635–656, 2000     

Optimal control of entry to an M/Ek/1 queue serving several classes of customers

The individual and social optimum control policies for entry to an M/M//1 queue serving several classes of customers have been shown to be control-limit policies. The technique of policy iteration provides the social optimum policy for such a queue in a straightforward manner. In this article, the problem of finding the optimal control policy for the M/E_k/1 system is solved, thereby expanding the potential applicability of the solutions developed. The Markovian nature of the queueing system is preserved by considering the service as having k sequential phases, each with independent, identically distributed, exponential service times, through which a customer must pass to be serviced. The optimal policy derived by policy iteration for such a system is likely to be difficult to use because it requires knowledge of the number of phases rather than customers in the system when an arrival occurs. To circumvent this difficulty, a heuristic is used to find a good usable (implementable) solution. In addition, a mixed-integer program is developed which yields the optimal implementable solution when solved.     

An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system

A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled π^S) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (π^M) is a myopic heuristic which works well when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a policy improvement step to the asymptotically optimal heuristic π^S, in which we use a fluid model to obtain an approximation for the value function of π^S. The performance of the proposed heuristic is investigated in an extensive numerical study. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

Optimal admission pricing policies for M/Ek/1 queues

This paper extends the Low-Lippman M/M/1 model to the case of Gamma service times. Specifically, we have a queue in which arrivals are Poisson, service time is Gamma-distributed, and the arrival rate to the system is subject to setting an admission fee p. The arrival rate λ(p) is non-increasing in p. We prove that the optimal admission fee p^* is a non-decreasing function of the customer work load on the server. The proof is for an infinite capacity queue and holds for the infinite horizon continuous time Markov decision process. In the special case of exponential service time, we extend the Low-Lippman model to include a state-dependent service rate and service cost structure (for finite or infinite time horizon and queue capacity). Relatively recent dynamic programming techniques are employed throughout the paper. Due to the large class of functions represented by the Gamma family, the extension is of interest and utility.     

An application of yield management for Internet Service Providers

In this paper we study strategies for better utilizing the network capacity of Internet Service Providers (ISPs) when they are faced with stochastic and dynamic arrivals and departures of customers attempting to log‐on or log‐off, respectively. We propose a method in which, depending on the number of modems available, and the arrival and departure rates of different classes of customers, a decision is made whether to accept or reject a log‐on request. The problem is formulated as a continuous time Markov Decision Process for which optimal policies can be readily derived using techniques such as value iteration. This decision maximizes the discounted value to ISPs while improving service levels for higher class customers. The methodology is similar to yield management techniques successfully used in airlines, hotels, etc. However, there are sufficient differences, such as no predefined time horizon or reservations, that make this model interesting to pursue and challenging. This work was completed in collaboration with one of the largest ISPs in Connecticut. The problem is topical, and approaches such as those proposed here are sought by users. © 2001 John Wiley & Sons, Inc., Naval Research Logistics 48:348–362, 2001     

Optimal renewal policies for complex systems

Most maintenance and replacement models for industrial equipment have been developed for independent single-component machines. Most equipment, however, consists of multiple components. Also, when the maintenance crew services several machines, the maintenance policy for each machine is not independent of the states of the other machines. In this paper, two dynamic programming replacement models are presented. The first is used to determine the optimal replacement policy for multi-component equipment. The second is used to determine the optimal replacement policy for a multi-machine system which uses one replacement crew to service several machines. In addition, an approach is suggested for developing an efficient replacement policy for a multi-component, multi-machine system.     

Value management of diagnostic equipment with cancelation,no‐show,and emergency patients

Magnetic resonance imaging and other multifunctional diagnostic facilities, which are considered as scarce resources of hospitals, typically provide services to patients with different medical needs. This article examines the admission policies during the appointment management of such facilities. We consider two categories of patients: regular patients who are scheduled in advance through an appointment system and emergency patients with randomly generated demands during the workday that must be served as soon as possible. According to the actual medical needs of patients, regular patients are segmented into multiple classes with different cancelation rates, no‐show probabilities, unit value contributions, and average service times. Management makes admission decisions on whether or not to accept a service request from a regular patient during the booking horizon to improve the overall value that could be generated during the workday. The decisions should be made by considering the cancelation and no‐show behavior of booked patients as well as the emergency patients that would have to be served because any overtime service would lead to higher costs. We studied the optimal admission decision using a continuous‐time discrete‐state dynamic programming model. Identifying an optimal policy for this discrete model is analytically intractable and numerically inefficient because the state is multidimensional and infinite. We propose to study a deterministic counterpart of the problem (i.e., the fluid control problem) and to develop a time‐based fluid policy that is shown to be asymptotically optimal for large‐scale problems. Furthermore, we propose to adopt a mixed fluid policy that is developed based on the information obtained from the fluid control problem. Numerical experiments demonstrate that this improved policy works effectively for small‐scale problems. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 287–304, 2016     

Optimal control of noncollaborative servers in two‐stage tandem queueing systems

We consider two‐stage tandem queueing systems with dedicated servers in each station and a flexible server that is trained to serve both stations. We assume no arrivals, exponential service times, and linear holding costs for jobs present in the system. We study the optimal dynamic assignment of servers to jobs assuming a noncollaborative work discipline with idling and preemptions allowed. For larger holding costs in the first station, we show that (i) nonidling policies are optimal and (ii) if the flexible server is not faster than the dedicated servers, the optimal server allocation strategy has a threshold‐type structure. For all other cases, we provide numerical results that support the optimality of threshold‐type policies. Our numerical experiments also indicate that when the flexible server is faster than the dedicated server of the second station, the optimal policy may have counterintuitive properties, which is not the case when a collaborative service discipline is assumed. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 435–446, 2014     

The discrete max-min problem

The historic max-min problem is examined as a discrete process rather than in its more usual continuous mode. Since the practical application of the max-min model usually involves discrete objects such as ballistic missiles, the discrete formulation of the problem seems quite appropriate. This paper uses an illegal modification to the dynamic programming process to obtain an upper bound to the max-min value. Then a second but legal application of dynamic programming to the minimization part of the problem for a fixed maximizing vector will give a lower bound to the max-min value. Concepts of optimal stopping rules may be applied to indicate when sufficiently near optimal solutions have been obtained.     

Scheduling customer arrivals to a stochastic service system

An efficient algorithm for determining the optimal arrival schedule for customers in a stochastic service system is developed. All customers arrive exactly when scheduled, and service times are modeled as iid Erlang random variables. Costs are incurred at a fixed rate per unit of time each customer waits for service, and an additional cost is incurred for every unit of time the server operates beyond a scheduled closing time. The objective is to minimize total operating cost. This type of problem arises in many operational contexts including transportation, manufacturing, and appointment‐based services. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 549–559, 1999