Return policy: Hassle‐free or your money‐back guarantee?

This article compares the profitability of two pervasively adopted return policies—money‐back guarantee and hassle‐free policies. In our model, a seller sells to consumers with heterogeneous valuations and hassle costs. Products are subject to quality risk, and product misfit can only be observed post‐purchase. While the hassle‐free policy is cost advantageous from the seller's viewpoint, a money‐back guarantee allows the seller to fine‐tune the consumer hassle on returning the product. Thus, when the two return policies lead to the same consumer behaviors, the hassle‐free policy dominates. Conversely, a money‐back guarantee can be more profitable even if on average, high‐valuation consumers experience a lower hassle cost than the low‐valuation ones. The optimal hassle cost can be higher when product quality gets improved; thus, it is not necessarily a perfect proxy or signal of the seller's quality. We further allow the seller to adopt a mixture of these policies, and identify the concrete operating regimes within which these return policies are optimal among more flexible policies. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 403–417, 2014     

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     

Dynamic server assignment policies for assembly‐type queues with flexible servers

We seek dynamic server assignment policies in finite‐capacity queueing systems with flexible and collaborative servers, which involve an assembly and/or a disassembly operation. The objective is to maximize the steady‐state throughput. We completely characterize the optimal policy for a Markovian system with two servers, two feeder stations, and instantaneous assembly and disassembly operations. This optimal policy allocates one server per station unless one of the stations is blocked, in which case both servers work at the unblocked station. For Markovian systems with three stations and instantaneous assembly and/or disassembly operations, we consider similar policies that move a server away from his/her “primary” station only when that station is blocked or starving. We determine the optimal assignment of each server whose primary station is blocked or starving in systems with three stations and zero buffers, by formulating the problem as a Markov decision process. Using this optimal assignment, we develop heuristic policies for systems with three or more stations and positive buffers, and show by means of a numerical study that these policies provide near‐optimal throughput. Furthermore, our numerical study shows that these policies developed for assembly‐type systems also work well in tandem systems. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Asymptotic analysis of periodic policies for the inventory routing problem

In this article, a distribution system is studied where the sum of transportation and inventory costs is to be minimized. The inventory holding cost is assumed to be the same for all retailers. A fixed partition (FP) periodic policy is proposed with tight asymptotic worst‐case performance of 3/2 with respect to the best possible policy. This bound cannot be improved in the class of FP periodic policies. In partition‐based PB policies, the retailers are first partitioned into sets and then the sets are grouped in such a way that sets of retailers within a group are served together at selected times. A PB periodic, policy is presented with tight worst‐case asymptotic performance of with respect to the best possible policy. This latter performance improves the worst‐case asymptotic performance of of the previously best known policy for this problem. We also show that the proposed PB periodic policy has the best worst‐case asymptotic performance within the class of PB policies. Finally, practical heuristics inspired by the analyzed policies are designed and tested. The asymptotic worst–case performances of the heuristics are shown to be the same of those of the analyzed policies. Computational results show that the heuristics suggested are less than 6.4% on average from a lower bound on the optimal cost when 50 or more retailers are involved. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 00: 000–000, 2013     

The single and multi‐item transshipment problem with fixed transshipment costs

This article deals with supply chain systems in which lateral transshipments are allowed. For a system with two retailers facing stochastic demand, we relax the assumption of negligible fixed transshipment costs, thus, extending existing results for the single‐item case and introducing a new model with multiple items. The goal is to determine optimal transshipment and replenishment policies, such that the total centralized expected profit of both retailers is maximized. For the single‐item problem with fixed transshipment costs, we develop optimality conditions, analyze the expected profit function, and identify the optimal solution. We extend our analysis to multiple items with joint fixed transshipment costs, a problem that has not been investigated previously in the literature, and show how the optimality conditions may be extended for any number of items. Due to the complexity involved in solving these conditions, we suggest a simple heuristic based on the single‐item results. Finally, we conduct a numerical study that provides managerial insights on the solutions obtained in various settings and demonstrates that the suggested heuristic performs very well. © 2014 Wiley Periodicals, Inc. Naval Research Logistics, 61: 637–664, 2014     

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     

Optimal and asymptotically optimal policies for assemble‐to‐order n‐ and W‐systems

We consider two specially structured assemble‐to‐order (ATO) systems—the N‐ and W‐systems—under continuous review, stochastic demand, and nonidentical component replenishment leadtimes. Using a hybrid approach that combines sample‐path analysis, linear programming, and the tower property of conditional expectation, we characterize the optimal component replenishment policy and common‐component allocation rule, present comparative statics of the optimal policy parameters, and show that some commonly used heuristic policies can lead to significant optimality loss. The optimality results require certain symmetry in the cost parameters. In the absence of this symmetry, we show that, for systems with high demand volume, the asymptotically optimal policy has essentially the same structure; otherwise, the optimal policies have no clear structure. For these latter systems, we develop heuristic policies and show their effectiveness. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 62: 617–645, 2015     

