Stochastic call center staffing with uncertain arrival,service and abandonment rates: A Bayesian perspective

In this article, we introduce staffing strategies for the Erlang‐A queuing system in call center operations with uncertain arrival, service, and abandonment rates. In doing so, we model the system rates using gamma distributions that create randomness in operating characteristics used in the optimization formulation. We divide the day into discrete time intervals where a simulation based stochastic programming method is used to determine staffing levels. More specifically, we develop a model to select the optimal number of agents required for a given time interval by minimizing an expected cost function, which consists of agent and abandonment (opportunity) costs, while considering the service quality requirements such as the delay probability. The objective function as well as the constraints in our formulation are random variables. The novelty of our approach is to introduce a solution method for the staffing of an operation where all three system rates (arrival, service, and abandonment) are random variables. We illustrate the use of the proposed model using both real and simulated call center data. In addition, we provide solution comparisons across different formulations, consider a dynamic extension, and discuss sensitivity implications of changing constraint upper bounds as well as prior hyper‐parameters. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 460–478, 2016     

Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems

In Assemble‐To‐Order (ATO) systems, situations may arise in which customer demand must be backlogged due to a shortage of some components, leaving available stock of other components unused. Such unused component stock is called remnant stock. Remnant stock is a consequence of both component ordering decisions and decisions regarding allocation of components to end‐product demand. In this article, we examine periodic‐review ATO systems under linear holding and backlogging costs with a component installation stock policy and a First‐Come‐First‐Served (FCFS) allocation policy. We show that the FCFS allocation policy decouples the problem of optimal component allocation over time into deterministic period‐by‐period optimal component allocation problems. We denote the optimal allocation of components to end‐product demand as multimatching. We solve the multi‐matching problem by an iterative algorithm. In addition, an approximation scheme for the joint replenishment and allocation optimization problem with both upper and lower bounds is proposed. Numerical experiments for base‐stock component replenishment policies show that under optimal base‐stock policies and optimal allocation, remnant stock holding costs must be taken into account. Finally, joint optimization incorporating optimal FCFS component allocation is valuable because it provides a benchmark against which heuristic methods can be compared. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 158–169, 2015     

Appointment scheduling at a multidisciplinary outpatient clinic using stochastic programming

The purpose of this paper is to investigate the problem of constructing an appointment template for scheduling patients at a specific type of multidisciplinary outpatient clinic called an integrated practice unit (IPU). The focus is on developing and solving a stochastic optimization model for a back pain IPU in the face of random arrivals, an uncertain patient mix, and variable service times. The deterministic version of the problem is modeled as a mixed integer program with the objective of minimizing a weighted combination of clinic closing time (duration) and total patient waiting time (length of stay). A two‐stage stochastic program is then derived to account for the randomness and the sequential nature of the decisions. Although it was not possible to solve the two‐stage problem for even a limited number of scenarios, the wait‐and‐see (WS) problem was sufficiently tractable to provide a lower bound on the stochastic solution. The introduction of valid inequalities, limiting indices, and the use of special ordered sets helped to speed up the computations. A greedy heuristic was also developed to obtain solutions much more quickly. Out of practical considerations, it was necessary to develop appointment templates with time slots at fixed intervals, which are not available from the WS solution. The first to be derived was the expected value (EV) template that is used to find the expected value of the EV solution (EEV). This solution provides an upper bound on the objective function value of the two‐stage stochastic program. The average gap between the EEV and WS solutions was 18%. Results from extensive computational testing are presented for the EV template and for our adaptation of three other templates found in the literature. Depending on the relative importance of the two objective function metrics, the results demonstrate the trade‐off that exists between them. For the templates investigated, the “closing time” ranged from an average of 235 to 275 minutes for a 300‐minute session, while the corresponding “total patient time in clinic” ranged from 80 to 71 minutes.     

Optimal burn‐in procedure for periodically inspected systems

