This note corrects an error in the formula to obtain the Whittle index using the Sherman–Morrison formula in Akbarzadeh and Mahajan (2022). Also, some other minor typos are highlighted.

Restless bandits are a class of sequential resource allocation problems concerned with allocating one or more resources among several alternative processes where the evolution of the processes depends on the resources allocated to them. Such models capture the fundamental trade-offs between exploration and exploitation. In 1988, Whittle developed an index heuristic for restless bandit problems which has emerged as a popular solution approach because of its simplicity and strong empirical performance. The Whittle index heuristic is applicable if the model satisfies a technical condition known as indexability. In this paper, we present two general sufficient conditions for indexability and identify simpler-to-verify refinements of these conditions. We then revisit a previously proposed algorithm called the adaptive greedy algorithm which is known to compute the Whittle index for a sub-class of restless bandits. We show that a generalization of the adaptive greedy algorithm computes the Whittle index for all indexable restless bandits. We present an efficient implementation of this algorithm which can compute the Whittle index of a restless bandit with K states in $\mathcal{O}\!\left(K^3\right)$ computations. Finally, we present a detailed numerical study which affirms the strong performance of the Whittle index heuristic.

We study the dynamic assignment of cross-trained workers in serial production lines characterized by stochastic process times and inventory buffers between stations. Throughput maximization is the objective. Each worker is trained for a subset of tasks, where emphasis is placed on systems with each worker trained for a zone of stations with stations near the zone boundaries being served (shared) by one or more other workers as well. Using sample path comparisons, we identify structural properties of optimal worker allocation policies. We identify when (i) a worker can prioritize the job in the most downstream station (last-buffer-first-served), and (ii) only the downstream (as opposed to upstream) server should serve a single task.

Parallel processing is a way to use resources efficiently by processing several jobs simultaneously on different servers. In a well-controlled environment where the status of the servers and the jobs are well known, everything is nearly deterministic and replicating jobs on different servers is obviously a waste of resources. However, in a poorly controlled environment where the servers are unreliable and/or their capacity is highly variable, it is desirable to design a system that is robust in the sense that it is not affected by the poorly performing servers. By replicating jobs and assigning them to several different servers simultaneously, we not only achieve robustness but we can also make the system more efficient under certain conditions so that the jobs are processed at a faster rate overall. In this paper we consider the option of replicating jobs and study how the performance of different ‘degrees’ of replication, ranging from no replication to full replication, affects the performance of a system of parallel servers.

We study the problem of dynamically allocating flexible workers to stations in tandem or serial manufacturing systems. Workers are trained to do a subset of consecutive tasks. We show that the optimal policy is often LBFS (last buffer first-served) or FBFS (first buffer first-served). These results generalize earlier results on the optimality of the pick-and-run, expedite, and bucket brigade-type policies. We also show that, for exponential processing times and general manufacturing networks, the optimal policy will tend to have several workers assigned to the same station.

In 1988 Whittle introduced an important but intractable class of restless bandit problems which generalise the multiarmed bandit problems of Gittins by allowing state evolution for passive projects. Whittle's account deployed a Lagrangian relaxation of the optimisation problem to develop an index heuristic. Despite a developing body of evidence (both theoretical and empirical) which underscores the strong performance of Whittle's index policy, a continuing challenge to implementation is the need to establish that the competing projects all pass an indexability test. In this paper we employ Gittins' index theory to establish the indexability of (inter alia) general families of restless bandits which arise in problems of machine maintenance and stochastic scheduling problems with switching penalties. We also give formulae for the resulting Whittle indices. Numerical investigations testify to the outstandingly strong performance of the index heuristics concerned.

