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     

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     

Sojourn times in a two‐stage queueing network with blocking

The model considered in this paper involves a tandem queue consisting of a sequence of two waiting lines. The main feature of our model is blocking, i.e., as soon as the second waiting line reaches a certain upper limit, the first line is blocked. The input of units to the tandem queue is the MAP (Markovian arrival process), and service requirements are of phase type. Our objective is to study the sojourn time distribution under the first‐come‐first‐serve discipline by analyzing the sojourn time through times until absorption in appropriately defined quasi‐birth‐and‐death processes and continuous‐time Markov chains. © 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.     

On reversibility of tandem queues with blocking

We study the effect of the order of service stations on the departure process in a tandem system with finite buffers and blocking. A reversibility result for a twostation system with various types of blocking mechanisms has been shown before. We show that a similar result holds for a three-station tandem system with no buffers between stations and a so-called communication type of blocking. A general conjecture is stated regarding the reversibility of tandem systems with finite buffers and blocking. © 1992 John Wiley & Sons, Inc.     

A generalized assignment model for dynamic supply chain capacity planning

We consider a generalization of the well‐known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single‐period assignment costs and agent‐capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single‐period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation‐based heuristic as well as a branch‐and‐bound algorithm for MultiGAP. Computational experience with the heuristic and branch‐and‐bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high‐quality and in many cases near‐optimal solutions. The branch‐and‐bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

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 job splitting on a multi‐slot machine with applications in the printing industry

In this article, we define a scheduling/packing problem called the Job Splitting Problem, motivated by the practices in the printing industry. There are n types of items to be produced on an m‐slot machine. A particular assignment of the types to the slots is called a “run” configuration and requires a setup cost. Once a run begins, the production continues according to that configuration and the “length” of the run represents the quantity produced in each slot during that run. For each unit of production in excess of demand, there is a waste cost. Our goal is to construct a production plan, i.e., a set of runs, such that the total setup and waste cost is minimized. We show that the problem is strongly NP‐hard and propose two integer programming formulations, several preprocessing steps, and two heuristics. We also provide a worst‐case bound for one of the heuristics. Extensive tests on real‐world and randomly generated instances show that the heuristics are both fast and effective, finding near‐optimal solutions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Heuristics for the multi‐resource generalized assignment problem

The well‐known generalized assignment problem (GAP) involves the identification of a minimum‐cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi‐resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three‐phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pirkul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near‐optimal solutions. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 468–483, 2001     

Equitable bandwidth allocation in content distribution networks

Applications for content distribution over networks, such as Video‐on‐Demand (VOD), are expected to grow significantly over time. Effective bandwidth allocation schemes that can be repeatedly executed must be deployed since new programs are often installed at various servers while other are deleted. We present a model for bandwidth allocation in a content distribution network that consists of multiple trees, where the root of each tree has a server that broadcasts multiple programs throughout the tree. Each network link has limited capacity and may be used by one or more of these trees. The model is formulated as an equitable resource allocation problem with a lexicographic maximin objective function that attempts to provide equitable service performance for all requested programs at the various nodes. The constraints include link capacity constraints and tree‐like ordering constraints imposed on each of the programs. We present an algorithm that provides an equitable solution in polynomial time for certain performance functions. At each iteration, the algorithm solves single‐link maximin optimization problems while relaxing the ordering constraints. The algorithm selects a bottleneck link, fixes various variables at their lexicographic optimal solution while enforcing the ordering constraints, and proceeds with the next iteration. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Limiting behavior of the stochastic sequential assignment problem

The stochastic sequential assignment problem (SSAP) considers how to allocate available distinct workers to sequentially arriving tasks with stochastic parameters such that the expected total reward obtained from the sequential assignments is maximized. Implementing the optimal assignment policy for the SSAP involves calculating a new set of breakpoints upon the arrival of each task (i.e., for every time period), which is impractical for large‐scale problems. This article studies two problems that are concerned with obtaining stationary policies, which achieve the optimal expected reward per task as the number of tasks approaches infinity. The first problem considers independent and identically distributed (IID) tasks with a known distribution function, whereas in the second problem tasks are derived from r different unobservable distributions governed by an ergodic Markov chain. The convergence rate of the expected reward per task to the optimal value is also obtained for both problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Analysis of decentralized multi‐product pull systems with lost sales