Burn‐in is a widely used method to improve the quality of products or systems after they have been produced. In this paper, we study burn‐in procedure for a system that is maintained under periodic inspection and perfect repair policy. Assuming that the underlying lifetime distribution of a system has an initially decreasing and/or eventually increasing failure rate function, we derive upper and lower bounds for the optimal burn‐in time, which maximizes the system availability. Furthermore, adopting an age replacement policy, we derive upper and lower bounds for the optimal age parameter of the replacement policy for each fixed burn‐in time and a uniform upper bound for the optimal burn‐in time given the age replacement policy. These results can be used to reduce the numerical work for determining both optimal burn‐in time and optimal replacement policy. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A stochastic programming approach for chemotherapy appointment scheduling

Chemotherapy appointment scheduling is a challenging problem due to the uncertainty in premedication and infusion durations. In this paper, we formulate a two‐stage stochastic mixed integer programming model for the chemotherapy appointment scheduling problem under limited availability of nurses and infusion chairs. The objective is to minimize the expected weighted sum of nurse overtime, chair idle time, and patient waiting time. The computational burden to solve real‐life instances of this problem to optimality is significantly high, even in the deterministic case. To overcome this burden, we incorporate valid bounds and symmetry breaking constraints. Progressive hedging algorithm is implemented in order to solve the improved formulation heuristically. We enhance the algorithm through a penalty update method, cycle detection and variable fixing mechanisms, and a linear approximation of the objective function. Using numerical experiments based on real data from a major oncology hospital, we compare our solution approach with several scheduling heuristics from the relevant literature, generate managerial insights related to the impact of the number of nurses and chairs on appointment schedules, and estimate the value of stochastic solution to assess the significance of considering uncertainty.     

A sequential dynamic pricing model and its applications

Consider a sequential dynamic pricing model where a seller sells a given stock to a random number of customers. Arriving one at a time, each customer will purchase one item if the product price is lower than her personal reservation price. The seller's objective is to post a potentially different price for each customer in order to maximize the expected total revenue. We formulate the seller's problem as a stochastic dynamic programming model, and develop an algorithm to compute the optimal policy. We then apply the results from this sequential dynamic pricing model to the case where customers arrive according to a continuous‐time point process. In particular, we derive tight bounds for the optimal expected revenue, and develop an asymptotically optimal heuristic policy. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

The probability of the existence of a feasible flow in a stochastic transportation network

Stochastic transportation networks arise in various real world applications, for which the probability of the existence of a feasible flow is regarded as an important performance measure. Although the necessary and sufficient condition for the existence of a feasible flow represented by an exponential number of inequalities is a well‐known result in the literature, the computation of the probability of all such inequalities being satisfied jointly is a daunting challenge. The state‐of‐the‐art approach of Prékopa and Boros, Operat Res 39 (1991) 119–129 approximates this probability by giving its lower and upper bounds using a two‐part procedure. The first part eliminates all redundant inequalities and the second gives the lower and upper bounds of the probability by solving two well‐defined linear programs with the inputs obtained from the first part. Unfortunately, the first part may still leave many non‐redundant inequalities. In this case, it would be very time consuming to compute the inputs for the second part even for small‐sized networks. In this paper, we first present a model that can be used to eliminate all redundant inequalities and give the corresponding computational results for the same numerical examples used in Prékopa and Boros, Operat Res 39 (1991) 119–129. We also show how to improve the lower and upper bounds of the probability using the multitree and hypermultitree, respectively. Furthermore, we propose an exact solution approach based on the state space decomposition to compute the probability. We derive a feasible state from a state space and then decompose the space into several disjoint subspaces iteratively. The probability is equal to the sum of the probabilities in these subspaces. We use the 8‐node and 15‐node network examples in Prékopa and Boros, Operat Res 39 (1991) 119–129 and the Sioux‐Falls network with 24 nodes to show that the space decomposition algorithm can obtain the exact probability of these classical examples efficiently. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 479–491, 2016     

Optimal power control in a wireless network using a model with stochastic link coefficients

This paper addresses optimal power allocation in a wireless communication network under uncertainty. The paper introduces a framework for optimal transmit power allocation in a wireless network where both the useful and interference coefficients are random. The new approach to power control is based on a stochastic programming formulation with probabilistic SIR constraints. This allows to state the power allocation problem as a convex optimization problem assuming normally or log‐normally distributed communication link coefficients. Numerical examples illustrate the performance of the optimal stochastic power allocation. A distributed algorithm for the decentralized solution of the stochastic power allocation problem is discussed. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Optimal empty vehicle redistribution for hub‐and‐spoke transportation systems