Maintenance scheduling for modular systems: Modeling and algorithms

We study new models of scheduled maintenance management for modular systems, consisting of multiple components with respective cycle limits. The cycle limit of each component specifies the time interval in which this component must be repaired or replaced. The goal is to compute a feasible maintenance schedule that minimizes the cost associated with component maintenance. Applications of these models arise in Air Force aircraft maintenance as well as in other arenas with required preventive maintenance. The typical cost structures that arise in practical settings are submodular, which make the resulting models computationally challenging. We develop two efficient and operationally tenable approximation algorithms. We prove constant factor worst‐case guarantees for both algorithms, and present computational experiments showing that these algorithms perform within a few percent of optimality on operationally relevant instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 472–488, 2014     

Analysis of practical policies for a single link distribution system

In this paper we consider a transportation problem where several products have to be shipped from an origin to a destination by means of vehicles with given capacity. Each product is made available at the origin and consumed at the destination at the same constant rate. The time between consecutive shipments must be greater than a given minimum time. All demand needs to be satisfied on time and backlogging is not allowed. The problem is to decide when to make the shipments and how to load the vehicles with the objective of minimizing the long run average of the transportation and the inventory costs at the origin and at the destination over an infinite horizon. We consider two classes of practical shipping policies, the zero inventory ordering (ZIO) policies and the frequency‐based periodic shipping (FBPS) policies. We show that, in the worst‐case, the Best ZIO policy has a performance ratio of . A better performance guarantee of is shown for the best possible FBPS policy. The performance guarantees are tight. Finally, combining the Best ZIO and the Best FBPS policies, a policy that guarantees a performance is obtained. Computational results show that this policy gives an average percent optimality gap on all the tested instances of <1%. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Bin‐packing problem with concave costs of bin utilization

We consider a generalized one‐dimensional bin‐packing model where the cost of a bin is a nondecreasing concave function of the utilization of the bin. Four popular heuristics from the literature of the classical bin‐packing problem are studied: First Fit (FF), Best Fit (BF), First Fit Decreasing (FFD), and Best Fit Decreasing (BFD). We analyze their worst‐case performances when they are applied to our model. The absolute worst‐case performance ratio of FF and BF is shown to be exactly 2, and that of FFD and BFD is shown to be exactly 1.5. Computational experiments are also conducted to test the performance of these heuristics. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Improved bounds for batch scheduling with nonidentical job sizes

Here, we revisit the bounded batch scheduling problem with nonidentical job sizes on single and parallel identical machines, with the objective of minimizing the makespan. For the single machine case, we present an algorithm which calls an online algorithm (chosen arbitrarily) for the one‐dimensional bin‐packing problem as a sub‐procedure, and prove that its worst‐case ratio is the same as the absolute performance ratio of . Hence, there exists an algorithm with worst‐case ratio , which is better than any known upper bound on this problem. For the parallel machines case, we prove that there does not exist any polynomial‐time algorithm with worst‐case ratio smaller than 2 unless P = NP, even if all jobs have unit processing time. Then we present an algorithm with worst‐case ratio arbitrarily close to 2. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 351–358, 2014     

A robust policy for serial agile production systems

One of the major problems in modeling production systems is how to treat the job arrival process. Restrictive assumptions such as Markovian arrivals do not represent real world systems, especially if the arrival process is generated by job departures from upstream workstations. Under these circumstances, cost‐effective policies that are robust with respect to the nature of the arrival process become of interest. In this paper, we focus on minimizing the expected total holding and setup costs in a two‐stage produce‐to‐order production system operated by a cross‐trained worker. We will show that if setup times are insignificant in comparison with processing times, then near‐optimal policies can be generated with very robust performances with respect to the arrival process. We also present conditions under which these near‐optimal policies can be obtained by using only the arrival and service rates. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

The stochastic single resource service‐provision problem

