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     

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     

Analysis of a production system in a general configuration

We consider a production system comprising multiple stations (or workshops) such as an entry station, a set of work stations, a central station, and an exit station, which are arranged in a general configuration. A worker (or a vehicle tool) is assigned to each station, who sends a part from the station to the destination station according to the required process path of the part. Any part is allowed to visit a work station more than once if its process path requires. We propose a new control strategy with the push policy for instructing each worker to send a part and the kanban mechanism for controlling the work‐in‐process (WIP) in each work station. As all work stations have limited local buffers, the central station is used for storing blocked parts temporarily. Such a production system is modeled as an open queueing network in a general configuration with a Markovian part sending policy and a machine no blocking mechanism. The queueing network is analytically characterized. Some important performance measures are compared with other control strategies. A semi‐open decomposition approach is applied to the queueing network for computing the blocking probabilities when parts arrive at the work stations. An algorithm is developed based on the semi‐open decomposition approach. Numerical experiments show the quality of the solutions obtained by the algorithm as well as a property of a performance measure. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 128–143, 2001     

Modeling and analysis of flexible queueing systems

We consider queueing systems with multiple classes of customers and heterogeneous servers where customers have the flexibility of being processed by more than one server and servers possess the capability of processing more than one customer class. We provide a unified framework for the modeling and analysis of these systems under arbitrary customer and server flexibility and for a rich set of control policies that includes customer/server‐specific priority schemes for server and customer selection. We use our models to generate several insights into the effect of system configuration and control policies. In particular, we examine the relationship between flexibility, control policies and throughput under varying assumptions for system parameters. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

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.     

Revenue maximization in two-station tandem queueing systems

We study optimal pricing for tandem queueing systems with finite buffers. The service provider dynamically quotes prices to incoming price sensitive customers to maximize the long-run average revenue. We present a Markov decision process model for the optimization problem. For systems with two stations, general-sized buffers, and two or more prices, we describe the structure of the optimal dynamic pricing policy and develop tailored policy iteration algorithms to find an optimal pricing policy. For systems with two stations but no intermediate buffer, we characterize conditions under which quoting either a high or a low price to all customers is optimal and provide an easy-to-implement algorithm to solve the problem. Numerical experiments are conducted to compare the developed algorithms with the regular policy iteration algorithm. The work also discusses possible extensions of the obtained results to both three-station systems and two-station systems with price and congestion sensitive customers using numerical analysis.     

Optimal policies for M/M/m queue with two different kinds of (N,T)‐policies

In this paper, two different kinds of (N, T)‐policies for an M/M/m queueing system are studied. The system operates only intermittently and is shut down when no customers are present any more. A fixed setup cost of K > 0 is incurred each time the system is reopened. Also, a holding cost of h > 0 per unit time is incurred for each customer present. The two (N, T)‐policies studied for this queueing system with cost structures are as follows: (1) The system is reactivated as soon as N customers are present or the waiting time of the leading customer reaches a predefined time T, and (2) the system is reactivated as soon as N customers are present or the time units after the end of the last busy period reaches a predefined time T. The equations satisfied by the optimal policy (N*, T*) for minimizing the long‐run average cost per unit time in both cases are obtained. Particularly, we obtain the explicit optimal joint policy (N*, T*) and optimal objective value for the case of a single server, the explicit optimal policy N* and optimal objective value for the case of multiple servers when only predefined customers number N is measured, and the explicit optimal policy T* and optimal objective value for the case of multiple servers when only predefined time units T is measured, respectively. These results partly extend (1) the classic N or T policy to a more practical (N, T)‐policy and (2) the conclusions obtained for single server system to a system consisting of m (m ≥ 1) servers. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 240–258, 2000     

Quantifying the performance effects of idle time utilization in multiserver systems

In many practical multiserver queueing systems, servers not only serve randomly arriving customers but also work on the secondary jobs with infinite backlog during their idle time. In this paper, we propose a c‐server model with a two‐threshold policy, denoted by (e d), to evaluate the performance of this class of systems. With such a policy, when the number of idle servers has reached d (<c), then e (<d) idle agents will process secondary jobs. These e servers keep working on the secondary jobs until they find waiting customers exist in the system at a secondary job completion instant. Using the matrix analytic method, we obtain the stationary performance measures for evaluating different (e, d) policies. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Optimal maintenance policies for serial,multi‐machine systems with non‐instantaneous repairs

We study optimal age‐replacement policies for machines in series with non‐instantaneous repair times by formulating two nonlinear programs: one that minimizes total cost‐rate subject to a steady‐state throughput requirement and another that maximizes steady‐state throughput subject to a cost‐rate budget constraint. Under reasonable assumptions, the single‐machine cost‐optimal and throughput‐optimal solutions are unique and orderable, and the multi‐machine optimal solutions have appealing structure. Furthermore, we establish equivalence between the two formulations and provide an illustrative numerical example. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Design and control of agile automated CONWIP production lines

