Queueing networks featuring fork/join stations are natural models for a variety of computer and manufacturing systems. Unfortunately, an exact solution for a Markovian fork/join network can only be obtained by analyzing the underlying Markov chain using numerical methods, and these methods are computationally feasible only for networks with small population sizes and numbers of service stations. In this paper we present a new, simple, and accurate analytical approximation method to estimate the throughput (and other performance metrics) of a closed queueing network that features a single fork/join station receiving inputs from general subnetworks. An extensive numerical study illustrates the high accuracy of our proposed technique, especially for networks with large populations and numbers of stations. It also shows that the accuracy of our approximation method improves with increasing population size, deteriorating network balance, and increasing number of stations when the added stations weaken the network balance. Furthermore, our method has significant computational advantages compared to simulation and existing approximation techniques, the latter of which are in general less accurate than ours and in many cases even fail to provide a solution in our numerical study. We also bound analytically the relative error of our method for a broad class of networks, which provides theoretical support for some of our numerical observations. The online appendix is available at https://doi.org/10.1287/ijoc.2016.0727 .

Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to replicate a request so that it joins the queue at multiple servers. The request is considered complete as soon as any one of its copies completes. Redundancy allows us to overcome serverside variability-the fact that a server might be temporarily slow due to factors such as background load, network interrupts, and garbage collection to reduce response time. In the past few years, queueing theorists have begun to study redundancy, first via approximations, and, more recently, via exact analysis. Unfortunately, for analytical tractability, most existing theoretical analysis has assumed an Independent Runtimes (IR) model, wherein the replicas of a job each experience independent runtimes (service times) at different servers. The IR model is unrealistic and has led to theoretical results that can be at odds with computer systems implementation results. This paper introduces a much more realistic model of redundancy. Our model decouples the inherent job size (X) from the serverside slowdown (S), where we track both S and X for each job. Analysis within the S&X model is, of course, much more difficult. Nevertheless, we design a dispatching policy, Redundant-to-Idle-Queue, which is both analytically tractable within the S&X model and has provably excellent performance.

Recent computer systems research has proposed using redundant requests to reduce latency. The idea is to replicate a request so that it joins the queue at multiple servers. The request is considered complete as soon as any one copy of the request completes. Redundancy is beneficial because it allows us to overcome server-side variability - the fact that the server we choose might be temporarily slow due to factors such as background load, network interrupts, and garbage collection. When there is significant server-side variability, replicating requests can greatly reduce response times. In the past few years, queueing theorists have begun to study redundancy, first via approximations, and, more recently, via exact analysis. Unfortunately, for analytical tractability, most existing theoretical analysis has assumed an Independent Runtimes (IR) model, wherein the replicas of a job each experience independent runtimes (service times) at different servers. The IR model is unrealistic and has led to theoretical results which can be at odds with computer systems implementation results. This paper introduces a much more realistic model of redundancy. Our model allows us to decouple the inherent job size (X) from the server-side slowdown (S), where we track both S and X for each job. Analysis within the S&X model is, of course, much more difficult. Nevertheless, we design a policy, Redundant-to-Idle-Queue (RIQ) which is both analytically tractable within the S&X model and has provably excellent performance.

An increasingly prevalent technique for improving response time in queueing systems is the use of redundancy. In a system with redundant requests, each job that arrives to the system is copied and dispatched to multiple servers. As soon as the first copy completes service, the job is considered complete, and all remaining copies are deleted. A great deal of empirical work has demonstrated that redundancy can significantly reduce response time in systems ranging from Google's BigTable service to kidney transplant waitlists. We propose a theoretical model of redundancy, the Redundancy-d system, in which each job sends redundant copies to d servers chosen uniformly at random. We derive the first exact expressions for mean response time in Redundancy-d systems with any finite number of servers. We also find asymptotically exact expressions for the distribution of response time as the number of servers approaches infinity.

Using a novel stochastic programming (SP) formulation, we develop an algorithm for inventory control in industrial-size assemble-to-order (ATO) systems that has unparalleled efficiency and scalability. Applying our algorithm to several numerical examples, we generate new insights regarding the control and optimization of these systems. We consider a continuous time model, seeking base-stock levels for components that minimize the sum of holding costs and product-specific backorder costs. Our initial focus is on first-come, first-served (FCFS) allocation of components to products; for this setting our algorithm quickly computes solutions for which the asymptotic optimality gap with the optimal FCFS base-stock policy is less than 1%. We then turn to two related questions: How do common heuristics used in practice compare to our performance, and how costly is the FCFS assumption? For the first question, we investigate the effectiveness of ignoring simultaneous stock-outs (ISS), a heuristic that has been used by companies such as IBM and Dell. Our experiments indicate that ISS performance, when compared to the optimal FCFS base-stock policy, improves as the average newsvendor (NV) fractiles increase but suffers under lead-time demand correlations. For the second question, we develop an efficiently computable upper bound on the benefit of optimal allocation over FCFS. We find that for many large ATO systems, FCFS performs surprisingly well and that its performance improves with decreasing NV fractile asymmetry among products and, again, with increasing average NV fractiles. We also investigate simple no-holdback allocation policies and find that they tend to outperform the best FCFS policies.