The service‐provision problem described in this paper comes from an application of distributed processing in telecommunications networks. The objective is to maximize a service provider's profit from offering computational‐based services to customers. The service provider has limited capacity and must choose which of a set of software applications he would like to offer. This can be done dynamically, taking into consideration that demand for the different services is uncertain. The problem is examined in the framework of stochastic integer programming. Approximations and complexity are examined for the case when demand is described by a discrete probability distribution. For the deterministic counterpart, a fully polynomial approximation scheme is known 2 . We show that introduction of stochasticity makes the problem strongly NP‐hard, implying that the existence of such a scheme for the stochastic problem is highly unlikely. For the general case a heuristic with a worst‐case performance ratio that increases in the number of scenarios is presented. Restricting the class of problem instances in a way that many reasonable practical problem instances satisfy allows for the derivation of a heuristic with a constant worst‐case performance ratio. Worst‐case performance analysis of approximation algorithms is classical in the field of combinatorial optimization, but in stochastic programming the authors are not aware of any previous results in this direction. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

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     

Technical note: Reexamination of all‐or‐none inspection policies in a supply chain with endogenous product quality

This note studies the optimal inspection policies in a supply chain in which a manufacturer purchases components from a supplier but has no direct control of component quality. The manufacturer uses an inspection policy and a damage cost sharing contract to encourage the supplier to improve the component quality. We find that all‐or‐none inspection policies are optimal for the manufacturer if the supplier's share of the damage cost is larger than a threshold; otherwise, the manufacturer should inspect a fraction of a batch. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Dynamic inventory control with limited capital and short‐term financing

For most firms, especially the small‐ and medium‐sized ones, the operational decisions are affected by their internal capital and ability to obtain external capital. However, the majority of the literature on dynamic inventory control ignores the firm's financial status and financing issues. An important question that arises is: what are the optimal inventory and financing policies for firms with limited internal capital and limited access to external capital? In this article, we study a dynamic inventory control problem where a capital‐constrained firm periodically purchases a product from a supplier and sells it to a market with random demands. In each period, the firm can use its own capital and/or borrow a short‐term loan to purchase the product, with the interest rate being nondecreasing in the loan size. The objective is to maximize the firm's expected terminal wealth at the end of the planning horizon. We show that the optimal inventory policy in each period is an equity‐level‐dependent base‐stock policy, where the equity level is the sum of the firm's capital level and the value of its on‐hand inventory evaluated at the purchasing cost; and the structure of the optimal policy can be characterized by four intervals of the equity level. Our results shed light on the dynamic inventory control for firms with limited capital and short‐term financing capabilities.Copyright © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 184–201, 2014     

Analysis of algorithms for two‐stage flowshops with multi‐processor task flexibility

In this article we introduce a 2‐machine flowshop with processing flexibility. Two processing modes are available for each task: namely, processing by the designated processor, and processing simultaneously by both processors. The objective studied is makespan minimization. This production environment is encountered in repetitive manufacturing shops equipped with processors that have the flexibility to execute orders either individually or in coordination. In the latter case, the product designer exploits processing synergies between two processors so as to execute a particular task much faster than a dedicated processor. This type of flowshop environment is also encountered in labor‐intensive assembly lines where products moving downstream can be processed either in the designated assembly stations or by pulling together the work teams of adjacent stations. This scheduling problem requires determining the mode of operation of each task, and the subsequent scheduling that preserves the flowshop constraints. We show that the problem is ordinary NP‐complete and obtain an optimal solution using a dynamic programming algorithm with considerable computational requirements for medium and large problems. Then, we present a number of dynamic programming relaxations and analyze their worst‐case error performance. Finally, we present a polynomial time heuristic with worst‐case error performance comparable to that of the dynamic programming relaxations. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Inventory control and replenishment with flexible delivery‐time upgrade

We consider a capacitated inventory model with flexible delivery upgrades, in which the seller allocates its on‐hand inventory to price‐ and delivery‐time‐sensitive customers. The seller has two decisions: inventory commitment and replenishment. The former addresses how the on‐hand inventories are allocated between the two classes of customers within an inventory cycle. The latter addresses how the inventory is replenished between inventory cycles. We develop optimal inventory allocation, upgrade, and replenishment policies and demonstrate that the optimal policy can be characterized by a set of switching curves. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 418–426, 2014     

Exponential size neighborhoods for makespan minimization scheduling

We investigate the quality of local search heuristics for the scheduling problem of minimizing the makespan on identical parallel machines. We study exponential size neighborhoods (whose size grows exponentially with the input length) that can be searched in polynomial time, and we derive worst‐case approximation guarantees for the local optima of such neighborhoods. The so‐called split neighborhood splits a feasible schedule into two layers, and then recombines the two layers by finding a perfect matching. We show that the makespan of every local optimum for split is at most a factor of 2 away from the globally optimal makespan. We then combine the split neighborhood with two neighborhoods from the literature. The combination of split with the jump neighborhood only marginally improves the approximation guarantee, whereas the combination with the lexicographic‐jump neighborhood decreases the approximation guarantee from 2 to 3/2. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

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