Scheduling in the Multiclass M/G/1 queue

Here is a bit more about this for those who are interested. Shyam has asked me about this section of the last lecture.

The result in Section 8.7 is originally due to Klimov in this paper: Klimov, G.P. (1974). Time-sharing service systems I, Theory Probab. Appl.,19, 532–51.

However, you will find easier to read something like this: On the Gittins index in the M/G/1 queue, Aalto, Ayesta and Righter, Queueing Systems, 63, 437-458, 2009, and also to see that researchers are still thinking about it even 35 years later!

Abstract: For an M/G/1 queue with the objective of minimizing the mean number of jobs in the system, the Gittins index rule is known to be optimal among the set of non-anticipating policies. We develop properties of the Gittins index. For a single-class queue it is known that when the service time distribution is of type Decreasing Hazard Rate (New Better than Used in Expectation), the ...

Perhaps you wondered about my calculation of a Gittins index as

         $\frac{r_i +  \alpha t_i r_1}{t_i + α t_i t_1}$

This is when we are trying to find the bandit of second highest priority after job class 1. In calculating its index in an undiscounted case we will be wanting to maximize the quantity of  (reward up to $\tau$)/$\tau$. The stopping time $\tau$ will be the first time that we have again cleared the system of type 1 jobs, i.e. all jobs of priority greater than $i$ (assuming hypothetically for now that $i$ is the job type of second greatest index).

Although it is not actually needed, we can value of $\alpha$ as follows. It is the length of a busy period of type 1 jobs that is created while we process a single type $i$ job.

Processing the type $i$ job takes time $t_i$. During that time suppose $M$ type 1 jobs arrive. To clear one of these, and other type 1 jobs that arrive while doing so (and while doing thoses, etc) takes an expected time $x_1$, where

$x_1 = t_1 + (\lambda_1 t_1) x_1$ 

Think about this. While we process one class 1 job, other class 1 jobs arrive, the expected number of which is $\lambda_1 t_1$. So $x_1 = t_1/(1-\lambda_1 t_1)$. So we will take time $M x_1$ to clear type 1 jobs after after finishing a type $i$ job. The expected value of $M$ is $\lambda_1 t_i$. So 

$\alpha = \lambda t_1/(1-\lambda_1 t_1 )$.

We also get a $r_1$ for each type 1 job cleared, and so this is why the numerator has $\alpha t_i r_1$. 

A similar calculation will be carried out when we have identified the job class of second highest priority, say class 2, and and are now looking for the one of third highest priority. Now $\alpha$ will be determined by the time needed to clear all jobs of classes 1 and 2.

Session 4

In today's lecture I used a portion of my slides from a talk on the Gittins Index. You may enjoy looking through the entire talk. It will look better if you download the .pdf file to your computer and read the presentation with a .pdf viewer such as acrobat, rather than try to read within your browser.

I have slightly changed Problems sheet 2. The assignment for this week is to do questions 5-7.

Subsequent to today's lecture I have made some changes to sections 8.5 and 8.7, now using $C_i$ to mean the completion time of job $i$. I did not discuss Section 8.8 of the notes. This is about an application of the Gittins index theorem to a problem in which it at first does not seem to apply because the states of the bandits that are not continued are not frozen.

It is remarkable how many interesting problems can be recast as bandit problems. We saw today several ways to massage some problems into the form of bandit processes (Weitzmas's problem, target and tax problems, and scheduling in a $M/G/1$ queue). In particular, we saw that the $\beta\to 1$ limit can be meaningful. You will explore this a bit in Problem 6 on Problems Sheet 2.

The proof of the Gittins index theorem is actually fairly easy. Yet it is one of the most beautiful results in the field of Markov decision processes. Its discovery and proof in 1974 is due to John Gittins. The proof I have given in today's lecture is very different to Gittins's original proof. It was first presented in my paper On the Gittins index for multiarmed bandits. Ann. Appl. Prob. 2, 1024-33, 1992.

Session 3

I started today by talking about the solution to the burglar problem. This is a subtle question and a very good one for testing your understanding. My solutions for the problems are now on the web site.

I said more about the problem with which we ended Session 2, namely, the famous unsolved problem concerned with searching for a randomly moving hidden object. But I realized later that I forgot to make the comment that this is an example of a partially observed Markov decision process (POMDP). In a POMDP the decision-maker cannot directly observe the underlying state. Instead, he must maintain a probability distribution over the set of possible states, based on his observations, and the underlying MDP. This distribution is updated using the usual Bayesian calculations. That is what we did by defining $x_i=P(\text{object is in location $i$})$.

I mentioned that this problem has not yet been solved in full generality. However, the problem has been solved in continuous time. See R. R. Weber. Optimal search for a randomly moving object. J. Appl. Prob. 23:708-717, 1986. The reason the problem is easier in continuous time is that the state $x_1$ (the probability that the object is in location 1) changes continuously, rather than in jumps.

Let me emphasize that in Session 2 (Chapter 4), we used $F_s(x)$ to mean the value function of a MDP over $s$ steps, with $F_0(x)=0$. In the case of $c(x,u)\geq 0$, $F_s(x)$ is clearly nondecreasing in $s$. By contrast, in this lecture, $F_s(x)$ was used to mean the minimum cost in a stopping problem in which we must stop within $s$ steps, and $F_0(x)=k(x)$. $F_s(x)$ is now clearly nonincreasing in $s$. That is because as $s$ increases we are being given more flexibility as to when we must stop. In both cases $F_s(x)$ satisfies an optimality equation and $F_s(x)\to$ a limit, say $F_\infty(x)$, but from a different direction.

In Lecture 5 we looked at some stopping problems, which are a type of problem that crop up all over the place. Those of you working in economics and finance are almost certainly familiar with the theory of option pricing (Black-Scholes). The holder of an American option is allowed to exercise the right to buy (or sell) the underlying asset at a predetermined price at any time before or at the expiry date. The valuation of American options is essentially an optimal stopping problem.

You can read more about Bruss's odds algorithm in his paper: "Sum the odds to one and stop" Annals of Probability, Vol. 28, 1384–1391, (2000). I showed you (and have now added to the notes) how to use this to address a Secretary Problem in which the candidates arrive in groups, of sizes $t_1,t_2,\dotsc,t_h$. This partially addresses a problem asked by Ken Chang about secretary problems in which candidates are heterogeneous.

I decided not to talk about Example 6.2. You might like to look at that in the notes. This is a classic problem, which was addressed by some of the mathematicians who did the earliest work on optimal stopping problems.

Let me finish with some hints for the first four questions of Problems Sheet 2. Question 1 can be solved by realizing that there are only two stationary Markov policies. You simple need to decide which is best. Question 2 is a simple stopping problem that can be solved using a OSLA rule. When you do Question 3 you might think about using Bruss's Odds Algorithm. Although you cannot apply the algorithm directly, you should be able to solve this problem using the same scheme of proof as we used to prove Bruss's result in 6.1. Question 4 is an important one because it should convince you that it is possible to solve stochastic dynamic programming equations using linear programming (at least if both state space and action space are finite.)  It there are $n$ states and $m$ actions (controls) available in each state then we will have an LP in $n$ variables, with $nm$ linear inequality constraints.