This article considers the empty vehicle redistribution problem in a hub‐and‐spoke transportation system, with random demands and stochastic transportation times. An event‐driven model is formulated, which yields the implicit optimal control policy. Based on the analytical results for two‐depot systems, a dynamic decomposition procedure is presented which produces a near‐optimal policy with linear computational complexity in terms of the number of spokes. The resulting policy has the same asymptotic behavior as that of the optimal policy. It is found that the threshold‐type control policy is not usually optimal in such systems. The results are illustrated through small‐scale numerical examples. Through simulation the robustness of the dynamic decomposition policy is tested using a variety of scenarios: more spokes, more vehicles, different combinations of distribution types for the empty vehicle travel times and loaded vehicle arrivals. This shows that the dynamic decomposition policy is significantly better than a heuristics policy in all scenarios and appears to be robust to the assumptions of the distribution types. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

Newsvendor bounds and heuristics for serial supply chains with regular and expedited shipping

We study an infinite‐horizon, N‐stage, serial production/inventory system with two transportation modes between stages: regular shipping and expedited shipping. The optimal inventory policy for this system is a top–down echelon base‐stock policy, which can be computed through minimizing 2N nested convex functions recursively (Lawson and Porteus, Oper Res 48 (2000), 878–893). In this article, we first present some structural properties and comparative statics for the parameters of the optimal inventory policies, we then derive simple, newsvendor‐type lower and upper bounds for the optimal control parameters. These results are used to develop near optimal heuristic solutions for the echelon base‐stock policies. Numerical studies show that the heuristic performs well. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Rescheduling to minimize makespan on a changing number of identical processors

We consider the problem of rescheduling n jobs to minimize the makespan on m parallel identical processors when m changes value. We show this problem to be NP-hard in general. Call a list schedule totally optimal if it is optimal for all m = 1, …,n. When n is less than 6, there always exists a totally optimal schedule, but for n ≥ 6 this can fail. We show that an exact solution is less robust than the largest processing time first (LPT) heuristic and discuss implications for polynomial approximation schemes and hierarchical planning models.     

On online bin packing with LIB constraints

In many applications of packing, the location of small items below large items, inside the packed boxes, is forbidden. We consider a variant of the classic online one‐dimensional bin packing, in which items allocated to each bin are packed there in the order of arrival, satisfying the condition above. This variant is called online bin packing problem with LIB (larger item in the bottom) constraints. We give an improved analysis of First Fit showing that its competitive ratio is at most , and design a lower bound of 2 on the competitive ratio of any online algorithm. In addition, we study the competitive ratio of First Fit as a function of an upper bound (where d is a positive integer) on the item sizes. Our upper bound on the competitive ratio of First Fit tends to 2 as d grows, whereas the lower bound of two holds for any value of d. Finally, we consider several natural and well known algorithms, namely, Best Fit, Worst Fit, Almost Worst Fit, and Harmonic, and show that none of them has a finite competitive ratio for the problem. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Simultaneous production of market‐specific and global products: A two‐stage stochastic program with additional demand after recourse

This paper analyzes the simultaneous production of market‐specific products tailored to the needs of individual regions and a global product that could be sold in many regions. We assume that the global product costs more to manufacture, but allows the decision concerning the allocation of products to regions to be delayed until after the manufacturing process has been completed. We further assume that there is additional demand after the region allocation but prior to delivery, extending the two‐stage stochastic program with recourse to include additional stochastic demand after the recourse. This scenario arises, for example, when there is additional uncertainty during a delivery delay which might occur with transoceanic shipments. We develop conditions for optimality assuming a single build‐allocate‐deliver cycle and stochastic demand during both the build and deliver periods. The optimal policy calls for the simultaneous production of market‐specific and global products, even when the global product is substantially more costly than the market‐specific product. In addition, we develop bounds on the performance of the optimal policy for the multicycle problem. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 438–461, 2003     

Managing waiting times of backordered demands in single‐stage (Q,r) inventory systems

