Discrete‐time analysis of MAP/PH/1 multiclass general preemptive priority queue

We use the matrix‐geometric method to study the MAP/PH/1 general preemptive priority queue with a multiple class of jobs. A procedure for obtaining the block matrices representing the transition matrix P is presented. We show that the special upper triangular structure of the matrix R obtained by Miller [Computation of steady‐state probabilities for M/M/1 priority queues, Oper Res 29(5) (1981), 945–958] can be extended to an upper triangular block structure. Moreover, the subblock matrices of matrix R also have such a structure. With this special structure, we develop a procedure to compute the matrix R. After obtaining the stationary distribution of the system, we study two primary performance indices, namely, the distributions of the number of jobs of each type in the system and their waiting times. Although most of our analysis is carried out for the case of K = 3, the developed approach is general enough to study the other cases (K ≥ 4). © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 662–682, 2003.     

Realignment in the National Football League: Did they do it right?

The National Football League (NFL) in the United States expanded to 32 teams in 2002 with the addition of a team in Houston. At that point, the league was realigned into eight divisions, each containing four teams. We describe a branch‐and‐cut algorithm for minimizing the sum of intradivisional travel distances. We consider first the case where any team can be assigned to any division. We also consider imposing restrictions, such as aligning the AFC (American Football Conference) and the NFC (National Football Conference) separately or maintaining traditional rivalries. We show that the alignment chosen by the NFL does not minimize the sum of intradivisional travel distances, but that it is close to optimal for an alignment that aligns the NFC and AFC separately and imposes some additional restrictions. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 683–701, 2003.     

Potential impact of recharging plug‐in hybrid electric vehicles on locational marginal prices

Plug‐in hybrid electric vehicles (PHEVs), upon market penetration, will create additional recharging loads to the electric power systems. This article considers different recharging scenarios and uses game theoretic models to study the potential impact of the recharging loads on locational marginal prices (wholesale electricity prices). Computational results from a Pennsylvania‐New Jersey‐Maryland Interconnection case study show that, under the existing recharging infrastructures, even a small magnitude of load increase caused by PHEV recharging could have a significant undesirable impact on locational marginal prices. The impact could be mitigated to a varying extent by the availability of possible future recharging infrastructures, including realtime pricing recharging meters, battery stations, or vehicle‐to‐grid technology.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Decomposing inventory routing problems with approximate value functions

We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single‐period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory's value, and solving the multiperiod problem as a sequence of single‐period subproblems drastically decreases computational time without sacrificing solution quality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Scheduling a maintenance activity on parallel identical machines

We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

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     

Optimal inventory and dynamic admission policies for a retailer of seasonal products with affiliate programs and drop‐shipping

This article investigates the optimal inventory and admission policies for a “Clicks‐and‐Bricks” retailer of seasonal products that, in addition to selling through its own physical and online stores, also sells through third‐party websites by means of affiliate programs. Through postings on partners' webpages, an affiliate program allows a retailer to attract customers who would otherwise be missed. However, this retailer needs to pay a commission for each sale that originates from the website operators participating in the program. The retailer may also refer online orders to other sources (such as distributors and manufacturers) for fulfillment through a drop‐shipping agreement and thus earns commissions. This would be an option when, for example, the inventories at the physical stores were running low. Therefore, during the selling horizon, the retailer needs to dynamically control the opening/closing of affiliate programs and decide on the fulfillment option for online orders. On the basis of a discrete‐time dynamic programming model, the optimal admission policy of the retailer is investigated in this paper, and the structural properties of the revenue function are characterized. Numerical examples are given to show the revenue impact of optimal admission control. The optimal initial stocking decisions at the physical stores are also studied. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

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     

Dynamic routing of prioritized warranty repairs

Recent years have seen a strong trend toward outsourcing warranty repair services to outside vendors. In this article we consider the problem of dynamically routing warranty repairs to service vendors when warranties have priority levels. Each time an item under warranty fails, it is sent to one of the vendors for repair. Items covered by higher priority warranty receive higher priority in repair service. The manufacturer pays a fixed fee per repair and incurs a linear holding cost while an item is undergoing or waiting for repair. The objective is to minimize the manufacturer's long‐run average cost. Because of the complexity of the problem, it is very unlikely that there exist tractable ways to find the optimal routing strategies. Therefore, we propose five heuristic routing procedures that are applicable to real‐life problems. We evaluate the heuristics using simulation. The simulation results show that the index‐based “generalized join the shortest queue” policy, which applies a single policy improvement step to an initial state‐independent policy, performs the best among all five heuristics. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Technical note: An improved range chart for normal and long‐tailed symmetrical distributions

The distribution of the range of a sample, even in the case of a normal distribution, is not symmetric. Shewhart's control chart for range and other approximations for range from skewed distributions and long‐tailed (leptokurtic) symmetrical distributions assume the distribution of range as symmetric and provide 3 sigma control limits. We provide accurate approximations for the R‐chart control limits for the leptokurtic symmetrical distributions, using a range quantile approximation (RQA) method and illustrate the use of the RQA method with a numerical example. As special cases, we provide constants for the R‐chart for the normal, logistic, and Laplace distributions. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2008