We study a pull‐type, flexible, multi‐product, and multi‐stage production/inventory system with decentralized two‐card kanban control policies. Each stage involves a processor and two buffers with finite target levels. Production stages, arranged in series, can process several product types one at a time. Transportation of semi‐finished parts from one stage to another is performed in fixed lot sizes. The exact analysis is mathematically intractable even for smaller systems. We present a robust approximation algorithm to model two‐card kanban systems with batch transfers under arbitrary complexity. The algorithm uses phase‐type modeling to find effective processing times and busy period analysis to identify delays among product types in resource contention. Our algorithm reduces the effort required for estimating performance measures by a considerable margin and resolves the state–space explosion problem of analytical approaches. Using this analytical tool, we present new findings for a better understanding of some tactical and operational issues. We show that flow of material in small procurement sizes smoothes flow of information within the system, but also necessitates more frequent shipments between stages, raising the risk of late delivery. Balancing the risk of information delays vis‐à‐vis shipment delays is critical for the success of two‐card kanban systems. Although product variety causes time wasted in setup operations, it also facilitates relatively short production cycles enabling processors to switch from one product type to another more rapidly. The latter point is crucial especially in high‐demand environments. Increasing production line size prevents quick response to customer demand, but it may improve system performance if the vendor lead‐time is long or subject to high variation. Finally, variability in transportation and processing times causes the most damage if it arises at stages closer to the customer. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Allocating capacity in parallel queues to improve their resilience to deliberate attack

We develop models that lend insight into how to design systems that enjoy economies of scale in their operating costs, when those systems will subsequently face disruptions from accidents, acts of nature, or an intentional attack from a well‐informed attacker. The systems are modeled as parallel M/M/1 queues, and the key question is how to allocate service capacity among the queues to make the system resilient to worst‐case disruptions. We formulate this problem as a three‐level sequential game of perfect information between a defender and a hypothetical attacker. The optimal allocation of service capacity to queues depends on the type of attack one is facing. We distinguish between deterministic incremental attacks, where some, but not all, of the capacity of each attacked queue is knocked out, and zero‐one random‐outcome (ZORO) attacks, where the outcome is random and either all capacity at an attacked queue is knocked out or none is. There are differences in the way one should design systems in the face of incremental or ZORO attacks. For incremental attacks it is best to concentrate capacity. For ZORO attacks the optimal allocation is more complex, typically, but not always, involving spreading the service capacity out somewhat among the servers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Using stochastic programming to solve an outpatient appointment scheduling problem with random service and arrival times

We study a stochastic outpatient appointment scheduling problem (SOASP) in which we need to design a schedule and an adaptive rescheduling (i.e., resequencing or declining) policy for a set of patients. Each patient has a known type and associated probability distributions of random service duration and random arrival time. Finding a provably optimal solution to this problem requires solving a multistage stochastic mixed‐integer program (MSMIP) with a schedule optimization problem solved at each stage, determining the optimal rescheduling policy over the various random service durations and arrival times. In recognition that this MSMIP is intractable, we first consider a two‐stage model (TSM) that relaxes the nonanticipativity constraints of MSMIP and so yields a lower bound. Second, we derive a set of valid inequalities to strengthen and improve the solvability of the TSM formulation. Third, we obtain an upper bound for the MSMIP by solving the TSM under the feasible (and easily implementable) appointment order (AO) policy, which requires that patients are served in the order of their scheduled appointments, independent of their actual arrival times. Fourth, we propose a Monte Carlo approach to evaluate the relative gap between the MSMIP upper and lower bounds. Finally, in a series of numerical experiments, we show that these two bounds are very close in a wide range of SOASP instances, demonstrating the near‐optimality of the AO policy. We also identify parameter settings that result in a large gap in between these two bounds. Accordingly, we propose an alternative policy based on neighbor‐swapping. We demonstrate that this alternative policy leads to a much tighter upper bound and significantly shrinks the gap.     