We consider the dynamic scheduling of a multiclass queueing system with two servers, one dedicated (server 1) and one flexible (server 2), with no arrivals. Server 1 is dedicated to processing type-1 jobs while server 2 is primarily responsible for processing type-2 jobs but can also aid server 1 with its work. We address when it is optimal for server 2 to aid server 1 with type-1 jobs rather than process type-2 jobs. The objective is to minimize the total holding costs incurred until all jobs in the system are processed and leave the system. We show that the optimal policy can exhibit one of three possible structures: (i) an exhaustive policy for type-2 jobs, (ii) a nonincreasing switching curve in the number of type-1 jobs and (iii) a nondecreasing switching curve in the number of type-1 jobs. We characterize the necessary and sufficient conditions under which each policy will be optimal. We also explore the use of the optimal policy for the problem with no arrivals as a heuristic for the problem with dynamic arrivals.

We study a service system in which, in each service period, the server performs the current set B of tasks as a batch, taking time s(B), where the function s(·) is subadditive. A natural definition of ‘traffic intensity under congestion’ in this setting is ρ := limt→∞t-1Es (all tasks arriving during time [0,t]). We show that ρ > 1 and a finite mean of individual service times are necessary and sufficient to imply stability of the system. A key observation is that the numbers of arrivals during successive service periods form a Markov chain {An}, enabling us to apply classical regenerative techniques and to express the stationary distribution of the process in terms of the stationary distribution of {An}.

We show that if performance measures in a general stochastic scheduling problem satisfy partial conservation laws (PCL), which extend the generalized conservation laws (GCL) introduced by Bertsimas and Niño-Mora (1996), then the problem is solved optimally by a priority-index policy under a range of admissible linear performance objectives, with both this range and the optimal indices being determined by a one-pass adaptive-greedy algorithm that extends Klimov's: we call such scheduling problems PCL-indexable. We further apply the PCL framework to investigate the indexability property of restless bandits (two-action finite-state Markov decision chains) introduced by Whittle, obtaining the following results: (i) we present conditions on model parameters under which a single restless bandit is PCL-indexable, and hence indexable; membership of the class of PCL-indexable bandits is tested through a single run of the adaptive-greedy algorithm, which further computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (ii) we further introduce the subclass of GCL-indexable bandits (including classical bandits), which are indexable under arbitrary linear rewards. Our analysis is based on the achievable region approach to stochastic optimization, as the results follow from deriving and exploiting a new linear programming reformulation for single restless bandits.

We consider the optimal stochastic scheduling of a two-stage tandem queue with two parallel servers. The servers can serve either queue at any point in time and the objective is to minimize the total holding costs incurred until all jobs leave the system. We characterize sufficient and necessary conditions under which it is optimal to allocate both servers to the upstream or downstream queue. We then conduct a numerical study to investigate whether the results shown for the static case also hold for the dynamic case. Finally, we provide a numerical study that explores the benefits of having two flexible parallel servers which can work at either queue versus servers dedicated to each queue. We discuss the results' implications for cross-training workers to perform multiple tasks.

A set of jobs is to be processed on a machine which is subject to breakdown and repair. When the processing of a job is interrupted by a machine breakdown, the processing later resumes at the point at which the breakdown occurred. We assume that the machine uptime is Erlang distributed and that processing and repair times follow general distributions. Simple permutation policies on both machine parameters and the processing distributions are given which minimize the weighted number of tardy jobs, weighted flow times and the weighted sum of the job delays.

We study the problem of preemptive scheduling of jobs in a two-machine open shop. Jobs require processing on both machines, but the order does not matter. We define the D-LERPT (double longest expected remaining processing time) policy as the policy that first processes jobs that have not yet been processed by either machine (double jobs), in decreasing order of expected remaining processing times, and then processes jobs that require processing on only one machine in any order. We show that D-LERPT stochastically minimizes the makespan when preemption is not permitted and jobs (but not machines) are stochastically identical, and that D-LERPT minimizes the makespan in the increasing convex sense when preemption is permitted and the machines are stochastically identical and processing times are exponential or geometric with a job dependent rate.

A single machine is available to process a collection of jobs J, each of which evolves stochastically under processing. Jobs incur costs while awaiting the machine at a rate which is state dependent and processing must respect a set of precedence constraints Γ. Index policies are optimal in a variety of scenarios. The indices concerned are characterised as values of restart problems with the average reward criterion. This characterisation yields a range of efficient approaches to their computation. Index-based suboptimality bounds are derived for general processing policies. These bounds enable us to develop sensitivity analyses and to evaluate scheduling heuristics.