We present a service constrained (Q, r) model that minimizes expected holding and ordering costs subject to an upper bound on the expected waiting time of demands that are actually backordered. We show that, after optimizing over r, the average cost is quasiconvex in Q for logconcave continuous lead time demand distributions. For logconcave discrete lead time demand distributions we find a single‐pass efficient algorithm based on a novel search stopping criterion. The algorithm also allows for bounds on the variability of the service measure. A brief numerical study indicates how the bounds on service impact the optimal average cost and the optimal (Q, r) choice. The discrete case algorithm can be readily adapted to provide a single pass algorithm for the traditional model that bounds the expected waiting time of all demands (backordered or not). © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 557–573, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10028     

A branch‐and‐price approach for the stochastic generalized assignment problem

In this article, we address a stochastic generalized assignment machine scheduling problem in which the processing times of jobs are assumed to be random variables. We develop a branch‐and‐price (B&P) approach for solving this problem wherein the pricing problem is separable with respect to each machine, and has the structure of a multidimensional knapsack problem. In addition, we explore two other extensions of this method—one that utilizes a dual‐stabilization technique and another that incorporates an advanced‐start procedure to obtain an initial feasible solution. We compare the performance of these methods with that of the branch‐and‐cut (B&C) method within CPLEX. Our results show that all B&P‐based approaches perform better than the B&C method, with the best performance obtained for the B&P procedure that includes both the extensions aforementioned. We also utilize a Monte Carlo method within the B&P scheme, which affords the use of a small subset of scenarios at a time to estimate the “true” optimal objective function value. Our experimental investigation reveals that this approach readily yields solutions lying within 5% of optimality, while providing more than a 10‐fold savings in CPU times in comparison with the best of the other proposed B&P procedures. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 131–143, 2014     

Bi‐objective missile rescheduling for a naval task group with dynamic disruptions

This paper considers the rescheduling of surface‐to‐air missiles (SAMs) for a naval task group (TG), where a set of SAMs have already been scheduled to intercept a set of anti‐ship missiles (ASMs). In missile defense, the initial engagement schedule is developed according to the initial state of the defensive and attacking units. However, unforeseen events may arise during the engagement, creating a dynamic environment to be handled, and making the initial schedule infeasible or inefficient. In this study, the initial engagement schedule of a TG is assumed to be disrupted by the occurrence of a destroyed ASM, the breakdown of a SAM system, or an incoming new target ASM. To produce an updated schedule, a new biobjective mathematical model is formulated that maximizes the no‐leaker probability value for the TG and minimizes the total deviation from the initial schedule. With the problem shown to be NP‐hard, some special cases are presented that can be solved in polynomial time. We solve small size problems by the augmented ? ‐ constraint method and propose heuristic procedures to generate a set of nondominated solutions for larger problems. The results are presented for different size problems and the total effectiveness of the model is evaluated.     

Bounding the optimal burn‐in time for a system with two types of failure

Burn‐in is a widely used method to improve the quality of products or systems after they have been produced. In this paper, we consider the problem of determining bounds to the optimal burn‐in time and optimal replacement policy maximizing the steady state availability of a repairable system. It is assumed that two types of system failures may occur: One is Type I failure (minor failure), which can be removed by a minimal repair, and the other is Type II failure (catastrophic failure), which can be removed only by a complete repair. Assuming that the underlying lifetime distribution of the system has a bathtub‐shaped failure rate function, upper and lower bounds for the optimal burn‐in time are provided. Furthermore, some other applications of optimal burn‐in are also considered. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

A note on optimal pricing for finite capacity queueing systems with multiple customer classes

This article investigates optimal static prices for a finite capacity queueing system serving customers from different classes. We first show that the original multi‐class formulation in which the price for each class is a decision variable can be reformulated as a single dimensional problem with the total load as the decision variable. Using this alternative formulation, we prove an upper bound for the optimal arrival rates for a fairly large class of queueing systems and provide sufficient conditions that ensure the existence of a unique optimal arrival rate vector. We show that these conditions hold for M/M/1/m and M/G/s/s systems and prove structural results on the relationships between the optimal arrival rates and system capacity. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008