1 Introduction
We consider the optimal scheduling problem of a single-server queue with Poisson arrivals and generally distributed service times, i.e., the M/G/1 queue. The objective is to minimize the mean delay (a.k.a. sojourn time or response time). The characteristics of the optimal scheduling discipline depend on the information available to the scheduler. The scheduler is said to be anticipating if it knows the remaining service times of jobs, while a nonanticipating scheduler does not know the remaining service times of jobs.
The optimal anticipating scheduling policy, shortest-remaining-processing-time (SRPT), minimizes the number of jobs even sample-pathwise for general service times and arrival processes [11, 14]. The optimal nonanticipating scheduling policy minimizing the mean delay in the M/G/1 queue is known to be the Gittins index policy [2, 3, 7, 8, 12]. Gittins derived this result as a by-product of his ground-breaking results on the multiarmed bandit1 problems [7, 8]. These problems remained unsolved for long, until Gittins proved that the structure of the optimal policy is surprisingly simple based on an index associated with each bandit separately depending just on the state of the bandit [17]. In our scheduling problem, bandits correspond to jobs: When one of them is being served, the states of the other jobs remain frozen.
Advertisement
The Gittins index is thoroughly characterized for ordinary jobs whose state is described by the attained service.2 For example, if the service time distribution belongs to the new-better-than-used-in-expectation (NBUE) family of distributions, then the Gittins index policy coincides with the well-known first-come-first-served (FCFS) scheduling discipline, or if there are multiple job classes and the service time distributions of all classes belong to the decreasing-mean-residual-lifetime (DMRL) family, then the Gittins index policy coincides with the shortest-expected-remaining-processing-time (SERPT) discipline [2].3
While the Gittins index is thoroughly characterized for ordinary jobs, this is not the case with jobs that have more complex structure. Recently, a class of such jobs, multistage jobs, were introduced in [13]. A multistage job progresses through a stochastic sequence of stages, each of which has its own independent stochastic service requirement, and the job completes when its last stage completes. The state of an uncompleted multistage job is described by the pair (j, a), where j refers to the current stage and a to the attained service in the current stage. In [13], it is shown that the computation of Gittins index of a multistage job decomposes into separable computations for the individual stages. The characterization is, however, indirect in the sense that it relies on the recursion for an auxiliary function (the so-called SJP function) and not for the Gittins index itself. Thus, it is natural to ask whether the characterization is possible to do more directly: Is it possible to compute the Gittins index by recursively combining the Gittins indices of individual stages?
In this paper, we focus on sequential multistage jobs, which have a fixed sequence of stages, and prove that, for such jobs, it is indeed possible to compute the Gittins index directly by recursively combining the Gittins indices of individual stages. In addition, we give sufficient conditions under which FCFS is the optimal nonanticipating policy for sequential multistage jobs, and a corresponding result for SERPT when there are multiple classes of sequential multistage jobs. On the other hand, we demonstrate that, for nonsequential multistage jobs, it is usually better to compute the Gittins index by utilizing the SJP functions. We also discuss the connection between the scheduling problem of multistage jobs and the optimal control problem of tandem queues with flexible servers.
The rest of the paper is organized as follows. In Sect. 2, we recall some results concerning the Gittins index and the related Gittins index policy for ordinary jobs (consisting of a single stage). In Sect. 3, we present our main result concerning the direct computation of the Gittins index for sequential multistage jobs. As other main results, we give sufficient conditions for the optimality of the FCFS and SERPT disciplines for scheduling sequential multistage jobs. In Sect. 4, we discuss the connection between the scheduling problem of multistage jobs and the optimal control problem of tandem queues with flexible servers. In Sect. 5, we discuss the relationship between our new results and the approach based on the SJP framework. In Sect. 6, we discuss the computation of the Gittins index for nonsequential multistage jobs. Finally, in Sect. 7, we outline how one can generalize our main result to a more general model of sequential multistage jobs.
Advertisement
The original version of this paper, albeit very different and much more complicated due to the alternative approach used, is available in [1].
2 Gittins index and the optimal policy for ordinary jobs
In this preliminary section, we first recall some results (Lemmas 1, 2) related to the Gittins index for ordinary single-stage jobs. These results characterize the optimal nonanticipating policy (i.e., the Gittins index policy) for the corresponding M/G/1 scheduling problem in certain cases (Propositions 1, 2).
Consider first a single ordinary job with service time S. From a nonanticipating scheduler point of view, the state of such an ordinary job is described by its attained service a, which increases at rate 1 whenever served, until the service is completed. As presented in [2, 3, 7, 8, 12], the corresponding Gittins index G(a) at state \(a \ge 0\) can be characterized as follows:
$$\begin{aligned} G(a) = \sup _{b> a} \frac{P\{S \le b \mid S> a\}}{E[\min \{S,b\} - a \mid S > a]}. \end{aligned}$$
(1)
Remark 1
The intuition behind the Gittins index is as follows. Imagine the state \(b > a\) as a “stopping state,” and suppose we serve the job until it either completes or reaches the stopping state. In (1), the numerator is the probability the job completes before reaching the stopping state, and the denominator is the expected amount of time we spend serving the job. The fraction in (1) can therefore be thought of as an “expected completion rate” relative to stopping state b. The Gittins index G(a) is the thus maximum expected completion rate attainable by optimizing the stopping state b.
The mean residual lifetime (MRL) function M(a) of a service time distribution is defined asLet NBUE refer to the family of service time distributions with the New-Better-than-Used-in-Expectation property, i.e.,Now, we give a known result, which we utilize later on in this paper.
$$\begin{aligned} M(a) = E[S - a \mid S > a]. \end{aligned}$$
(2)
$$\begin{aligned} M(a) \le M(0) \quad \hbox {for all}\, a \ge 0. \end{aligned}$$
(3)
Lemma 1
([2, Prop. 7]) The service time distribution belongs to NBUE if and only ifMoreover, if the service time distribution belongs to NBUE, then
$$\begin{aligned} G(a) \ge G(0) = \frac{1}{M(0)} \quad \hbox {for all}\, a \ge 0. \end{aligned}$$
(4)
$$\begin{aligned} G(a) \ge \frac{1}{M(a)} \quad \hbox {for all}\, a \ge 0. \end{aligned}$$
Let then DMRL refer to the family of service time distributions with a decreasing MRL function, i.e.,Note that \(\mathrm {DMRL} \subset \mathrm {NBUE}\). Below we give another known result, which we utilize later on in this paper.
$$\begin{aligned} M(b) \le M(a) \quad \hbox {for all }\,b \ge a. \end{aligned}$$
(5)
Lemma 2
([2, Prop. 6 ]) The service time distribution belongs to DMRL if and only if
$$\begin{aligned} G(a) = \frac{1}{M(a)} \quad \text {for all } a \ge 0. \end{aligned}$$
(6)
Thus, if the service time distribution belongs to DMRL, the Gittins index \(G(a) = 1/M(a)\) is an increasing function of a.
Let us now consider the optimal scheduling problem of an M/G/1 queue loaded with ordinary jobs. Assume that the jobs are classified into \(K \ge 1\) different classes. Let FCFS refer to the first-come-first-served scheduling discipline, which serves customers in their arrival order, and SERPT to the shortest-expected-remaining-processing-time discipline, where the scheduler always serves the job with the current shortest mean residual lifetime (2). Below we give two known results related to these scheduling disciplines, which are based on the two lemmas above.
Proposition 1
([2, Thm. 4]) Assume that there is just one class of ordinary jobs (\(K = 1\)). If the service time distribution belongs to NBUE, then FCFS (or any other nonpreemptive work-conserving policy) is the optimal nonanticipating policy.
Proposition 2
([2, Thm. 7]) Assume that there are K classes of ordinary jobs (\(K \ge 2\)). If the service time distributions for all job classes belong to DMRL, then SERPT is the optimal nonanticipating policy.
3 Gittins index and the optimal policy for sequential multistage jobs
In this section, we present our main results (Theorem 1, Corollaries 1, 2, and 3) concerning the computation of the Gittins index for sequential multistage jobs. In addition, based on these results, we characterize the optimal nonanticipating policy (i.e., the Gittins index policy) for the corresponding M/G/1 scheduling problem in certain cases (Theorems 2, 3).
Multistage jobs were introduced in [13] as jobs consisting of a finite number of stages, say J, that form an absorbing acyclic Markov chain. The service times \(S_j\) in each stage j are assumed to be independent. From a nonanticipating scheduler point of view, the state of such a multistage job is described by the pair (j, a), where j refers to the current stage and a to the attained service at the current stage. As noted in [13], the Gittins index G(j, a) for a multistage job is defined by a multidimensional optimization problem with one dimension per stage, which makes the direct computation of the Gittins indices intractable in general. However, below we demonstrate that this is not the case always but the direct computation is, indeed, tractable for a certain type of multistage jobs.
A multistage job with a fixed (i.e., deterministic) sequence of stages is called a sequential multistage job. The total service time S of such a job is given bywhere \(S_j\) refers to the service time of stage j and J is the number of stages for the job. So, the service starts from stage 1, and only when the first stage is completed, the service of stage 2 starts and so on. The whole service is completed when the service of the last stage is completed. The crucial difference between a sequential multistage job and an ordinary job with service time S is that in the multistage case, the scheduler is aware of which stage j is currently in progress, as indicated by the multistage job’s state being a pair (j, a).
$$\begin{aligned} S = S_1 + \ldots + S_J, \end{aligned}$$
The Gittins index G(j, a) for the whole sequential multistage job at state (j, a) is defined by the following multidimensional optimization problem [13]:Although the above expression appears complicated, it follows essentially the same intuition as explained for the single-stage case in Remark 1. The difference is that instead of a single stopping state, we have a “stopping set” represented by a multidimensional vector \((b_j, b_{j+1}, \ldots , b_J)\), where we stop serving the job once it reaches state \((i, b_i)\) for any stage \(j \le i \le J\). In (7), the numerator is the probability the job completes without hitting the stopping set, and the denominator is the amount of time we spend serving the job until it completes or hits the stopping set.
$$\begin{aligned} \begin{aligned}&G(j,a) = \sup _{b_j> a, \; b_{j+1},\ldots ,b_J> 0} \\&\quad \frac{P\{S_j \le b_j, S_{j+1} \le b_{j+1}, \ldots , S_J \le b_J \mid S_j> a\}}{E\big [\min \{S_j,b_j\} - a + \sum _{n = j+1}^J \prod _{m = j}^{n-1} 1_{\{S_m \le b_m\}} \min \{S_n,b_n\} \mid S_j > a \big ]}. \end{aligned} \end{aligned}$$
(7)
Below, we show that the multidimensional optimization problem in (7) can be solved recursively stage-by-stage. So, instead of solving one (intractable) multidimensional optimization problem, we can proceed by solving a sequence of (tractable) one-dimensional problems.
Theorem 1
For any sequential multistage job with J stages, the Gittins index can be calculated recursively as follows:where \(G_J(a)\) denotes the Gittins index of a single-stage job with service time \(S_J\), and \(G_{\le J-1}(j,a)\) denotes the Gittins index at state (j, a) of a sequential multistage job consisting of stages \(1,2,\ldots ,J-1\).4
$$\begin{aligned} \begin{aligned} G(J,a)&= G_J(a) = \sup _{b> a} \frac{P\{S_J \le b \mid S_J> a\}}{E[\min \{S_J,b\} - a \mid S_J> a]}, \\ G(j,a)&= \sup _{b > 0} \frac{P\{S_J \le b\}}{\frac{1}{G_{\le J-1}(j,a)} + E[\min \{S_J,b\}]}, \quad j \in {\{1,2,\ldots ,J-1\}}, \end{aligned} \end{aligned}$$
(8)
Proof
Consider a sequential multistage job with J stages. For the last stage J, the claim \(G(J,a) = G_J(a)\) is trivially true. Let then \(j \in \{1,2,\ldots ,J-1\}\). According to (7), the Gittins index G(j, a) at state (j, a) reads aswhere we have used the following shorthand notations:Since the stages are independent, we haveThus,which is equivalent toThis completes the proof. \(\square \)
$$\begin{aligned} G(j,a) = \sup _{b_j> a, \; b_{j+1},\ldots ,b_J > 0} \frac{P(b_j, b_{j+1}, \ldots , b_J \mid a)}{E[b_j, b_{j+1}, \ldots , b_J \mid a]}, \end{aligned}$$
$$\begin{aligned} \begin{aligned}&P(b_j, b_{j+1}, \ldots , b_J \mid a) \; \\&\quad =P\{S_j \le b_j, S_{j+1} \le b_{j+1}, \ldots , S_J \le b_J \mid S_j> a\}, \\&E[b_j, b_{j+1}, \ldots , b_J \mid a] \; \\&\quad = E\big [\min \{S_j,b_j\} - a + \sum _{n = j+1}^J \prod _{m = j}^{n-1} 1_{\{S_m \le b_m\}} \min \{S_n,b_n\} \mid S_j > a \big ]. \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned}&P(b_j, b_{j+1}, \ldots , b_J \mid a) \; \\&\quad = P(b_j, b_{j+1}, \ldots , b_{J-1} \mid a) P\{S_J \le b_J\}, \\&E[b_j, b_{j+1}, \ldots , b_J \mid a] \; \\&\quad = E[b_j, b_{j+1}, \ldots , b_{J-1} \mid a] + P(b_j, b_{j+1}, \ldots , b_{J-1} \mid a) E[\min \{S_J,b_J\}]. \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned}&G(j,a) = \sup _{b_j> a, \; b_{j+1},\ldots ,b_J > 0} \\&\quad \frac{P(b_j, b_{j+1}, \ldots , b_{J-1} \mid a) P\{S_J \le b_J\}}{E[b_j, b_{j+1}, \ldots , b_{J-1} \mid a] + P(b_j, b_{j+1}, \ldots , b_{J-1} \mid a) E[\min \{S_J,b_J\}]}, \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} G(j,a)&= \; \sup _{b_J> 0} \frac{P\{S_J \le b_J\}}{\inf _{b_j> a, \; b_{j+1},\ldots ,b_{J-1}> 0} \frac{E[b_j, b_{j+1}, \ldots , b_{J-1} \mid a]}{P(b_j, b_{j+1}, \ldots , b_{J-1} \mid a)} + E[\min \{S_J,b_J\}]} \\&= \; \sup _{b_j > 0} \frac{P\{S_J \le b_j\}}{\frac{1}{G_{\le J-1}(j,a)} + E[\min \{S_J,b_j\}]}. \end{aligned} \end{aligned}$$
By applying Lemma 3 (presented in Appendix A) to (8) with the choice \(u = G_{\le J-1}(j,a)\), we get the following corollary.
Corollary 1
Consider a sequential multistage job with J stages for which the service time of the last stage belongs to NBUE. Now, for any \(a \ge 0\),where \(G_{\le J-1}(j,a)\) denotes the Gittins index at state (j, a) of a sequential multistage job consisting of stages \(1,2,\ldots ,J-1\).
$$\begin{aligned} \begin{aligned} G(J,a) =&\; G_J(a), \\ G(j,a) =&\; \frac{1}{\frac{1}{G_{\le J-1}(j,a)} + E[S_J]}, \quad j \in {\{1,2,\ldots ,J-1\}}, \end{aligned} \end{aligned}$$
(9)
By continuing and combining this corollary with Lemma 1 presented in Sect. 2 (and the remark made thereafter), we get another corollary.
Corollary 2
Consider a sequential multistage job with J stages for which the service time of each stage belongs to NBUE. Now, for any \(j \in {1,2,\ldots ,J}\) and \(a \ge 0\),
$$\begin{aligned} G(j,a) \ge G(1,0) = \frac{1}{E[S]}. \end{aligned}$$
(10)
By further continuing and combining Corollary 1 with Lemma 2 presented in Sect. 2, we get still another corollary.
Corollary 3
Consider a sequential multistage job with J stages for which the service time of each stage belongs to DMRL. Now, for any \(j \in {1,2,\ldots ,J}\) and \(a \ge 0\),where M(j, a) is the MRL function for the sequential multistage job at state (j, a),
$$\begin{aligned} G(j,a) = \frac{1}{M(j,a)}, \end{aligned}$$
(11)
$$\begin{aligned} M(j,a) = E[S_j - a \mid S_j > a] + E[S_{j+1}] + \ldots + E[S_J]. \end{aligned}$$
(12)
Let us now consider the optimal scheduling problem of an M/G/1 queue loaded with sequential multistage jobs. Assume that the jobs are classified into \(K \ge 1\) different classes, and service time of a class-k job consists of \(J_k\) stages,Below we give two novel results, which follow immediately from the two last corollaries above.
$$\begin{aligned} S_k = S_{k,1} + \ldots + S_{k,J_k}. \end{aligned}$$
Theorem 2
Assume that there is just one class of sequential multistage jobs (\(K = 1\)). If the service time distributions of all stages belong to NBUE, then FCFS (or any other nonpreemptive work-conserving policy) is the optimal nonanticipating policy.
Theorem 3
Assume that there are K classes of sequential multistage jobs (\(K \ge 2\)). If the service time distributions of all stages in each job class belong to DMRL, then SERPT is the optimal nonanticipating policy.
We conclude this section with two remarks about the above results. First, the \(K = 1\) case of Theorem 3 is a special case of Theorem 2, because DMRL is a subset of NBUE. Second, under the preconditions of Theorem 2, namely in the \(K = 1\) NBUE case, the SERPT policy, like Gittins, also coincides with FCFS. This is because in this case, SERPT, like Gittins, prioritizes jobs that have started service above those that have not.
4 Connection to the optimal control of tandem queues
In this section, we discuss the connection between the scheduling problem of multistage jobs and the optimal control problem of tandem queues with flexible servers.
Assume that there is just one class of sequential multistage jobs (\(K = 1\)). In this case, the scheduling problem of multistage jobs is in fact equivalent to preemptively assigning a single server to a job at a station in a tandem queue consisting of one server, K stations, and infinite buffers at each station. Or, as well, it is equivalent to preemptively assigning multiple servers that are fully flexible (i.e., able to server any job at any station) and collaborative (i.e., able to serve simultaneously the same job). Such optimal control problems of tandem queues have been studied in [4‐6, 9, 10, 15].
In [5, 10, 15], the aim is to find the optimal policy \(\pi \) that maximizes the departure process \(D^\pi (t)\) (from the last station) either stochastically or pathwise. Note that maximizing the departure process is equivalent to minimizing the total number of jobs, \(X^\pi (t)\), for any t, since \(X^\pi (t) = A(t) - D^\pi (t)\), where A(t) refers to the arrival process of jobs at the first station, which is naturally independent of the control policy applied. In all these papers, the optimal policy, under certain additional assumptions, proves to be such that all the jobs arriving in the first station are served nonpreemptively one-by-one through all the stations so that there is, at any time, at most one job in service in the whole system. In [10], this optimal policy is called CEF (closest-to-exit-first), while, in [15], it is named the expedite policy, and LBFS (last-buffer-first-served) in [5]. Clearly this optimal policy, called Expedite below, corresponds to FCFS for sequential multistage jobs. Thus, our Theorem 2 together with the well-known Little’s formula gives the following optimality result.
Corollary 4
Consider a tandem queue with Poisson arrivals and fully flexible and collaborative servers. Expedite minimizes the mean total delay (i.e., the total sojourn time through all the stations), as well as the mean total number of jobs in the system, if the service times in all stations belong to NBUE.
This result does not follow from the previous ones, since the related results in [10, Theorem 2] and [5, Theorem 4.3] are restricted to exponential service times in all stations, and optimization in [15, Theorem 1] is restricted to the subset of policies for which the departure order of jobs is required to be the same as their arrival order.
In [4, 6, 9], the objective is to minimize the mean holding costs of jobs, possibly together with switching costs of servers. Our multistage job scheduling problem covers the models of these papers in the special case where holding costs remain the same in each station and there are no switching costs nor any switching delays. It follows from [9, Proposition 3] that Expedite is optimal in this special case if \(K = 2\) and optimization is restricted to the subset of nonpreemptive policies. When preemptive policies and multiple stations \(K \ge 2\) are allowed, [6, Theorem 1] implies that, in this special case, the last station K is served in a greedy and exhaustive manner, which is in line with Expedite. A similar characterization is presented in [4, Theorem 3.2] for exponential service times and \(K = 2\). On the other hand, our Theorem 2 has now the following implication, which does not follow from the previous results.
Corollary 5
Consider a tandem queue with Poisson arrivals and fully flexible and collaborative servers, where holding costs remain the same in each station and there are no switching costs nor any switching delays. In this special case, Expedite minimizes the mean holding costs if the service times in all stations belong to NBUE.
Finally, we note that, for any stationwise service time distributions and even when there are multiple classes of jobs, the Gittins index policy, in which all servers are assigned to the job with the highest index, is optimal in a tandem queue with Poisson arrivals and fully flexible and collaborative servers minimizing (among all nonanticipating control policies) In addition, our Theorem 1 describes how to recursively compute the corresponding Gittins index.
(i)
the mean total delay and the mean total number of jobs in any case;
5 Relationship to the SJP framework
While the original method to compute the Gittins index for ordinary jobs (as presented in Sect. 2) was based on the work of Gittins himself, an interesting alternative method has recently been presented in [13], where the so-called SJP (single-job profit) framework is introduced. Given attained service a and an arbitrary parameter \(r \ge 0\), one defines the SJP function asAs a supremum of convex increasing functions of r, the SJP function has a (partial) inverse with respect to its second argument:One can define the Gittins index in terms of the inverse SJP function asThe SJP framework can also be utilized to compute the Gittins index for multistage jobs. In this section, we discuss the relationship between the SJP approach and our new approach.
$$\begin{aligned} V(a;r) = \sup _{b> a} \Big ( r P\{S \le b \mid S> a\} - E[\min \{S,b\} - a \mid S > a] \Big ). \end{aligned}$$
(13)
$$\begin{aligned} V^{-1}(a; u) = \inf \{ r \ge 0 : V(a; r) > u \}. \end{aligned}$$
$$\begin{aligned} G(a) = \frac{1}{V^{-1}(a;0)}. \end{aligned}$$
(14)
Consider a sequential multistage job that consists of J stages. According to [13], the Gittins index G(j, a) at state (j, a) satisfieswhere \(V^{-1}(j,a;\cdot )\) is the partial inverse of \(V(j,a;\cdot )\), the SJP function at state (j, a), which is in turn defined by the following multidimensional optimization problem:In [13], a composition law is proved, which reduces the computation of the SJP function (and, thus, the Gittins index, as well) for any multistage job into separable SJP computations for the individual stages. Below we formulate this composition law for sequential multistage jobs.
$$\begin{aligned} G(j,a) = \frac{1}{V^{-1}(j,a;0)}, \end{aligned}$$
(15)
$$\begin{aligned} \begin{aligned}&V(j,a;r) = \sup _{b_j> a, \; b_{j+1},\ldots ,b_J> 0} \\&\quad \Bigg ( r P\{S_j \le b_j, S_{j+1} \le b_{j+1}, \ldots , S_J \le b_J \mid S_j> a\} \; \\&\qquad - E\bigg [\min \{S_j,b_j\} - a + \sum _{n = j+1}^J \prod _{m = j}^{n-1} 1_{\{S_m \le b_m\}} \min \{S_n,b_n\} \mid S_j > a \bigg ] \Bigg ). \end{aligned} \end{aligned}$$
(16)
Proposition 3
([13, Thm. 4.2]) For any sequential multistage job with J stages, the SJP function can be calculated recursively as follows:where \(V_{\le J-1}(j,a;\cdot )\) refers to the SJP function for a sequential multistage job consisting of stages \(1,2,\ldots ,J-1\) at state (j, a), and \(V_J(0;\cdot )\) refers to the SJP function for a single-stage job consisting just of stage J at state 0.
$$\begin{aligned} \begin{aligned} V(J,a;r) =&\; V_J(a;r), \\ V(j,a;r) =&\; V_{\le J-1}(j,a;V_J(0;r)), \quad j \in {\{1,2,\ldots ,J-1\}}, \end{aligned} \end{aligned}$$
(17)
By iterating Proposition 3 and taking inverses, one can transform (15) into nested single-stage inverse SJP functions:While (18) characterizes the Gittins index for a sequential multistage job indirectly via the inverse of the SJP function, our novel result presented in Theorem 1 gives a more direct computation method: It enables computing the Gittins index for a sequential multistage job by solving a single one-dimensional optimization problem for each stage.
$$\begin{aligned} \begin{aligned} G(j, a)&= \frac{1}{V_J^{-1}(0; V_{J-1}^{-1}(0; \cdots V_{j+1}^{-1}(0; V_j^{-1}(a; 0)) \cdots ))} \\&= \frac{1}{V_J^{-1}(0; V_{J-1}^{-1}(0; \cdots V_{j+1}^{-1}(0; 1/G_j(a)) \cdots ))}. \end{aligned} \end{aligned}$$
(18)
The alternative perspectives offered by (18) and Theorem 1 can be reconciled. Underlying Theorem 1 is a direct way of computing the inverse SJP function of a single-stage job. Specifically, using reasoning similar to the proof of Theorem 1, one can showFor completeness, we provide a proof in Proposition 4 (presented in Appendix B).
$$\begin{aligned} V^{-1}(a; u) = \inf _{b> a} \frac{u + E[\min \{S, b\} - a \mid S> a]}{P\{S \le b \mid S > a\}}. \end{aligned}$$
6 Gittins index for nonsequential multistage jobs
In this section, we discuss whether it is useful or at least possible to generalize Theorem 1 to any multistage jobs. There is one type of nonsequential job, or more accurately sequential jobs with possible skips, to which Theorem 1 easily applies (Corollary 6). But in general, generalizing Theorem 1 is possible but not that useful as demonstrated via the examples given below (Examples 1, 2).
Let us define a sequential job with possible skips as follows: It consists of stages \(1,\ldots ,J\), but each stage j is included only with probability \(p_j\) and skipped with probability \(1 - p_j\), as revealed to the scheduler upon reaching stage j. Now, we can apply Theorem 1 to such a job because we can think of it as an ordinary sequential job: Simply give each stage j probability \(1 - p_j\) of having service time equal to 0. Thus, we have the following corollary of Theorem 1.
Corollary 6
For any sequential multistage job with possible skips, the Gittins index can be calculated recursively by applying Eq. (8) as follows: Replace the original service times \(S_j\) with the modified service times \({\tilde{S}}_j\) that take value 0 with probability \(1 - p_j\) and follow the distribution of the original service time \(S_j\) with probability \(p_j\).
Example 1
(Random number of stages) Consider now a stochastic multistage job that has a random number of stages, \(Z \in \{1,2,3\}\), where the random variable Z is independent of everything. Let \(q_j\) denote the probability that the job consists of exactly first j stages \(1,\ldots ,j\), where \(j \in \{1,2,3\}\). Clearly, the Gittins index G(j, a) for stage 3 is just the same as the Gittins index (1) for the corresponding single-stage job:For the second stage \(j = 2\), the Gittins index G(2, a) is defined by the following multidimensional optimization problem:Since all random variables are independent, it follows, after some manipulation, thatThus, the computation of the Gittins index for stage 2 reduces to a sequence of separate one-dimensional optimization problems.
$$\begin{aligned} G(3,a) = G_3(a) = \sup _{b> a} \frac{P\{S_3 \le b \mid S_3> a\}}{E[\min \{S_3,b\} - a \mid S_3 > a]}. \end{aligned}$$
$$\begin{aligned} \begin{aligned}&G(2,a) = \sup _{b_2> a, \; b_3> 0} \\&\quad \frac{P\{Z = 2, S_2 \le b_2 \mid Z \ge 2, S_2> a\} + P\{Z = 3, S_2 \le b_2, S_3 \le b_3 \mid Z \ge 2, S_2> a\}}{E\big [\min \{S_2,b_2\} - a + 1_{\{Z = 3\}} 1_{\{S_2 \le b_2\}} \min \{S_3,b_3\} \mid Z \ge 2, S_2 > a \big ]}. \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} G(2,a)&= \; \sup _{b_3> 0} \frac{P\{Z = 2 \mid Z \ge 2\} + P\{Z = 3 \mid Z \ge 2\} P\{S_3 \le b_3\}}{\inf _{b_2> a} \frac{E[\min \{S_2,b_2\} - a \mid S_2> a]}{P\{S_2 \le b_2 \mid S_2> a\}} + P\{Z = 3 \mid Z \ge 2\} E[\min \{S_3,b_3\}]} \\&= \; \sup _{b_3 > 0} \frac{P\{Z = 2 \mid Z \ge 2\} + P\{Z = 3 \mid Z \ge 2\} P\{S_3 \le b_3\}}{\frac{1}{G_2(a)} + P\{Z = 3 \mid Z \ge 2\} E[\min \{S_3,b_3\}]}. \end{aligned} \end{aligned}$$
Consider then the first stage \(j = 1\), for which the Gittins index G(1, a) is defined by the following multidimensional optimization problem:Since all random variables are independent, it follows, after some manipulation, thatAs we see from above, unlike for stages 2 and 3, the computation of the Gittins index for stage 1 does not reduce to separate one-dimensional optimization problems, but, in one optimization problem, there are as many dimensions as there are remaining possible stages.
$$\begin{aligned} \begin{aligned}&G(1,a) = \sup _{b_1> a, \; b_2, b_3> 0} \\&\quad \frac{\sum _{n = 1}^3 P\{Z = n, S_1 \le b_1, \ldots , S_n \le b_n \mid S_1> a\}}{E\big [\min \{S_1,b_1\} - a + \sum _{n = 2}^3 1_{\{Z \ge n\}} \prod _{m = 1}^{n-1} 1_{\{S_m \le b_m\}} \min \{S_n,b_n\} \mid S_1 > a \big ]}. \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} G(1,a)&= \; \sup _{b_2, b_3> 0} \\&\quad \frac{\sum _{n = 1}^3 P\{Z = n\} \prod _{m = 2}^{n} P\{S_m \le b_m\}}{\inf _{b_1> a} \frac{E[\min \{S_1,b_1\} - a \mid S_1> a]}{P\{S_1 \le b_1 \mid S_1> a\}} + \sum _{n = 2}^3 P\{Z = n\} \prod _{m = 2}^{n-1} P\{S_m \le b_m\} E[\min \{S_n,b_n\}]} \\&= \; \sup _{b_2, b_3 > 0} \frac{\sum _{n = 1}^3 P\{Z = n\} \prod _{m = 2}^{n} 1_{\{S_m \le b_m\}}}{\frac{1}{G_1(a)} + \sum _{n = 2}^3 P\{Z = n\} \prod _{m = 2}^{n-1} P\{S_m \le b_m\} E[\min \{S_n,b_n\}]}. \end{aligned} \end{aligned}$$
On the other hand, by utilizing the SJP framework and the related composition law developed in [13], we show below that the computation of the Gittins index for stage 1 can be reduced to separate one-dimensional optimization problems, which makes the computation much more tractable.
According to [13], the Gittins index G(1, a) at state (1, a) satisfieswhere V(1, a; r) denotes the SJP function at state (1, a) defined by the following multidimensional optimization problem:However, by [13, Cor. 4.5], we have the following composition for V(1, a; r), which modifies this multidimensional optimization problem into a sequence of separate one-dimensional optimization problems:where \(V_j(a;\cdot )\) refers to the SJP function for a single-stage job consisting just of stage j, \(j \in \{1,2,3\}\). \(\Box \)
$$\begin{aligned} G(1,a) = \frac{1}{V^{-1}(1,a;0)} = \frac{1}{\inf \{ r \ge 0 : V(1,a;r) > 0 \}}, \end{aligned}$$
$$\begin{aligned} \begin{aligned}&V(1,a;r) = \sup _{b_1> a, \; b_2, b_3> 0} \\&\quad \Bigg ( r \sum _{n = 1}^3 P\{Z = n, S_1 \le b_1, \ldots , S_n \le b_n \mid S_1> a\} \; \\&\qquad -E\bigg [\min \{S_1,b_1\} - a + \sum _{n = 2}^3 1_{\{Z \ge n\}} \prod _{m = 1}^{n-1} 1_{\{S_m \le b_m\}} \min \{S_n,b_n\} \mid S_1 > a \bigg ] \Bigg ). \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned}&V(1,a;r) \; \\&\quad = V_1(a; P\{Z = 1\} r + P\{Z \ge 2\} V_2(0; P\{Z = 2 \mid Z \ge 2\} r \\&+ P\{Z = 3 \mid Z \ge 2\} V_3(0;r))), \end{aligned} \end{aligned}$$
Example 2
(Parallel stages with random routing) Consider now another multistage job, which always starts with stage 1 but thereafter comes either stage 2 or 3 depending on a random and independent routing decision \(Z \in \{2,3\}\). Clearly, the Gittins index G(j, a) for stages \(j \in \{2,3\}\) is just the same as the Gittins index (1) for the corresponding single-stage job:But, for the first stage \(j = 1\), the Gittins index G(1, a) is defined by the following multidimensional optimization problem:Since the stages and the routing decision are independent, it follows, after some manipulation, thatAs we see from above, unlike for stages 2 and 3, the computation of the Gittins index for stage 1 does not reduce to separate one-dimensional optimization problems, but, in one optimization problem, there are as many dimensions as there are routing options after the first stage.
$$\begin{aligned} G(j,a) = G_j(a) = \sup _{b> a} \frac{P\{S_j \le b \mid S_j> a\}}{E[\min \{S_j,b\} - a \mid S_j > a]}, \quad j \in \{2,3\}. \end{aligned}$$
$$\begin{aligned} \begin{aligned}&G(1,a) = \sup _{b_1> a, \; b_2, b_3> 0} \\&\quad \frac{\sum _{n = 2}^3 P\{Z = n, S_1 \le b_1, S_n \le b_n \mid S_1> a\}}{E\big [\min \{S_1,b_1\} - a + \sum _{n = 2}^3 1_{\{Z = n\}} 1_{\{S_1 \le b_1\}} \min \{S_n,b_n\} \mid S_1 > a \big ]}. \end{aligned} \end{aligned}$$
$$\begin{aligned} \begin{aligned} G(1,a)&= \; \sup _{b_2, b_3> 0} \frac{\sum _{n = 2}^3 P\{Z = n\} P\{S_n \le b_n\}}{\inf _{b_1> a} \frac{E[\min \{S_1,b_1\} - a \mid S_1> a]}{P\{S_1 \le b_1 \mid S_1> a\}} + \sum _{n = 2}^3 P\{Z = n\} E[\min \{S_n,b_n\}]} \\&= \; \sup _{b_2, b_3 > 0} \frac{\sum _{n = 2}^3 P\{Z = n\} P\{S_n \le b_n\}}{\frac{1}{G_1(a)} + \sum _{n = 2}^3 P\{Z = n\} E[\min \{S_n,b_n\}]}. \end{aligned} \end{aligned}$$
On the other hand, by utilizing the SJP framework and the related composition law developed in [13], we show below that the computation of the Gittins index for stage 1 can be reduced to separate one-dimensional optimization problems, which makes the computation much more tractable.
According to [13], the Gittins index G(1, a) at state (1, a) satisfieswhere V(1, a; r) denotes the SJP function at state (1, a) defined by the following multidimensional optimization problem:However, by [13, Cor. 4.5], we have the following composition for V(1, a; r), which modifies this multidimensional optimization problem into a sequence of separate one-dimensional optimization problems:where \(V_j(a;\cdot )\) refers to the SJP function for a single-stage job consisting just of stage j, \(j \in \{1,2,3\}\). \(\Box \)
$$\begin{aligned} G(1,a) = \frac{1}{V^{-1}(1,a;0)} = \frac{1}{\inf \{ r \ge 0 : V(1,a;r) > 0 \}}, \end{aligned}$$
$$\begin{aligned} \begin{aligned}&V(1,a;r) = \sup _{b_1> a, \; b_2, b_3> 0} \\&\quad \Bigg ( r \sum _{n = 2}^3 P\{Z = n, S_1 \le b_1, S_n \le b_n \mid S_1> a\} \; \\&\qquad -E\bigg [\min \{S_1,b_1\} - a + 1_{\{S_1 \le b_1\}} \sum _{n = 2}^3 1_{\{Z = n\}} \min \{S_n,b_n\} \mid S_1 > a \bigg ] \Bigg ). \end{aligned} \end{aligned}$$
$$\begin{aligned} V(1,a;r) = V_1(a;P\{Z = 2\} V_2(0;r) + P\{Z = 3\} V_3(0;r)), \end{aligned}$$
To conclude, for sequential multistage jobs (even with possible skips), Theorem 1 gives a direct way to compute the Gittins index, but, for the other types of multistage jobs, it is better to do the computation by utilizing the SJP framework.
7 Generalizing to the case of complex dynamics within each stage
In [12], a Markov-process job model was proposed that generalizes the multistage job model studied in this paper. Below, we outline how one can generalize Theorem 1 to this more general job model.
We begin with a brief discussion of the Markov-process job model. In the model, each job is an absorbing Markov process X(t) on a general state space. A job’s state evolves only during service, and a job completes when it reaches an absorbing state \(*\). One can define the Gittins index of a state x following the same intuition as in Remark 1. The main difference is that the stopping set is a general set of states Y. Letting \(\tau ^*(Y)\) denote the hitting time of \(Y \cup \{*\}\), we have, roughly speaking,5Consider now a sequential multistage job where each stage, instead of being an ordinary job, is an absorbing Markov process. Let \(X_j(t)\) be the jth stage’s Markov process. The state of a multistage job is then a pair \((j, x_j)\), denoting being in state \(x_j\) of the jth stage’s Markov process. When a job would reach a state \((j, *)\), it instead jumps to the (possibly random) initial state \((j+1, X_{j+1}(0))\) of the next stage, unless \(j = J\), in which case the job completes.
$$\begin{aligned} G(x) = \sup _Y \frac{P\{X({\tau ^*(Y)}) = * \mid X(0) = x\}}{E[\tau ^*(Y) \mid X(0) = x]}. \end{aligned}$$
(19)
Our main result, Theorem 1, can be generalized to sequential multistage jobs with Markov-process stages:where \(Y_J\) and \(\tau ^*_J(Y_J)\) denote sets of states and hitting times, respectively, for stage J’s Markov process, and, as usual, \(G_{\le J-1}(j,x_j)\) denotes the Gittins index of \((j,x_j)\) in the sequential multistage job with stages \(1,2,\ldots ,J-1\). The proof is essentially the same as that of Theorem 1, with tuples of real numbers \((b_j, b_{j+1}, \ldots , b_J)\) replaced by tuples of sets of states \((Y_j, Y_{j+1}, \ldots , Y_J)\).
$$\begin{aligned} \begin{aligned} G(J,x_J)&= G_J(x_J) \\ G(j,x_j)&= \sup _{Y_J} \frac{P\{X_J(\tau ^*_J(Y_J)) = *\}}{\frac{1}{G_{\le J-1}(j,x_j)} + E[\tau ^*_J(Y_J)]}, \quad j \in {\{1,2,\ldots ,J-1\}}, \end{aligned} \end{aligned}$$
The main takeaway is that one can recursively compute the Gittins index of any job which can be decomposed into multiple sequential stages, even if those stages have more complicated dynamics than ordinary jobs. However, the practical usefulness of this more general result rests on the ability to compute Gittins indices of the individual stages. Such computation of Gittins indices requires optimizing over subsets of states Y, see (19), which is likely difficult to do in general.
Acknowledgements
Ziv Scully was supported by NSF Grant Nos. CMMI-1938909 and CSR-1763701. We thank the anonymous reviewer who pointed out the connection between the scheduling problem of sequential multistage jobs and the optimal control problem of tandem queues with flexible servers.
Open Access
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.