The M/M/k/setup model, where there is a penalty for turning servers on, is common in data centers, call centers and manufacturing systems. Setup costs take the form of a time delay, and sometimes there is additionally a power penalty, as in the case of data centers. While the M/M/1/setup was exactly analyzed in 1964, no exact analysis exists to date for the M/M/k/setup with k>1. In this paper we provide the first exact, closed-form analysis for the M/M/k/setup and some of its important variants including systems in which idle servers delay for a period of time before turning off or can be put to sleep. Our analysis is made possible by our development of a new technique, Recursive Renewal Reward (RRR), for solving Markov chains with a repeating structure. RRR uses ideas from renewal reward theory and busy period analysis to obtain closed-form expressions for metrics of interest such as the transform of time in system and the transform of power consumed by the system. The simplicity, intuitiveness, and versatility of RRR makes it useful for analyzing Markov chains far beyond the M/M/k/setup. In general, RRR should be used to reduce the analysis of any 2-dimensional Markov chain which is infinite in at most one dimension and repeating to the problem of solving a system of polynomial equations. In the case where all transitions in the repeating portion of the Markov chain are skip-free and all up/down arrows are unidirectional, the resulting system of equations will yield a closed-form solution.

We consider the problem of task assignment in a distributed server system, where short jobs are separated from long jobs, but short jobs may be run in the long job partition if it is idle (cycle stealing). Jobs are assumed to be nonpreemptible, where short and long jobs have generally distributed service requirements, and arrivals are Poisson. We consider two variants of this problem: a central queue model and an immediate dispatch model. This paper presents the first analysis of cycle stealing under the central-queue model. (Cycle stealing under the immediate dispatch model is analyzed in [9]). The analysis uses a technique which we refer to as busy period transitions. Results show that cycle stealing can reduce mean response time for short jobs by orders of magnitude, while long jobs are only slightly penalized. Furthermore using a central queue yields significant performance improvement over immediate dispatch, both from the perspective of the benefit to short jobs and the penalty to long jobs.

We consider the scenario of two processors, each serving its own workload, where one of the processors (known as the "donor") can help the other processor (known as the "beneficiary") with its jobs, during times when the donor processor is idle. That is the beneficiary processor "steals idle cycles" from the donor processor. We assume that both donor jobs and beneficiary jobs may have generally-distributed service requirements. We assume that there is a switching cost required for the donor processor to start working on the beneficiary jobs, as well as a switching cost required for the donor processor to return to working on its own jobs. We also allow for threshold constraints, whereby the donor processor only initiates helping the beneficiary if both the donor is idle and the number of jobs at the beneficiary exceeds a certain threshold.We analyze the mean response time for the donor and beneficiary processors. Our analysis is approximate, but can be made as accurate as desired, and is validated via simulation. Results of the analysis illuminate several interesting principles with respect to the general benefits of cycle stealing and the design of cycle stealing policies.

We consider the practical problem of task assignment in a server farm, where each arriving job is immediately dispatched to a server in the farm. We look at the benefit of cycle stealing at the point of the dispatcher, where jobs normally destined for one machine may be routed to a different machine if it is idle. The analysis uses a technique which we refer to as dimensionality reduction via busy period transitions. Our analysis is approximate, but can be made as close to exact as desired, and is validated via simulation. Results show that the beneficiaries of the idle cycles can benefit unboundedly, due to an increase in their stability region, while the donors are only slightly penalized. These results still hold even when there is only one donor server and 20 beneficiary servers stealing its idle cycles.

We envision a future economy where e–markets will play an essential role as exchange hubs for commodities and services. Future e–markets should be designed to be robust to manipulation, flexible, and sufficiently efficient in facilitating exchanges. One of the most important aspects of designing an e–market is market mechanism design. A market mechanism defines the organization, information exchange process, trading procedure, and clearance rules of a market. If we view an e–market as a multi–agent system, the market mechanism also defines the structure and rules of the environment in which agents (buyers and sellers) play the market game. We design an e–market mechanism that is strategy–proof with respect to reservation price, weakly budget–balanced, and individually rational. Our mechanism also makes sellers unlikely to underreport the supply volume to drive up the market price. In addition, by bounding our market’s efficiency loss, we provide fairly unrestrictive sufficient conditions for the efficiency of our mechanism to converge in a strong sense when (1) the number of agents who successfully trade is large, or (2) the number of agents, trading and not, is large. We implement our design using the RETSINA infrastructure, a multi–agent system development toolkit. This enables us to validate our analytically derived bounds by numerically testing our e–market.