In this article, we study the design and control of manufacturing cells with a mix of manual and automated equipment, operating under a CONWIP pull protocol, and staffed by a single agile (cross‐trained) worker. For a three‐station line with one automated station, we fully characterize the structure of the optimal control policy for the worker and show that it is a static priority policy. Using analytical models and extensive simulation experiments, we also evaluate the effectiveness of practical heuristic control policies and provide managerial insights on automation configuration design of the line. This characterization of the worker control policy enables us to develop managerial insights into the design issues of how best to locate and concentrate automation in the line. Finally, we show that, in addition to ease of control and greater design flexibility, the CONWIP protocol also offers higher efficiency and robustness than does the push protocol. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

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 control policies in service systems with limited information on the downstream stage

Existing models in multistage service systems assume full information on the state of downstream stages. In this paper, we investigate how much the lack of such information impacts jobs' waiting time in a two‐stage system with two types of jobs at the first stage. The goal is to find the optimal control policy for the server at the first stage to switch between type‐1 and type‐2 jobs, while minimizing the long‐run average number of jobs in the system. We identify control policies and corresponding conditions under which having no or partial information, the system can still capture the most benefit of having full information.     

Analysis of production lines with Coxian service times and no intermediate buffers

This paper uses the holding time model (HTM) method to derive an approximate analytic formula for the calculation of the mean throughput of a K-station production line with no buffers between any two successive stations. Service times follow the two-stage Coxian (C²) distribution at all stations. The paper provides a formula that relates the third moment of the service completion (or virtual service) time with the respective parameters of the service time, the repair time and the time to breakdown (the latter is assumed to follow the exponential distribution). In this way, it concludes that under certain conditions the two-stage Coxian distribution can be used to approximate any general distribution matching the first three moments of the service completion time distribution. The mean holding times (consisting of the service and blocking periods) of all stations of the line are obtained in an analytical form. Numerical results are provided for the mean throughput of lines with up to 20 stations. These results are shown to have a good accuracy compared against results obtained from the Markovian state method (for short lines) and results from simulation (for longer lines). © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 669–685, 1998     

Optimal policies for stochastic clearing systems with time-dependent delay penalties

We study stochastic clearing systems with a discrete-time Markovian input process, and an output mechanism that intermittently and instantaneously clears the system partially or completely. The decision to clear the system depends on both quantities and delays of outstanding inputs. Clearing the system incurs a fixed cost, and outstanding inputs are charged a delay penalty, which is a general increasing function of the quantities and delays of individual inputs. By recording the quantities and delays of outstanding inputs in a sequence, we model the clearing system as a tree-structured Markov decision process over both a finite and infinite horizon. We show that the optimal clearing policies, under realistic conditions, are of the on-off type or the threshold type. Based on the characterization of the optimal policies, we develop efficient algorithms to compute parameters of the optimal policies for such complex clearing systems for the first time. We conduct a numerical analysis on the impact of the nonlinear delay penalty cost function, the comparison of the optimal policy and the classical hybrid policy (ie, quantity and age thresholds), and the impact of the state of the input process. Our experiments demonstrate that (a) the classical linear approximation of the cost function can lead to significant performance differences; (b) the classical hybrid policy may perform poorly (as compared to the optimal policies); and (c) the consideration of the state of the input process makes significant improvement in system performance.     

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     

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     

Base‐stock policies in capacitated assembly systems: Convexity properties

We study an assembly system with a single finished product managed using an echelon base‐stock or order‐up‐to policy. Some or all operations have capacity constraints. Excess demand is either backordered in every period or lost in every period. We show that the shortage penalty cost over any horizon is jointly convex with respect to the base‐stock levels and capacity levels. When the holding costs are also included in the objective function, we show that the cost function can be written as a sum of a convex function and a concave function. Throughout the article, we discuss algorithmic implications of our results for making optimal inventory and capacity decisions in such systems.© 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Approximation algorithms for capacitated stochastic inventory systems with setup costs

We develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014     

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     

Dynamic inventory management with cash flow constraints

In this article, we consider a classic dynamic inventory control problem of a self‐financing retailer who periodically replenishes its stock from a supplier and sells it to the market. The replenishment decisions of the retailer are constrained by cash flow, which is updated periodically following purchasing and sales in each period. Excess demand in each period is lost when insufficient inventory is in stock. The retailer's objective is to maximize its expected terminal wealth at the end of the planning horizon. We characterize the optimal inventory control policy and present a simple algorithm for computing the optimal policies for each period. Conditions are identified under which the optimal control policies are identical across periods. We also present comparative statics results on the optimal control policy. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008