Algorithms for computing waiting time distributions under different queue disciplines for the D-BMAP/PH/1

A queueing system characterized by the discrete batch Markovian arrival process (D-BMAP) and a probability of phase type distribution for the service time is one that arises frequently in the area of telecommunications. Under this arrival process and service time distribution we derive the waiting time distribution for three queue disciplines: first in first out (FIFO), last in first out (LIFO), and service in random order (SIRO). We also outline efficient algorithmic procedures for computing the waiting time distributions under each discipline. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 559–576, 1997     

Planning accelerated life tests for censored two‐parameter exponential distributions

We consider optimal test plans involving life distributions with failure‐free life, i.e., where there is an unknown threshold parameter below which no failure will occur. These distributions do not satisfy the regularity conditions and thus the usual approach of using the Fisher information matrix to obtain an optimal accelerated life testing (ALT) plan cannot be applied. In this paper, we assume that lifetime follows a two‐parameter exponential distribution and the stress‐life relationship is given by the inverse power law model. Near‐optimal test plans for constant‐stress ALT under both failure‐censoring and time‐censoring are obtained. We first obtain unbiased estimates for the parameters and give the approximate variance of these estimates for both failure‐censored and time‐censored data. Using these results, the variance for the approximate unbiased estimate of a percentile at a design stress is computed and then minimized to produce the near‐optimal plan. Finally, a numerical example is presented together with simulation results to study the accuracy of the approximate variance given by the proposed plan and show that it outperforms the equal‐allocation plan. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 169–186, 1999     

Facility location models for immobile servers with stochastic demand

This paper presents several models for the location of facilities subject to congestion. Motivated by applications to locating servers in communication networks and automatic teller machines in bank systems, these models are developed for situations in which immobile service facilities are congested by stochastic demand originating from nearby customer locations. We consider this problem from three different perspectives, that of (i) the service provider (wishing to limit costs of setup and operating servers), (ii) the customers (wishing to limit costs of accessing and waiting for service), and (iii) both the service provider and the customers combined. In all cases, a minimum level of service quality is ensured by imposing an upper bound on the server utilization rate at a service facility. The latter two perspectives also incorporate queueing delay costs as part of the objective. Some cases are amenable to an optimal solution. For those cases that are more challenging, we either propose heuristic procedures to find good solutions or establish equivalence to other well‐studied facility location problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Generation and storage dispatch in electricity networks with generator disruptions

We present methods for optimizing generation and storage decisions in an electricity network with multiple unreliable generators, each colocated with one energy storage unit (e.g., battery), and multiple loads under power flow constraints. Our model chooses the amount of energy produced by each generator and the amount of energy stored in each battery in every time period in order to minimize power generation and storage costs when each generator faces stochastic Markovian supply disruptions. This problem cannot be optimized easily using stochastic programming and/or dynamic programming approaches. Therefore, in this study, we present several heuristic methods to find an approximate optimal solution for this system. Each heuristic involves decomposing the network into several single‐generator, single‐battery, multiload systems and solving them optimally using dynamic programming, then obtaining a solution for the original problem by recombining. We discuss the computational performance of the proposed heuristics as well as insights gained from the models. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 493–511, 2015     

The effect of catastrophes on the strategic customer behavior in queueing systems

We consider the single server Markovian queue subject to Poisson generated catastrophes. Whenever a catastrophe occurs, all customers are forced to abandon the system, the server is rendered inoperative and an exponential repair time is set on. During the repair time new arrivals are allowed to join the system. We assume that the arriving customers decide whether to join the system or balk, based on a natural linear reward‐cost structure with two types of rewards: A (usual) service reward for those customers that receive service and a (compensation) failure reward for those customers that are forced to abandon the system due to a catastrophe. We study the strategic behavior of the customers regarding balking and derive the corresponding (Nash) equilibrium strategies for the observable and unobservable cases. We show that both types of strategic behavior may be optimal: to avoid the crowd or to follow it. The crucial factor that determines the type of customer behavior is the relative value of the service reward to the failure compensation. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013