In this paper we study scheduling problems of multiclass customers on identical parallel processors. A new type of arrival process, called a Markov decision arrival process, is introduced. This arrival process can be controlled and allows for an indirect dependence on the numbers of customers in the queues. As a special case we show the optimality of LEPT and the µc-rule in the last node of a controlled tandem network for various cost structures. A unifying proof using dynamic programming is given.

A single machine is available to process a collection of stochastic jobs. Processing is preemptive and so (for example) the machine is allowed to switch away from a job before completion, should that prove advantageous. The jobs are deteriorating in the sense that their processing requirements grow (at job-specific rates) as they await processing. This phenomenon might be expected to enhance the status of non-preemptive policies. The primary objective of the paper is to find conditions which are sufficient to ensure the existence of a permutation policy to minimise the expected makespan. We also derive results for a weighted flowtime criterion. Applications of such models to the control of queues and to communication systems have been cited by other authors.

We show that using the FIFO service discipline at single server stations with ILR (increasing likelihood ratio) service time distributions in networks of monotone queues results in stochastically earlier departures throughout the network. The converse is true at stations with DLR (decreasing likelihood ratio) service time distributions. We use these results to establish the validity of the following comparisons:

(i) The throughput of a closed network of FIFO single-server queues will be larger (smaller) when the service times are ILR (DLR) rather than exponential with the same means.

(ii) The total stationary number of customers in an open network of FIFO single-server queues with Poisson external arrivals will be stochastically smaller (larger) when the service times are ILR (DLR) rather than exponential with the same means.

We also give a surprising counterexample to show that although FIFO stochastically maximizes the number of departures by any time t from an isolated single-server queue with IHR (increasing hazard rate, which is weaker than ILR) service times, this is no longer true for networks of more than one queue. Thus the ILR assumption cannot be relaxed to IHR.

Finally, we consider multiclass networks of exponential single-server queues, where the class of a customer at a particular station determines its service rate at that station, and show that serving the customer with the highest service rate (which is SEPT — shortest expected processing time first) results in stochastically earlier departures throughout the network, among all preemptive work-conserving policies. We also show that a cµ rule stochastically maximizes the number of non-defective service completions by any time t when there are random, agreeable, yields.

A single machine is available to process a collection of stochastic jobs preemptively. Rewards are received at job completions. We seek policies for machine allocation which maximize the total reward. Application areas point to the need to study such models for resource allocation when job processing requirements are dependent. To this end, models are developed in which the nature of such dependence is derived from various notions of positive and negative dependence in common usage in reliability. Optimal policies for resource allocation of simple structure are obtained for a variety of such models.

We consider scheduling problems with m machines in parallel and n jobs. The machines are subject to breakdown and repair. Jobs have exponentially distributed processing times and possibly random release dates. For cost functions that only depend on the set of uncompleted jobs at time t we provide necessary and sufficient conditions for the LEPT rule to minimize the expected cost at all t within the class of preemptive policies. This encompasses results that are known for makespan, and provides new results for the work remaining at time t. An application is that if the cµ rule has the same priority assignment as the LEPT rule then it minimizes the expected weighted number of jobs in the system for all t. Given appropriate conditions, we also show that the cµ rule minimizes the expected value of other objective functions, such as weighted sum of job completion times, weighted number of late jobs, or weighted sum of job tardinesses, when jobs have a common random due date.

The bivariate characterization of stochastic ordering relations given by Shanthikumar and Yao (1991) is based on collections of bivariate functions g(x, y), where g(x, y) and g(y, x) satisfy certain properties. We give an alternate characterization based on collections of pairs of bivariate functions, g1(x, y) and g2(x, y), satisfying certain properties. This characterization allows us to extend results for single machine scheduling of jobs that are identical except for their processing times, to jobs that may have different costs associated with them.

In this note we give a counterexample which shows that the µc-rule is not optimal in the second node of the tandem queue. This counterexample contradicts the interchange argument in Nain [1] and Nain et al. [2].